会員登録後、有料プランで広告を非表示に
詳しくはこちら
小説 フローベール『ボヴァリー夫人』芳川泰久訳、新潮文庫、2015年。 文学関係 Gérard Genette, Narrative Discourse: An Essay in Method, translated by J. E. Lewin, Ithaca: Cornell University Press, 1980. 和訳（花輪光、和泉涼一訳『物語のディスクール——方法論の試み』水声社、1985年）もありますが、入手しづらかったので英訳版を読むことにしました。 Seymour Chatman, Story and Discourse: Narrative Structure in F…
こんにちは，今回は論理学を固めて勉強したので，ブックレビューのようなものを書いていきたいと思います。 はじめに 論理学については，4単位分の授業を受けていたのである程度知識がありましたが，今回改めて論理学を勉強したのは，前々から気になっていたこちらの本，大西琢朗『論理学』を読みたかったからです。 論理学 (3STEPシリーズ) 単行本 – 2021/11/30posted with カエレバAmazon.co.jpで詳細を見る 大西先生のツイッター(https://twitter.com/takuro_onishi)も拝見していて，変わった内容の教科書だと聞いていたので，楽しみにしていました。…
【検証】ピュアDPSはシナジーに合わせないほうがrDPSが高くなる？
FF Logs というサイトではいくつかの指標が使われますが，中でも最も重視される指標がrDPSで，これは以下の計算式より算出されます。 rDPS = DPS - Taken + Given 参考：FF Logs - Combat Analysis for FF ところで，このrDPSについて，気になる記述を見つけました。 asellog.com 上記のブログでは，ピュアDPSはシナジーに合わせないほうがrDPSが高くなると紹介されていますが，本当でしょうか。 結論から言うと，高くなりません。 バーストをシナジーに合わせても合わせなくても，ピュアDPSのrDPSは同じ値になります。 これだけ分…
今回は、2021年1月実施の英検 1day S-CBT（準1級）を受験したので、その体験記を書こうと思います。 私はもともと英語の資格試験に興味はなかったのですが、最近、自分の特技をアピールするためには資格も必要だと考えが変わったので、とりあえず英検準1級を取ることにしました。とりあえず準1級を取っておいて、中長期的に英検1級を目指そうと考えています。 そんなわけで急遽受験を思い立った英検ですが、今回私が選んだ試験方式が、英検 1day S-CBT でした。 英検 1day S-CBT は、大学入試改革に合わせて2019年に開始した英検の新方式です。実施日が多く（準1級の実施日は限られますが）…
【誤訳？】オバマ元大統領が鳩山元総理を「硬直化し、迷走した日本政治の象徴だ」と痛烈批判？について
こんなツイートが目に止まりました。 翻訳は本当に難しいです。間違いは誰にもあると思うので普段はあまり指摘することはしたくないのですが、今回はNHKもTBSも誤訳です。「硬直化し目的を失った」のは鳩山元首相を指しているのではなく、その期間の政治のことを指しています。https://t.co/j1HC1I1WWm— 「英文法さかさ勉強法」のアドバンテージ・メディア英語教室 (@advanenglish) 2020年11月18日 アメリカのオバマ元大統領が発表した回顧録において、鳩山元総理について触れられた箇所の解釈を巡って議論が起こっているようです。これについて、私の解釈と意見について書いてみたい…
お問い合わせフォーム Loading…
個人情報の収集と利用目的 当サイトでは、お問い合わせの際に、お名前（ハンドルネーム）やメールアドレス等の個人情報を頂く場合がございます。これらの個人情報は、お問い合わせに対する返信にのみ利用し、それ以外の目的で利用することはありません。 また、頂いた個人情報は、(1)ご本人の同意がある場合、(2)法令に基づき開示・提供を求められた場合を除いて、第三者に開示することはありません。 広告の表示について 当サイトでは、第三者配信の広告サービス（A8.net）を利用しています。これらの広告サービスは、ユーザーに適した広告を表示するためCookieを使用することがあります。このCookieは匿名で収集さ…
OLYMPUS OM-D E-M10 Mark IIIを買った話・買うまでの話
どうもこんにちは。 手持ちの一眼レフを売って、中古でオリンパスのOM-D E-M10 Mark IIIを買う、という体験をしたので、その経緯をだらだらと書きたいと思います。究極に私的な話で申し訳ありません。 写真が撮りたい カメラを買い換えよう 悩んだカメラたち 1. FUJIFILM X-A5 2. FUJIFILM X-E3 3. OLYMPUS PENシリーズ 忘れていたやつ おわりに 写真が撮りたい 私は高校時代に写真部に入り、そこで写真を始めました。 その時に買ったカメラがニコンのD5300です。 Nikon デジタル一眼レフカメラ D5300 AF-P ダブルズームキット ブラック…
どうもこんにちは。 これを書いているのは9月です。夏休みも終わりましたが、みなさん単語学習は完璧でしょうか。 夏休みに単語を完璧にしようと思っていたのに、新型コロナの影響で夏休みが少なくなって、結局終わっていないという現役生もいるのではないでしょうか。 それでなくとも、やろうやろうと思っていてもなかなか完璧にならないのが単語です。 しかし、そもそも単語学習はだらだらと時間をかけてやるものではないと考えています。気合を入れてこなせば短い期間で終わります。 そういうわけで、時期を問わず単語学習に不安のある受験生に向けたアドバイスをQ&A形式で書いていこうと思います。 この中にはリアルによく聞かれる…
『古代スラヴ語の世界史』（白水社）を読みました。 スラヴ人はどこから来てどのように自分たちの文字を獲得したのか。そしてスラヴ人の言語は歴史と共にどのように変化したのだろうか。 www.hakusuisha.co.jp 独自の文字を持たなかったスラヴ人社会において「古代スラヴ語」（当時の共通スラヴ語の文語）がどのように誕生し，またそれがどのように発展（ときには衰退）したか，その言語の歴史を中心に，中世以降のスラヴ人と東欧の歴史について述べた本です。著者は京大の服部文昭先生。 内容について 一般的に，前近代のスラヴ人というのは歴史の表舞台にはあまり登場しない人々だと思います。スラヴ人の文字といえば…
話には聞くグラフ理論なるものについて，そろそろ体系的に練習したいと思ったので，Aizu Online Judgeのコース問題を解いてみました。 11_A~C はプログラム上でグラフを扱う練習のような問題だったので，よりアルゴリズムっぽい 11_D~12_C を掲載しています。 問題はこちら onlinejudge.u-aizu.ac.jp 11_D: 連結成分分解 12_A: 最小全域木 12_B: 単一始点最短経路 12_C: 単一始点最短経路 II 11_D: 連結成分分解 コメント 連結成分分解というタイトルですが，連結成分ごとの頂点集合を作ったりするのではなく，Union-Find木と…
問題はこちら atcoder.jp 方針 個のスイッチのon/off状態の順列は 通り，ということで一目全探索っぽいです。 問題では電球→スイッチの対応関係しか与えられないので，スイッチ→電球の対応関係を表す配列を作っています。あとはbit全探索です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) bool judge(int bit); int n,m; vector<int> k; vector<vector<int>> s; vector<int> p…
問題はこちら atcoder.jp 方針 +が入る場所は， の各数字の間 ヶ所です。それぞれの箇所について，+が入っている状態を1，何も入っていない状態を0とすれば，bit全探索が適用できます。 各数式の値を計算するプロセスはコードを見てください。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) long long value(int bit); string s; int n; int main(){ cin>>s; n=s.size()-1; // '+'…
問題はこちら atcoder.jp 方針 購入する参考書の組み合わせが高々 通りしかないところを見るに，全探索で解くのが本命です。 今回は「bit全探索」を用いていますが，この手法を使った経験がなかったのでたどたどしいコードになっています。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int n,m,x; vector<int> c; vector<vector<int>> a; bool judge(int bit); int cost(int bit)…
問題はこちら atcoder.jp 方針 基本的な動作は，「各マスについて，周囲8マスの爆弾の数を数える」ということですが，端のマスには調べるべき8マスが存在しないので，それをどう処理するかが一つのポイントだろうと思います。 私は，マス目の周囲にダミーの要素Nを入れる，という方法を取っています。 下のコードでは肝心の爆弾の数を数える処理が冗長になってしまっていますが，解説PDF にうまい手法が紹介されています。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) …
問題はこちら atcoder.jp 方針 簡単のため，上の列をマス ，下の列をマス とします。 動き方のパターンは，どの で と動くかの高々 通りしかないので，全部調べればよいです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n; cin>>n; vector<int> a(n),b(n); REP(i,n){ cin>>a[i]; } REP(i,n){ cin>>b[i]; } int sum=0,max=0; REP…
問題はこちら atcoder.jp 方針 単位量あたりの価格が安い（コスパが良い）サイズのボトルを優先的に購入します。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long q,h,s,d; long long n; cin>>q>>h>>s>>d>>n; long long sum=0; // 2リットル入り if(d<2*s && d<4*h && d<8*q){ sum+=(n/2)*d; n%=2; } // 1リットル入り if(s<2*h && s<4*q){ sum+=n*s; n=0; }…
問題はこちら atcoder.jp 方針 数列 は を並び替えたものなので，題意の操作の結果は， となるほかありません。 このとき，置き換えられるべき要素は 以外の 個であり，1回の操作で最大 個の要素を置き換えることができます。 つまり，求める操作回数は，（ 以上で最小の整数）です。 操作は を含む部分から始めればよく，操作回数は数列の並びによらず一定なので，実は を受け取る必要もありません。 （簡単すぎて嘘解法かと疑いましたが，解説PDFでも同様の解法が紹介されていました。こちらには証明もついています。） コード #include <bits/stdc++.h> using namespa…
ABC168 C - : (Colon) をベクトル計算で解く
ABC168のC問題ではゴリゴリの幾何問題が出題され，「余弦定理」がツイッターでトレンド入りするなど話題になりました。 私は普通に余弦定理を用いて解いたのですが，結構いろいろな解き方があったようです。ここでは，自分が後で思いついたうちの1つである「ベクトル」を用いた解法を示していきたいと思います（ベクトルの内積の定義に が使われているので，本質的には余弦定理と同じですが）。 問題はこちら atcoder.jp 前提 時計の中心を とし，時針，分針の でない端点をそれぞれ と表す。また， とし（長さが大文字なのは気持ち悪かったので問題文から変更しています）， 軸の正の方向と とのなす角をそれぞれ…
日立製作所 社会システム事業部 プログラミングコンテスト2020 B - Nice Shopping
問題はこちら atcoder.jp 方針 かかる金額が最小になるような買い方は，一番安い冷蔵庫と一番安い電子レンジを買うか，割引券が使える 種類の買い方のどれか，のいずれかです。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ int A,B,m; cin>>A>>B>>m; vector<int> a(A),b(B); int lowest_a=100001,lowest_…
問題はこちら atcoder.jp 方針 題意の操作を実際に実行しながら調べます。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n; cin>>n; vector<int> h(n); bool judge=true; REP(i,n){ cin>>h[i]; if(i>0){ if(h[i-1]==h[i]+1){ h[i]++; }else if(h[i-1]>h[i]+1){ judge=false; break; }…
AGC012 A - AtCoder Group Contest
問題はこちら atcoder.jp 方針 を降順ソートします。このとき， の中から各チームの2番目の人の強さをできるだけ大きくするには， のようにチーム分けをすれば良いです。つまり，求める和は です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ long long n; cin>>n; vector<long long> a(3*n); REP(i,3*n){ cin>>…
問題はこちら atcoder.jp 方針 各 に対して， if 問題P[i]がAC済{ continue }else{ if 提出iがAC{ 正解数++ ペナルティ数+=問題P[i]のWA数 }else{ 問題P[i]のWA数++ } } という操作を行います。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) int main(){ int n,m; cin>>n>>m; vector<int> p(m); vector<string> s(m); REP(i…
問題はこちら atcoder.jp 方針 を昇順ソートすると，求める最小値は， のうち最も小さい値です。 コード #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0; i<(n); i++) #define ALL(n) begin(n),end(n) int main(){ int n,k; cin>>n>>k; vector<int> h(n); REP(i,n){ cin>>h[i]; } sort(ALL(h)); int d,d_min; REP(i,n-k+1){ d=h[i+k-1]…
問題はこちら atcoder.jp 方針 なので普通にループを回しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; int ans=1; for(int i=2; i<=sqrt(x); i++){ for(int j=2; j<1000; j++){ if(pow(i,j)>x){ break; } if(pow(i,j)>ans){ ans=pow(i,j); } } } cout<<ans<<endl; }
問題はこちら atcoder.jp 方針 直感で解きました。 後付けで証明もしておきます。 求める和は， と表せます。ここで，ある整数を で割った余りは なので， です。 { } { } と並べ替えたとき，これを満たします。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long n; cin>>n; cout<<n*(n-1)/2<<endl; }
問題はこちら atcoder.jp 方針 問題文通りです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; string subs,a="a",b="b"; int i=1; while(a!=b){ subs=s.substr(0,s.size()-2*i); a=subs.substr(0,(s.size()-2*i)/2); b=subs.substr((s.size()-2*i)/2,(s.size()-2*i)/2); i++; } cout<<subs.size()<<e…
AGC029 A - Irreversible operation
問題はこちら atcoder.jp 方針 題意の操作は，文字列 においてBWをWBにすることと同じです。また， がWW...WBB...Bとなった時点で操作は終了します。 つまり，Wに注目すると， 回の操作で つのWが つ左に動き， 中にWが 個あるとき，一番うしろのWが 番目に来た時点で操作が終了します。 中で 個目のWが 番目にあるとき，これを 番目に移動させるためには 回の操作が必要です。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; vector<int> coor_w; …
三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105
問題はこちら atcoder.jp 方針 円ちょうどの買い物をできるならば，買う品物の数は 個( は の商) とできます1。 個の商品による合計金額 は なので， がこの範囲に含まれているかを判定すればよいです。コード中では余り を用いてやや工夫しています。 解説PDF では3種類の解法が紹介されています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; int q=x/100; int r=x%100; cout<<(r<=q*5)<<endl; } (i)買う品物の数が 個以上のとき，…
問題はこちら atcoder.jp 方針 日後に家に戻ってくるためには，旅程にNがあるならばSが少なくとも1つ必要で，SがあるならばNが少なくとも1つ必要です。W,Eについても同様。個数は関係ありません。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool north=false; bool south=false; bool east=false; bool west=false; bool judge=true; for(int i=0; i<s.size(); i++){…
問題はこちら atcoder.jp 方針 特になし。偶奇の場合分けのやり方はいくつかあると思います。 コード #include <bits/stdc++.h> using namespace std; int main(){ string o,e; cin>>o>>e; string password; for(int i=0; i<o.size(); i++){ password.push_back(o[i]); if(e.size()==i){ continue; } password.push_back(e[i]); } cout<<password<<endl; }
問題はこちら atcoder.jp 方針 に現れる最初のAから最後のZまでの文字列が，条件を満たす最長の文字列になります。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int firstA=-1; int lastZ=-1; for(int i=0; i<s.size(); i++){ if(s[i]=='Z'){ lastZ=i; } if(firstA!=-1){ continue; } if(s[i]=='A'){ firstA=i; } } cout<<lastZ-fir…
問題はこちら atcoder.jp 方針 レンガが123...と並ぶように，邪魔なレンガを砕いていきます。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int count=0; int aim=1; for(int i=0; i<n; i++){ if(a[i]!=aim){ count++; }else{ aim++; } } if(aim==1){ count=-1; } …
問題はこちら atcoder.jp 独り言 画像の引き伸ばしってこういう感じでやってるんかな。 コード #include <bits/stdc++.h> using namespace std; int main(){ int h,w; cin>>h>>w; vector<vector<char>> c(h,vector<char>(w)); vector<vector<char>> d(h*2,vector<char>(w)); for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ cin>>c[i][j]; d[i*2][j]=c[i][j]; d…
問題はこちら atcoder.jp 方針 「 の末尾を取得し， の先頭に挿入→ の末尾以外を とする」という操作で， を「回転」させることができます。 を回転させて得られる文字列は高々 種類なので， 回の操作後までに と一致するか調べればよいです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s,t; cin>>s>>t; string first; bool possible=false; for(int i=0; i<s.size(); i++){ first=s.substr(s.size()-…
問題はこちら atcoder.jp 方針 を辞書順にソートし，連結すればいいのですが，C++ではsort関数でstringもソートできるので簡単です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,l; cin>>n>>l; vector<string> s(n); for(int i=0; i<n; i++){ cin>>s[i]; } sort(s.begin(),s.end()); string min; for(int i=0; i<n; i++){ min+=s[i]; } cout<<min<…
問題はこちら atcoder.jp 方針 「 を辞書順にソート→ を高い順にソート」という方針で解けそうですが，市名，点数，レストランの番号の3変数をどう扱うか。 ということで，tupleを使ってみました。 解説PDF では，pairを入れ子にして3変数を扱っています。どちらが楽かは好みだと思います。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; string s; int p; vector<tuple<string,int,int>> r; for(int i=0; i<n; i++…
ABC050 B - Contest with Drinks Easy
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> t(n); for(int i=0; i<n; i++){ cin>>t[i]; } int m; cin>>m; vector<int> p(m),x(m); for(int i=0; i<m; i++){ cin>>p[i]>>x[i]; } for(int i=0; i<m; i++){ int sum=0; for(int j=0; j<n; j++){ if(j==p…
問題はこちら atcoder.jp 方針 によって税抜き価格のあたりをつけるのですが，int型は小数点以下切り捨てであるという性質上，本当の税抜価格は，a_sup,b_sup以上の整数です。 a_sup,b_sup以上である周辺の整数のうち，条件を満たすものが見つかり次第それを出力します。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; int a_sup,b_sup; a_sup=a/0.08; b_sup=b/0.1; int m=max(a_sup,b_sup); bool…
ABC093 B - Small and Large Integers
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b,k; cin>>a>>b>>k; for(int i=0; i<k; i++){ if(a+i>=((double)a+b)/2){ break; } cout<<a+i<<endl; } for(int i=k-1; i>=0; i--){ if(b-i<((double)a+b)/2){ continue; } cout<<b-i<<endl; } }
問題はこちら atcoder.jp 方針 構造的に難しい点はありませんが，2点間の距離の公式がやや複雑なのでコードもごちゃごちゃしています。 私は整数かどうかの判定は，「int型とdouble型の値が一致するか」，という発想をよく用いるのですが，他にやっている人を見たことがありません。何か技術的にまずい点があるのかもしれません。 一応AtCoderの解説PDFもご覧ください。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,d; cin>>n>>d; vector<vector<int>> x(n,vect…
問題はこちら atcoder.jp 方針 「その単語はまだ発言していない単語である」ことと「その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する」ことを確認しています。計算量が少ないので特に工夫はしていません。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<string> w(n); for(int i=0; i<n; i++){ cin>>w[i]; } bool judge=true; for(int i=1; i<n; i++){ if(w[i-1][w[i…
問題はこちら atcoder.jp 方針 to_stringを使ってみたかったので複雑になっています。 digit_sum+=i_str[j]-'0'の-'0'については，こちらを参考にしました。ASCIIコードでは文字'0'が48に対応しているらしいです。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,a,b; cin>>n>>a>>b; int sum_total=0; int digit_sum=0; string i_str; for(int i=1; i<=n; i++){ digit_sum=…
問題はこちら atcoder.jp 方針 各都市ではなく道路に注目しています。C. Peaks（記事にする予定）と似た発想です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> a(m),b(m); for(int i=0; i<m; i++){ cin>>a[i]>>b[i]; } vector<int> count(n); for(int i=0; i<m; i++){ count[a[i]-1]++; count[b[i]-1]++; } for(i…
問題はこちら atcoder.jp 方針 ボタンの挙動は問題分の通りに作ります。 問題はボタン が点けられるかの判定ですが， 回の操作後までにボタン が光らない場合，初期のボタン も含めてこれまでに 回ボタンが光っています。ボタンの数は 個なので，少なくとも 個のランプが 度光っています。つまりループしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int count=…
問題はこちら atcoder.jp 方針 あらかじめ縁のための配列を確保しておきます。 コード #include <bits/stdc++.h> using namespace std; int main(){ int h,w; cin>>h>>w; vector<vector<char>> a(h+2,vector<char>(w+2)); for(int i=1; i<h+1; i++){ for(int j=1; j<w+1; j++){ cin>>a[i][j]; } } for(int j=0; j<w+2; j++){ a[0][j]='#'; a[h+1][j]='#'; } f…
問題はこちら atcoder.jp 方針 以上の整数 について， 未満のすべての素数で割り切れなければ， は素数である，という普通の素数判定。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; vector<int> p={2}; bool not_prime=false; int i=2; while(i<=x (not_prime==true && i>x)){ not_prime=false; for(int j=0; j<p.size(); j++){ if(i%p[j]==0…
問題はこちら atcoder.jp 方針 のように を小さくしながら考えます。それぞれの に対して を最大にする貪欲法を用いています。ある A_i は B_i-1, B_i にのみ制約されるので，貪欲法で最適解が求まります。 （アルゴリズムがほぼ分からないので雰囲気で言ってます。間違い等あればご指摘ください。） コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n),b(n-1); for(int i=0; i<n-1; i++){ cin>>b[i]; } in…
問題はこちら atcoder.jp 方針 まず の桁数を比較し，それが同じ場合には大きい位の値から比較していきます。 コード #include <bits/stdc++.h> using namespace std; int compare(string x,string y,int i); int main(){ string a,b; cin>>a>>b; int i=0; if(a.size()>b.size()){ cout<<"GREATER"<<endl; }else if(a.size()<b.size()){ cout<<"LESS"<<endl; }else{ compare…
問題はこちら atcoder.jp 方針 番目のマスから順に試していき，最大値が出るたびに暫定の最大値を更新しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long> h(n); for(int i=0; i<n; i++){ cin>>h[i]; } int count=0,count_temp=0; for(int i=1; i<n; i++){ if(h[i-1]>=h[i]){ count_temp++; if(count_temp>count){ co…
問題はこちら atcoder.jp 方針 普通に足すだけ。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long long> l(n+1); l[0]=2,l[1]=1; for(int i=2; i<=n; i++){ l[i]=l[i-1]+l[i-2]; } cout<<l[n]<<endl; }
ABC124 C - Coloring Colorfully
問題はこちら atcoder.jp 方針 「どの隣り合う 枚のタイルも異なる色で塗」るということは，10101...か01010...のいずれかです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int count_1=0,count_2=0; //10101... for(int i=0; i<s.size(); i++){ if(i%2==0){ if(s[i]=='0'){ count_1++; } }else{ if(s[i]=='1'){ count_1++; } } …
問題はこちら atcoder.jp 方針 回ループを回せば良いのですが， 秒（ 年）かかってしまいます。 対称性があるので綺麗に消えそうだなと思いつつ，与 をそれぞれ ， 回の操作後の を として式をいじっていると， すごいですね。 は に全く関係ないようです。 コード #include <bits/stdc++.h> using namespace std; int main(){ long long a,b,c,k; cin>>a>>b>>c>>k; cout<<(k%2==0 ? a-b : b-a)<<endl; } 補足 ACを通してから， ただし、答えの絶対値が を超える場合は、代…
問題はこちら atcoder.jp 方針 いっぱいループしました。 コード #include <bits/stdc++.h> using namespace std; int main(){ string w; cin>>w; vector<int> count(26); bool check=true; char c='a'; for(int i=0; i<26; i++){ for(int j=0; j<w.size(); j++){ if(w[j]==c){ count[i]++; } } c++; } for(int i=0; i<26; i++){ if(count[i]%2!=0)…
ABC118 B - Foods Loved by Everyone
問題はこちら atcoder.jp 方針 ゴリゴリ調べる。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> k(n); vector<vector<int>> a(n, vector<int>(m)); for(int i=0; i<n; i++){ cin>>k[i]; for(int j=0; j<k[i]; j++){ cin>>a[i][j]; } } bool check=false; int count=0,loved=0; for(int i…
5月になりました。みなさんいかがお過ごしでしょうか。 ピカピカの新大学生の私はずっと家にいて，まだ1回しか登校していません。京アニでも見た鴨川の桜がとても綺麗だったのを覚えています。 とは言えいい加減春休みも終わるので，ブログに関係する今やっていること，やりたいことをまとめておこうと思います。 やっていること 読書 今現在，以下の二冊を読んでいます（授業の教科書とサブテキストなんですが…）。 宮崎修一『アルゴリズム理論の基礎』 内田賢德 乾善彦 編『万葉仮名と平仮名: その連続・不連続』 いずれもいい本なので，感想とかを書いて記事にしたいと思っています。特に下の本みたいなやつはこのブログのメイ…
問題はこちら atcoder.jp 方針 「任意の整数 に対して，」「（ の最小値）」です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> p(n); for(int i=0; i<n; i++){ cin>>p[i]; } int temp_min; int count=1; // i=1は常に条件を満たす temp_min=p[0]; for(int i=1; i<n; i++){ if(p[i]<temp_min){ count++; temp_min=p[…
問題はこちら atcoder.jp 方針 で場合分け（tex機能の関係で不等号の向きが不自然になってますが合ってます）。 ちなみにVS CodeをUbuntuストアからでなくMicrosoftからダウンロードしてインストールしたら日本語が打てるようになりました。 コード #include <bits/stdc++.h> using namespace std; int main(){ long a,b; cin>>a>>b; if(a<=0 && b>=0){ cout<<"Zero"<<endl; }else if(a>0){ cout<<"Positive"<<endl; }else{ i…
Mondai wa kochira atcoder.jp Houshin ga de saidai no youso deatta baai wa, 2-banme ni ookii youso wo syuturyoku simasu. sore igai no baai wa sonomama saidai no youso wo syuturyoku sureba iidesu. Ubuntu 20.04 LTS ni upgrade shitara, VS Code de nihongo ga utenaku narimasita. Code #include <bits/stdc++…
問題はこちら atcoder.jp 方針 ナイーブに 人の点数をいちいち引くのでは間に合いません。ラウンドで出た正解数は と分かっているので，各問の正解者に 点ずつ与えて，最後で一律に 点を引いても同じことです。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,k,q; cin>>n>>k>>q; vector<int> a(q); for(int i=0; i<q; i++){ cin>>a[i]; } vector<int> correct(n); //正解数 for(int i=0; i<q; i++…
問題はこちら atcoder.jp 方針 枚だけで全てのゲートを通過できるIDカードは， から まですべての共通範囲です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> l(m),r(m); for(int i=0; i<m; i++){ cin>>l[i]>>r[i]; } bool exist=true; int tent_l=0,tent_r=0; tent_l=l[0]; tent_r=r[0]; for(int i=0; i<m-1; i++)…
問題はこちら atcoder.jp 方針 AからZまでのアルファベットが 文字で， より，全探索でも 回以下のループで済みます。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool judge=false; bool exist=false; char i='a'; char result; while(judge==false && i<='z'){ for(int j=0; j<s.size(); j++){ if(s.at(j)==i){ exist=true; brea…
問題はこちら atcoder.jp 方針 この問題AtCoderでやったことある気がするけど印ついてなかった。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b,c,x; cin>>a>>b>>c>>x; int count=0; for(int i=0; i<a+1; i++){ for(int j=0; j<b+1; j++){ for(int k=0; k<c+1; k++){ if(500*i+100*j+50*k==x){ count++; } } } } cout<<count<<endl; …
問題はこちら atcoder.jp 方針 文字目以外がちゃんと数字になっているかチェックするのが面倒かな，と思ったら， は数字またはハイフンからなるという制約がありました。優しい。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; string s; cin>>a>>b>>s; bool judge=true; if(s.size()!=a+b+1){ judge=false; }else if(s.at(a)!='-'){ judge=false; } for(int i=0; i<a+b+1; i+…
ABC052 B - Increment Decrement
問題はこちら atcoder.jp 方針 特になし。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; string s; cin>>n>>s; int x=0; int x_max=0; for(int i=0; i<n; i++){ if(s.at(i)=='I'){ x++; }else{ x--; } if(x>x_max){ x_max=x; } } cout<<x_max<<endl; }
私はブログ記事内で数式を書きたいとき，はてなブログのTex機能を利用しています。 使い方は簡単で，Texのコマンドを[tex:]タグの中に書くだけです。 例えば，[tex:e^{i \theta} = \cos \theta + i \sin \theta]のように書くと， オイラーの公式が表示されます。 非常に便利なこの機能なのですが，機能自体の不完全さや，TexコマンドとMarkdown記法の衝突によって，うまく表示されないことがよくあります。 例えば， [tex: A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 …
どうも，『アルゴリズム理論の基礎』でアルゴリズムを初めて勉強しているshadeです。 まだ読了できていませんが，競技プログラミングでは頻出（多分）の動的計画法（DP）について一通り勉強したので，アウトプットも兼ねてAtCoderの「Educational DP Contest / DP まとめコンテスト」の問題を解いていきたいと思います。 順次解いた問題は追加されます。 コンテストページはこちら atcoder.jp A - Frog1 方針 足場 から足場 に辿り着くまでのコストの総和の最小値を ，足場 から足場 に行くためのコストを ，足場 から足場 に行くためのコストを と表すと， であ…
私は一浪して予備校に通い，京都大学（文系）に合格しましたが，現役時は独学をしていました。教科書の内容すら全範囲は扱われないような高校だったので，基礎から自力で勉強する必要がありましたが，良い勉強方法がわからず，現役時は数学「だけ」のせいで落ちたと言っても過言ではありません（得点率およそ1割）。 そんな私でも，予備校生活の一年間で数学力は格段に伸びました（と言ってもせいぜい合格者平均くらいですが）。 現役の頃と浪人生活の一年では何が違ったのか考えました。もちろん予備校に通える方は通えば良いのかもしれませんが，数学がとても苦手だけど京大を目指したいという方に向けて，自分が使った参考書なども思い出し…
AtCoder Problems の Boot camp for Beginners を埋めていく
AtCoder ProblemsのBoot camp for Beginnersに掲載されている問題を埋めていきたいと思います。言語は基本的にC++(g++)です。自分の復習用に記録していきますが，公開しておけば詳しい方からアドバイスがもらえたりするかもしれないと思って。AtCoder Problemsのdifficulty基準で，下に行くほど難易度が上がる（傾向がある）ようです。 Easy 100 #1 B. Power Socket #2 C. Rally #3 B. Qualification simulator #4 B. Tax Rate #5 B. Can you solve th…
問題はこちら atcoder.jp 方針 の各文字について， 内にそれが何個存在するかを数えています。 個以上あればアウト。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool check=false; for(int i=0; i<s.size(); i++){ int counter=count(s.begin(),s.end(),s[i]); if(counter>=2){ check=true; break; } } if(check==false){ cout<<"y…
問題はこちら atcoder.jp 方針 正方形に外接する，各辺が 軸， 軸に平行であるような正方形を描いて考えました。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x_1,y_1,x_2,y_2; cin>>x_1>>y_1>>x_2>>y_2; int a=y_1-y_2; int b=x_2-x_1; int x_3,y_3,x_4,y_4; x_3=x_2+a; y_3=y_2+b; x_4=x_3-b; y_4=y_3+a; cout<<x_3<<" "<<y_3<<" "<<x_4<<" "<<…
問題はこちら atcoder.jp 方針 の 桁である部分文字列を一つずつ調べています。 ご主人様が大好きな数は なのに，問題名は で変だなと思ったら，ABC114は シリーズなんですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int number=0,min=0; for(int i=0; i<s.size()-2; i++){ number=stoi(s.substr(i,3)); if(abs(number-753)<min min==0){ min=abs(nu…
問題はこちら atcoder.jp 方針 工夫点は入力段階で一度偶奇判定をしていることくらいです。簡単。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; bool even=true; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; if(a[i]%2!=0){ even=false; } } int count=0; while(even==true){ for(int i=0; i<n; i++){ a[i]/=2; if(a[…
問題はこちら atcoder.jp 方針 を 個で割って，余った分を場合分け。 コード #include <bits/stdc++.h> using namespace std; int main(){ long n,a,b; cin>>n>>a>>b; long q=n/(a+b); long r=n%(a+b); if(r<=a){ cout<<q*a+r<<endl; }else{ cout<<(q+1)*a<<endl; } }
問題はこちら atcoder.jp 方針 体力 のモンスターを倒すのに必要な攻撃回数を求めるアルゴリズムを とすると， times(H){ if H=1 1 を出力 else if H>=2 2*times([H/2])+1 を出力 } と再帰的に表せます（ は最初の攻撃）。] （ガウス記号，床関数）の処理がありますが，整数型は小数点以下切り捨てなので実際には何もする必要がありません。 かなり易しい部類のD問題ですね。 コード #include <bits/stdc++.h> using namespace std; long times(long h){ if(h==1){ return 1…
問題はこちら atcoder.jp 方針 人目の参加者が期間中に食べるチョコレートの数は， を満たす （ は非負整数）の個数です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,d,x; cin>>n>>d>>x; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int eat=0; for(int i=0; i<n; i++){ for(int j=0; j<d; j++){ if(a[i]*j+1>d){ break; } eat++; }…
AGC027 A - Candy Distribution Again
問題はこちら atcoder.jp 方針 要求するお菓子が少ない子どもから順番に配っていけばいいですが， 番目まで配って 番目の子どもに配る際は注意が必要。要求するぴったりの数でないと喜んでくれないので，別で（残っているお菓子の数）（ 番目の子どもが要求するお菓子の数）であるかを確認しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,x; cin>>n>>x; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } sort(a.begin()…
問題はこちら atcoder.jp 方針 「コラッツの問題」を題材にした問題です。私は数学には詳しくないので名前は知りませんでしたが，これを題材にした入試問題を見たことがあります。 例を見れば分かりますが， になった後は の繰り返しになっています。どのような に対してもこうなるというのが「コラッツの問題（予想）」の主張で，これを証明なしに用いてコードを書いてしまいました。 AtCoderの解説PDFでは， を順番に求めていく方法が本解となっています（そりゃそうだ）。ちょうどコード例は掲載されていなかったので，近いうちにこちらの方法でのコードを追記しておきます。 コード #include <bi…
問題はこちら atcoder.jp 方針 ごちゃごちゃした問題文ですが，求めるコストは から までにある料金所の数と， から までにある料金所の数のうち小さい方です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m,x; cin>>n>>m>>x; vector<int> a(m); for(int i=0; i<m; i++){ cin>>a[i]; } int cost_0=0,cost_n=0; for(int i=0; i<m; i++){ if(a[i]<x){ cost_0++; }else…
問題はこちら atcoder.jp 方針 は高々10文字なので，考えられる の部分文字列をすべてチェックしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; string subs; int length=0; for(int i=0; i<s.size()+1; i++){ for(int j=0; j<s.size()-i+1; j++){ bool judge=true; subs=s.substr(j,i); for(int k=0; k<i; k++){ if(su…
問題はこちら atcoder.jp 方針 問題文を読むと，出席番号 番の生徒は 番目に登校したことが分かります。つまりこれを変換して， 番目に登校した生徒の出席番号 を出力する配列を作れば終わりなのですが，ここで頭が混乱してしまいました。ということでC++のレファレンスを調べていると，vector<pair>で2要素をペアにして扱えるらしいことが分かったので，そちらを使って実装しています。firstに ，secondに の情報が入っています。この状態でsortすると，firstが小さい順 secondが小さい順でソートされます。なお，AtCoderの解説PDFでは，最初に示した方法が華麗に実装…
問題はこちら atcoder.jp 方針 「最後に残る具材の価値を最大にしたい」ということは，「 回目の操作で最も価値の大きい2つを鍋に投入したい」ということです。 鍋に入れられた具材の影響力は回数を経るごとに で割られて小さくなっていくので，価値の小さい具材から鍋に入れていけばいいです。コード中では， 回目の操作のみint型同士の計算になるので，double型に変換して小数点以下が出るようにしています（もともと をdouble型で宣言すれば済む話ですが，どっちの方が綺麗なコードなんでしょうか）。 コード #include <bits/stdc++.h> using namespace std…
ABC132 C - Divide the Problems
問題はこちら atcoder.jp 方針 題意の を値の小さい順に並べ替えると，求める の個数は， より大きく， 以下である整数の個数に等しい。簡単な問題なんですが，僕は最初 for(int i=d[n]; i<d[n-1]+1; i++){ int arc=0,abc=0; for(int j=0; j<n; j++){ if(d[j]>=i){ arc++; }else{ abc++; } } if(arc==abc){ count++; } } こんな大層なループを作ってTLEになりました。脳死はいけません。 コード #include <bits/stdc++.h> using name…
問題はこちら atcoder.jp 方針 例3が見るからにTLEを誘っているので，馬鹿正直に題意の操作をするのは断念。 のとき，題意の操作により は となっていきます。 となるまでこの操作を続ける（ を で割り切れなくなるまで割る）と，（ : を で割った余り）となり，以後 のときに合流します。問題は のときですが，これは操作を続けても か にしかならないので，このうち小さい方を出力すればいいですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ long n,k; cin>>n>>k; long surplus=n…
問題はこちら atcoder.jp 方針 言われた操作を記述するだけですが，while内を単に … a=b/2+c/2; b=c/2+a/2; c=a/2+b/2; … などとしてしまわないように注意。きれいな漸化式なのでやりたくなります。 「無限回操作が行える 有限回の操作後，初期状態に戻る」と解釈しています（証明はしていません）。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a_ini,b_ini,c_ini; //A,B,Cの初期値 cin>>a_ini>>b_ini>>c_ini; int a=a_…
ABC160 C - Traveling Salesman around Lake
問題はこちら atcoder.jp 方針 一番距離の遠い家と家の間を避けて湖を一周すればいいです。 と の間は原点を通るので別で計算しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int k,n; cin>>k>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a.at(i); } int d_max=0; for(int i=0; i<n-1; i++){ if(d_max<a.at(i+1)-a.at(i)){ d_max=a.at(i+1)-a.a…
問題はこちら atcoder.jp 方針 特に難しい点はありませんが， のとき が出力されないよう変数maxを で初期化しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int count_max=0; int max=1; // 求める整数 for(int i=1; i<n+1; i++){ int count=0; int j=i; while(j%2==0){ j/=2; count++; } if(count>count_max){ count_max=count; m…
問題はこちら atcoder.jp 方針 与えられた を大きい順にソートして，交互に取ってもらっています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a.at(i); } int alice=0,bob=0; // aの要素を大きい順にソート sort(a.begin(),a.end()); reverse(a.begin(),a.end()); if(n%2==0){ for(int i=…
ABC074 B - Collecting Balls (Easy Version)
問題はこちら atcoder.jp 方針 「これら 台のロボットのうちいくつかを起動して」なんて言われると身構えてしまいますが，各 に対して，ボールと近い方のロボットを起動するだけですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,k; cin>>n>>k; vector<int> x(n); for(int i=0; i<n; i++){ cin>>x.at(i); } int d_sum=0; for(int i=0; i<n; i++){ if(x.at(i)<k-x.at(i)){ d_sum…
問題はこちら atcoder.jp 方針 と を数値として受け取るか文字列として受け取るか迷いましたが，数値だと桁数による場合分けが必要な解法しか思いつかなかったので文字列扱いにしています。 string型で受け取ってもstoi関数でint型に変換できるので便利ですね。平方数かどうかの判定は， が整数になるかどうかで行っています。これが本解かと思いましたが，AtCoderの解説PDFでは を総当たりで調べています。 コード #include <bits/stdc++.h> using namespace std; int main(){ string a,b; cin>>a>>b; int a…
問題はこちら atcoder.jp 指針 例によってスマートな解き方が分かりません。数字表と判定表の2つのビンゴシートを作って穴が開く場所を先に調べ，後からビンゴの成立を調べています。本問は のビンゴなので何でもないですが， だったりした場合にはビンゴの成立判定を工夫する必要がありそうですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ vector<vector<int>> a(3,vector<int>(3)); vector<vector<bool>> a_m(3,vector<bool>(3)); for(…
パナソニックプログラミングコンテスト2020 B - Bishop
問題はこちら atcoder.jp 指針 問題を読んでもあまり意味が分かりませんが，よくよく例を見てみれば，左上端（初期位置）を としたとき， の と の偶奇が一致するマス目に印がつくことになりそうです。文中の条件式からも と の偶奇が一致しないマス目には行けないことが分かります。 と をint型で宣言すると例3でオーバーフローしてしまったので，long型にしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ long h,w; cin>>h>>w; if(h==1 w==1){ cout<<1<<end…
三井住友信託銀行プログラミングコンテスト2019 B - Tax Rate
問題はこちら atcoder.jp 指針 こういう小数の処理にはかなり苦手意識があります。 とりあえず で仮の を出しておいて，その で逆算してうまく行かなければ と を試してます。 センスがないコードでごめんなさい。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int x; x = n / 1.08; int n_p1=x*1.08; int n_p2=(x+1)*1.08; int n_p3=(x+1)*1.08; if(n_p1==n){ cout<<x<<endl; }else…
問題はこちら atcoder.jp 指針 特に言うことはないです。指示通り。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; int socket=1; int i=0; while(socket<b){ socket+=a-1; i++; } cout<<i<<endl; }
CODE FESTIVAL 2016 qual B B - Qualification simulator
問題はこちら atcoder.jp 指針 問題文中の 国内の学生は、現在予選の通過が確定した参加者がA+B人に満たなければ、予選を通過する 海外の学生は、現在予選の通過が確定した参加者がA+B人に満たず、さらに海外の学生の中での順位がB位以内なら、予選を通過する を忠実に実装していきます。 「現在予選の通過が確定した海外の学生がB人に満たない」と言えばいいところを，「海外の学生の中での順位がB位以内」という表現を使っているのはなぜだろうかとちょっと考えましたが，同義と捉えて問題ないです（ですよね？）。 コード #include <bits/stdc++.h> using namespace s…
ABC121 B - Can you solve this?
問題はこちら atcoder.jp 指針 問題文の通り。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m,c; cin>>n>>m>>c; vector<int> b(m); for(int i=0; i<m; i++){ cin>>b.at(i); } vector<vector<int>> a(n,vector<int> (m)); for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin>>a.at(i).at(j); } } int count=0;…
問題はこちら atcoder.jp 指針 スマートな方法が思いつかなかったのでローラー作戦。 なのでそれでも問題なさそう。問題文通りに整数 と一次元ベクタ を宣言して， の最小の要素から最大の要素までの範囲で を動かし，求める最小値を出しました。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> x(n); for(int i=0; i<n; i++){ cin>>x.at(i); } int sum=0,sum_min=0; sort(x.begin(),x.end…
「ブログリーダー」を活用して、shadekyunさんをフォローしませんか？
指定した記事をブログ村の中で非表示にしたり、削除したりできます。非表示の場合は、再度表示に戻せます。
画像が取得されていないときは、ブログ側にOGP(メタタグ)の設置が必要になる場合があります。
