atCoder の過去問を解いていくろぐ。（atCoder Problems のユーザーページ)
わからんまま保留しているもののリスト→ わからんものリスト
本番で50分ほどあったのに解けなかったやつ。テーブルを前もってつくることで高速化。アルファベットの個数 << t の長さ << 答えの大きさ という大小関係をとらえる感覚が鈍かった。そこに気づけば、かなり重い前処理でもAC, のちにしーやん先生にならって逆にみていくのがミソのLUT版を投稿: 7041951
N小さかったので、すなおにDFSで。next permutation 使えるなとおもったけど、未実施
サイズを数える機能つき Union Find をその場で実装しちゃえとおもって、ソラで書いて無限にバグった。反省: 705691
探索によらない、グラフの性質を考える問題。 スター接続のときが、最も「距離２ペア」の数が多く、そのとき \(\frac{(n-1)(n-2)}{2}\) 個ある、などから考えていく。
解説読むまでわからず、読んで「わかった」つもりでも、実装段階で数回間違った。 要反省： 7059102
ABC040D (二個まえにやった) の反省を生かして、手元ライブラリの UnionFind を使う。これは、配列を上手につかって、 連結成分のサイズもとれるやつなので、これ使えばすごくいいではないか、道路で連結だった場合のみ Unite するようにしよう！ と思ってよろこんで書いたやつは WA
解説によるとガロア体上の連立方程式と思えみたいなことが書いてあった気がする。今回は、Nがちっさいので全探索した。 Hacker's delight に population count あったなぁというので、ビット列を使った高速化：7089408
みんな大好きフィボナッチって感じで、書くだけだったけど、「入力例３」がなかったら、バグに気づかずWAしてたかも。 壊れているのを特別に -1 とかで表現するか、実際投稿したやつのように二つの配列に分けるか悩んで後者にしたんだけど、 broken[a] = true に設定するだけじゃなくて、stairs[a] = 0 にしないといけない（んだが、問題になるのは a = 1 のときのみ） てのにはまった：7091512
自力では解けなかった。解説参照：7097088
着想は自力で正解だったのだけど、牛刀を使おうとして失敗。AtCoder Problems で Moderate (50%) サジェストされるやつなので、二問にいっかいくらいは自力で解きたい。
自力で解けそうだったんだけど、RE に悩まされる。 原因は、Warshall-Floyed のための配列が大きくなりすぎたことのようだった。 （そこにたどり着くまでに３０分ロス） 任意の二点間の距離を求める必要はないので、Warshall-Floyed に頼る必要はなかった。
あとで実装しなおす。→ した： 7102655
わからず、解説みた。中学～高校数学って感じの問題だった。解説に書かれていなくて必要な知識は、以下の２つくらいだったかな： 7160019
「AtCoder の問題を問題を分類しました」の 5.5 グラフより。7160319
「ゼロサムゲームだ！」って感じでふつうにとけた 7160711
ゼロサムちがう気もする。（ちがう）
最初の着想でそのまま解けた。 7164832
Difficult(20%) だけど解けそう！と思ったもののWA。くっ、やはり。
ワーシャルフロイドの過程で、距離を書き換えるケース（経路圧縮？）でついでに消していけばよかろうと思ったものの、うまくいかなかった。なんでうまくいかないのか、 まだ理解してない → わからんものリスト へ。
ひとまず、解説通り、まずは最短経路を求めておいてから、最短経路の一部になっているかどうかを調べる方法を採用： 7165628
Difficult(20%) で推薦されたやつ。わかんなかったので、解説見て「うむむ、なるほど…？」ってなってる。あとで再挑戦。
あとで書こうとしてみたけど、結局わかんなくなって写経。あとでもいっかい考える: 7168802
つぎの日に、自分で書けるかやってみた。ちょっと間違い。そうか、0個まで買った状態で次に買う商品は0番なので、商品番号はゼロ始まりにしなきゃ。 だった。 7183167
まず、Warshall-floyd を使うときの初期化で、自分へもどってくるのをゼロに初期化すべきだったところでバグ。そっちは自分で気づいたんだけど、Inf にあたる数が小さすぎてWAを連発してしまった。これは、初期化にも、最後のMinを求めるときにも使う： 7208397
おおまかな方針はすぐわかったのだけど、隣接行列でやろうとして失敗。そこから心を入れ替えて一応自力で解けたけど、時間かかりすぎ。 はじめから、この実装にたどりつきたかった： 7211329
難しかった。補グラフを考えるという発想自体がなかった。けっか、できたプログラムはすごく簡潔： 7224022
Educational DP Contest A を解いてみた。普通にとけたけど、これは典型的なDPの書き方になってなかったな: 7233600
つづけて二問め。こんどは、典型的な「配るDP」風に書いたつもりだったけど、Inf の大きさが甘くてWA。これ、よくやる。要注意。 あと、dp 配列を n+k で余分にとっておけば、ループ条件緩和できる。どっちでもいいような気もするけど： 7233978
なるほど 7234407
でも、↓こういうループにした方がよかったかな
// ループ
for (int i = 0; i < N; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
if (j == k) continue;
chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
}
}
}
かんたん、とかいいつつ、例２に助けられた（うかつ）： 7318110
本番では、ひとつだけTLEのまま一時間くらい溶かしてしまったやつ。 グラフの最長経路の長さを求める問題に帰着させる。 あと、循環の検出。なかなか、ちゃんと書けなかった。 7318341
あまり考えずに解説みてしまった。ナップサックだからといって DP ではない。 条件を用いれば全探索可能になる。高速化のために累積和。 そういえば、いちど、w の int あふれで WA だした。きをつけよう： 7322752
なるほど、DP って強力なんですね。解説みて、上の桁（左端）からやってくのかというのが意外だったけど、なるほどきれいだ。 7339526
寝る前になんかやるかとおもて、Easy でレコメンドされたやつ。Easy ってのがヒントになっちゃったかもしれん。 7342360
限られた質問回数で木の直径（二点間の距離の最大値）を求める： 7345767
N や K の大きさから、探索めいたことをやっていてはダメだなぁとは思いつつ、ちゃんと腰をすえて考えられなかった。 （つぎのEを考えてみたり、Fを考えてみたりと注意を分散させてしまった） 7420982
Difficulty 983, Solve Provability 51% でレコメンドされたやつ。普通にとけた。 7424622
Difficulty = 1104, Solve Probability = 44% でレコメンドされたもの。 解けそうな気がしたし、解きたかったのだけど WA がひとつ取れなくて。 座標 (Cx, Cy) の候補の数が１万程度なので、全探索すればいいというのは気づいたんだけど、h が ０ になるケースの扱いを、あんまり考えずに書き始めたのがよくなかった。
解説をみて書き直したものは、だいぶすっきりしている。
Difficulty 1083。回数に制限ないので、すべてのコインを (1, 1) に集めてやればいいじゃんと思いやってみたけど、TLE の嵐。（ついでにWAもなんかでてるけど…）
グリッドをジグザグに一筆書きして一本の帯にしてしまうのは、典型的なのかも。 7434100
実は、はじめて幅優先探索のプログラムを書いた。Queue<T> も初めてつかった。 7434888
解説にあるような方針には自力でたどり着いていたのに、TLE 回避できずにいたもの。 他のひとのACを参考に高速化した。
必要だったのは、ans[n] をあとから数えるんじゃなくて、インクリメンタルに更新していくこと。さらに、C# の場合は、10^5 オーダの Key をもつ Dictionary をひとつで賄うのはダメっぽかったので、d[x][y] と階層化した (Dictionary<int, Dictionary<int, int>>)。C++の場合は、こんなことしなくても間に合っているようだった： 7437758
Difficulty 981, Probability 52%, time 34 mins でレコメンドされたもの。 最初の着想のまま書いてAC、23分： 7445120
Difficulty 1104, 制約が Q >> h, w だったので、こりゃ累積和だなってんでとけた。 全ての数字は d の剰余で分類できるってのが、ミソっちゃみそかな（ってほどでもない）。 23 分： 7448675
Difficulyt = 1152. さほど難しくないかなと思ったものの、解説を読んだ後でも、なかなか正解するプログラムが書けなかった。紙に書いて、落ち着いてコーディングしたらかけたもの。 7451777
敗北。なんか例外の多い「規則性」を見出したつもりで間違えたというのと、\(A_{i-1} > A_1\) のケースでは、べつに \(A_i > 1\) でもいいのを見落とし（勘違い）。 いちおう書いたけど、このように解く感覚をつかんでいない。要復習： 7461064
Difficulty 968. ひとまず A に着目して、書いてみたら TLE. TLE になってみると、そうか、BC に着目して、これが連続するAを「あがって」 いくイメージかと気づいて、しゃくとり的に探索回数減らせると気づいた。気づいたあとも、なんどかTLEになる度高速化したり、 ばぐってWA出したり。自力で解けたけど、最初からスっとこのくらいかけるといいんだな： 7475426
Difficulty 1164. これは、糸口がつかめず（普通にやったらTLEなのはよくわかる）、解説をみた。なるほど。 条件を満たす最小のパラメータを求めるのは難しいが、与えられたパラメータが条件を満たすかどうかは計算できるときには、 こんな風に二分探索する手があるのか。思いつかなかった。
正直いうと、与えられたパラメータが条件を満たすかどうかを簡単に判定できる、ということにも気づけなかったけど。 爆心ダメージがA, それ以外が B （A>B)というのを、すべてにBだけダメージをあたえて、１体だけ（A-B)の「追加ダメージ」 と捉えなおすというちょっとした考え方のコツなど。
あと、二分探索を自分で実装することが少ないので、ぱっと一発でかけなかったりもした： 7479064
プライオリティ・キューが思いつかなかったのは痛恨。 あと、\(2^Y\) で割って切り捨てるのと、2で\(Y\) 回割って都度切り捨てるので違いがでそうな気がして気が散ってしまったのだけど…。Yビット右シフトだと考えたら、1ビットずつやろうが、複数まとめてやろうが一緒なのは直観的にも納得のはずだった。 AC取っておきたかった問題： 7556950
これ、「二分探索の問題らしいな」と思って眺めていても、なかなか、 それで上手くいきそうな確信がもてなかった。慣れと計算量の感覚の両方が必要。 あと、H も S も結構大きいので、計算は long でやる必要があったのを見落としていて、 不要なバグをなんども出してしまった： 7574714
二部マッチは最大フローに帰着できるというのをはじめてやってみた。蟻本の Ford-Fulkerson コードを利用。
もう一つ、最大流でとけるというのでやってみた。最小カットは最大フローと等しいというので、直前につくった Ford-Fulkerson がつかえると思い。
たしかに、使えるんだけど、無向グラフなので AddEdge を二回呼ぶというのでWA連発と、 G = ０ のケースで、ReadIntArray に空行を食わせると Runtime エラーというのに随分はまった。
あと、最終的にログインしてみられるというのを、マークされた人からゴールへのパスで表すというのは、自分では思いつけなかったかな： 7619461
正解はとてもシンプル。いろいろ焦りながら考えていくなかで、 正解のパターンにはたどり着いていたのに、ごちゃごちゃした混乱から抜け出せず 0 完におわってしまった。 あと、一文字ずつ1万文字 Write すると TLE になるらしいというのは意外だったかな： 7644986
一文字ずつ出力するとTLEになるのは、AutoFlushをオフにし、最後にFlushするようにしたら通った： 8145382
他にも、Z-Algorithm でも解けるらしいけど、DP とローリングハッシュで。 DPについては、解説ビデオでは後ろからサーチしていて、ひとまずそれをまねてみた。 が、べつに前から見ていってもよくね？ もうひとつは、ローリングハッシュをつかって、部分文字列同士の比較を \(O(1)\) にしておいた上で、二分探索。それぞれの提出コードは、以下：
結構難しく感じたが、トポロジカルソートの数え上げに bitDP を用いるというのは典型なのかもしれない。あと、また dp 配列が int あふれて WA をやらかした： 7697771
N が小さいので、(p, q) の候補すべてについて、pick 回数をしらべて最小値を答えればよい。 単純にやると \(O(N^4)\) だが間に合う： 7708941
ちょっと難しかったので、まとめてみた
最初に考えたのは、まず１文字選んで \(s_1\) とする。 \(s_i\) が一文字のとき、次の文字が異なれば \(s_{i+1}\) も一文字選ぶ、 同じなら二文字選ぶ。 \(s_i\) が二文字のときは、常につぎの一文字を選らんで \(s_{i+1}\) にするという方法。 …が、これでは、末尾で二文字選べないケースに破綻してしまう。
そこで、バックトラック…なんてやっているとスタックあふれちゃいそうだが、 これは DP でとける： 7794952
※↑のコードは、AC だったけど、|S| = 1 であるような入力でしぬ。
条件にあうよう円環上に並べなおした結果が \(b_1, b_2, \cdots, b_n\) となったとする。 そうすると、\(b_1 = b_n \oplus b_2, b_n = b_{n-1} \oplus b_1\) および、 \(b_i = b_{i-1} \oplus b_{i+1} (1 < i < n)\) が成り立つ。これを用いて、 \(b_1 = b_n \oplus b_2\) の一番最後の項を置き換えていくと、
b_1 = b_n ̟⊕ b_2
= b_n ̟⊕ b_1 ⊕ b_3
= b_n ̟⊕ b_1 ⊕ ... ⊕ b_{n-2} ⊕ b_n
= b_n ̟⊕ b_1 ⊕ ... ⊕ b_{n-2} ⊕ b_{n-1} ⊕ b_1
この両辺に ⊕ b_1 すると、結局 \(b_1 \oplus b_2 \oplus \cdots \oplus b_n = 0\) となる。Yes になるのは、入力された数列を全部 XOR してゼロになるとき： 7799304
嘘回答だった！→ AGC 035 A - XOR Circle の正しい解き方
逆から考えて、i 番目にある数字 i を取り除けるかを確かめればいいというのには気づいたんだけど、全探索の DFS を書いてしまって TLE。解説にあるように、各回で、取り除き得るもっとも大きいものを取り除くしかないことに気づけば計算量が減らせた。なるほど、もうひといき： 7799966
つづきは AtCoder 練習帳２へ
丁寧にかいていたら続かないので、やめた。以下はやめる前の残骸。