直前まで開催が決まってなかったABCなので不安感はあったが、やってみると今回もクオリティが高くて満喫した。
A - Garden
図まであってなんか難しそうだが、これは知ってる。実装も簡単で40秒AC。最近は、これを30秒に縮めようみたいな気合の入れ方はしてない（unratedであっても単に順位を上げることを考えているのでAでリスクは取らない）。
B - 105
Bは全探索。やるだけ。ループを1から始めてたつもりが0からのままになっててサンプルが通らなかった。やったつもりでやってないの怖いね。将棋の手順前後みたい。
C - To Infinity
いかにもABCのCという感じで好き。しばらく考えて簡単なのはわかったのだが、そこからけっこう時間をかけてしまった。いやほんとこの問題いいね。こんな簡単な感じなのにちょっと手こずる。これぞCだ。
1以外の文字は指数関数的に増えるので最終的に文字列の最初のほうはそれで埋め尽くされる。1だけはその場に残る。文字列の長さをnとしてmin(n, k)まで調べればよさそう。具体例で確認する。例えばkが5のとき、"11112..."みたいな文字列だったらs[4]を見ることになる。1-indexedで問題が与えられるので、この辺かなり複雑で混乱した。あとから考えれば、単に最初のk文字を見るだけなのだが、やはりこの問題を初めて見てるからね。とりあえず、最初のk文字に1以外があるかを判定したが、1以外があったときのことがよくわかってなくて、s[0]を出力したりしてた。サンプルが通らないので気づいて、1以外に出くわしたときその文字を記録するようにする。それでもサンプルは通らない。ああ、上書きしないように見つけた時点でbreakする必要があるんだ（breakせずに楽しようという努力がバグを顕在化させたのでいいことなのか？（こういうギリギリを突いていく努力って必要だと思うんですよ））。提出してちょっと不安だったがAC。提出して不安なようではいけないな。
D - AtCoder Express 2
これもDらしい見た目。Cと違って普通の典型らしく安心感がある（発想力がなくても解けそうに見える）。さて、いもす法っぽい見た目だがちょっと違う。Nが500以下とやけに小さいが、とりあえず普通に考えてみる。ある都市の東にあるLやRの数はO(1)で得られる。問題はそこから「完全に含まれる」区間の数がわかるかということ。無理そうという感覚もあり、未知数4つで式が4本だから求まりそうな感もある。これ行列式0なんじゃねーのと思い、これについて何もわからない自分を悲しく思った。行列式0だとして解空間がどうなるかもイメージできない。方程式を少しいじくって、それによって、もう一つの方針に移る空気ができた。
そのもう一つの方針は、区間をLでソートしてその順に追加して行きながらクエリを処理していくもの。これだとどうも「完全に含む」という逆側を求めることになりそう。それが面倒で後回しにしていたが、まあ求まるのでこれで。ただ、クエリも区間と一緒にソートしなきゃいけない雰囲気もあり、さすがに面倒になった。やりたいけどそれはコンテスト後だ。
ここでようやくNの小ささに注目する。これはO(N^2)のメモリが確保できる。そもそも累積和みたいな感じにすれば、条件を満たす領域は普通に計算できそうだ。なんてこった。実装もけっこう軽い。2次元累積和はすぐに書けるけど、メモリアクセスを連続にして書けることまで思い出せてよかった。2次元なので、簡単に書けるグローバル変数の配列にしたが、サイズを500にするか501にするかで迷ってしまった（0-indexedに直した都市の番号は499までだが、累積和なので500まで使う、だから501以上にする必要がある）。変数名のqが被ってるのに気づいたので慌ててクエリ数のQを大文字に直した。今回は直さなくても通ったけど、経験的にここは何も考えず直すところ。
Dに時間をかけたとはいえ、思ったより順位が低い。やはりNが500というのを後回しにしたのが痛い。ただ、他の方針がダメ/面倒だからこの方針に注力できたというのがあるので、その辺の判断ができないのはまあ単純に実力不足ということになりそう。
