企業コンのときのブログタイトル、もうちょっと短くしたいが。ABDの3完。今回は調子悪かった。ずっと他のゲームやってて昼寝もしてないという完全に自己責任ぽいやつ。まあ調子出ないのはいつものことかもしれないけど。そこの加えて前回のAGCが楽しかったので今回のARC格（しかもwriterがyutaka1999）もと気合いが入っていた。ワンチャンオンサイトも狙いたい。つうわけで心拍数だけ上がって頭は回らないという状態に。別に力が発揮できなかったわけではないのでいいんだけど（は？）（ちゃんと楽しめた）。
A - Sum of Two Integers
クソムズ。結局愚直を提出したんだけど、愚直を書いて初めてこの問題がわかってきた気がした。もちろんO(1)解がそういう形になりそうなのはすぐにわかるけど、さすがにA問題で証明せずに出すわけにはいかんし。
B - Counting of Trees
やたら難しそうに見えてしまうんだが、（頂点1を根として）距離3の頂点は距離2の頂点の子になるしかないと気づいて解けそうになった。ただ、木には色々な形があるので、同じ考え方で行けるか不安になる。しかしもう少し考えると、形によらず、距離が1小さい頂点のどれかにつなげることになる。掛け算していくだけだ。D_1が0でないときを場合分けして提出。WA。他の頂点が距離0だったらダメじゃん！提出するもまたWA！この問題は（D_1以外）ソートしてもいいので最初ソートを書いてたんだけど必要ないので消したんだった。ソートしてある前提で書いてしまった。書き直してAC。
これはひどい。提出前に軽く見直ししてるけど意味ないな。頭に余裕が全くないのだ。余裕があればほぼミスしないし。最低限の体調管理をして、落ち着いてコンテストに臨めるようにしたい。
C - Swaps
N-2回までという微妙なライン。N-1回までならどんな並べ替えもできてしまう。しばらく考えて何も出てこないので順位表を見てDへ。
それぞれソートしてダメならダメ。1個でも動かないのがあればOK。ABをペアにしてAでソートすれば二分探索で各Bについて何番目のAまで許容できるかわかる。Bをswapする問題だとしてもよい。N-1回でできてN-2回でできないこととは何かを考えるが、ここで「chokudai speedrun」でググる。「N回スワップ」を見る。置換かあ。ちょうどN-1回でできる置換はパリティが決まってるのでは。この辺わかってないんだよな。とか思いながら。その判定も座標圧縮とか必要そうで間に合いそうにない。そもそも、それが判定できたとしてN-3回でできないことがどうしたらわかるのかわからない。といったあたりでタイムアップ。なんもわからん。
D - Shortest Path on a Line
少し考えると、DPでできそうな見た目をしている。その区間内ならコストCで移動できるということで、区間でしかないので（飛び地はないので）移動するならRまで行ってしまうのがいい（手前で降りるメリットはない）。スタート地点から最短距離を更新していけばできそうだ。だが、DPの更新で近いのにコストが大きいという無意味な場所ができてしまうと困る。それでも上手く更新する方法があるのか、それとも無意味な場所をなくす方法があるのか。結局後者をやるしかなさそうで、面倒だけどstd::mapを使った。前後を見て単調性が崩れるなら加えない、みたいな。しかし、途中まで実装して 10, 11, 12, 13, 14, 12 みたいなケースで12から14まで区間削除が高速にできなきゃダメだと気づいた。少し考えて、実装をpriority_queueに変更。コストが最小で最も遠いものから処理していけばよさそうだ。なんかダイクストラ法みたいだと思った。ただ、最初からダイクストラ法をやろうとしても辺の数がクソでかくなってしまうし、やっぱ動的にやっていくしかないのかなと。その辺は違いがよくわかっておらず、ACを取ることを優先した。ちゃんと書けて一発AC。
（解説PDFを見て）これはきれいだ！ダイクストラ法が使える。そもそも、この問題の本質（？）は「M個の区間を各定数回しか使わずにDPすること」（N回使っていいなら簡単）だと思っていて、それを実現するために色々考えてた。こうやって同じ区間のLに合流させるのねえ。これはきれいだ。自分の解法もちゃんとしたものだろうけど、こういう向きも思いつきたいね。
E - Non-triangular Triplets
あんまやってないけどこれやばそうだな。「小さいほうから貪欲」とかでいいなら簡単にできてしまう。サンプルもあからさまだし、可能なやつはどういう取り方をするんだろう。あとでもうちょっと実験とかしたい。
