6完2ペナ。早解き回はしょうがないねって言いたいけど、Dのペナは言い訳できない。Cはどうなんだろうなあ。実装がめちゃくちゃ難しいように感じたけどみんなはさっさと通してるし、自分の実力の低さなのか、「しょうがない」の範疇なのか。実力が低いのは間違いないけど、じゃあこれを素早く通してる人がみんなその実力を持っているかというとそうでもないと思うんだよね。
タイピングの精度がわずかずつ落ちていっている。つらい。
23時からおいうリーグがあり、このブログを書くのを一旦切り上げて観戦。リアルタイムで観てよかった。すさまじくクオリティの高い試合が続いていた。
最近、WAになっても、刺さるようなダメージは受けなくなった。むしろ、ブルアカの戦術対抗戦の攻撃で連敗したときのダメージのが大きい（どうでもよくない？？）。
A - Triangular Number
forを使わずに書いて30秒。いいね。
B - No-Divisible Range
3乗なんだけど、それだけでもけっこう難しいのに、最内ループが2個あることで一瞬4乗のようにも感じてしまうやつ。やるだけが重い。自分の実力では実装イメージがすぐにできない。
C - Domino
これは愚直にやってO(N)。それはわかるのだが、実装が見慣れない内容で、短時間で書く力が自分にはない。これは本当に困る。
まず、A_1未満まで倒れる。その範囲の、i + A_i の最大まで倒れる。新たに倒れた範囲の i + A_i の最大まで倒れる。新たに倒れなくなったり全部倒れたら終わり。このループにどういう初期値で入ればいいかが難しい。区間のどっち側がNになったときに抜けるかが難しい。Nを通り過ぎたときに気をつける必要がある。条件を大量に書いて保険をかけた（安全に保険をかけるには実力が必要で、その力はあった）。提出してWAで、iを足すのを忘れていた。普段サンプルに助けられているだけでこれが本当の自分なのだ。
解説見たらめっちゃ短いコード。1個ずつ見るのか。全く思いつかなかった。コンテスト中どうしても最初に解けると確信した方法で固まってしまうのは最近特にある。ただ、終了後も思いつかなかったし、普通に力不足。この考察難度の高さ、はまったときの見慣れない実装、ARC-Aを思わせる。もちろんARCよりか難易度は低いんだけど、自分はその低いところへ行けなかった。まあここまで苦戦したから気分が悪いというだけで、C問題でそういう気分になれたのはラッキーだしとてもいい問題だ。
D - Reachability Query 2
atcoder::scc_graphを使えば、同じ強連結成分内では1個黒ければよくて、トポロジカルソートもされてるから（左から右に並べて）自分と同じかより右に黒があるかわかればいい。fenwick_treeで判定できる。提出してWA。強連結成分分解しても全順序ではない当たり前。SCCに飛びついて嘘解法を提出までしてしまうの、救いようがない。正面から考えると、毎回逆辺DFSで塗り潰して間に合いそう。同じ頂点から大量の辺が出ているときそれを何度も探索するとまずいが、同じ頂点は1回しか探索しないので大丈夫（なかなか確信が持てなかった）。
E - Cover query
区間をsetで管理するやつで解ける。でもやりたくないので座標圧縮して遅延セグ木で。最終的に黒になる区間だけでなく全体[0, N)をセグ木に載せる方針。0とNも入れてsort,unique。これで、長さNのマスたちをO(Q)個に分割できた。遅延セグ木で区間変更するには累積和が必要だが、座標圧縮に使ったvectorがそのままそうなっている。区間和だけでなく区間を表す情報も必要だった。最後、答えはNから引いて求める形になっており、それで気づいたけど逆にすれば楽だった。セグ木で黒のマス数を持つのではなく、白のマス数にすれば最初にマス数を入れてクエリで0に潰すだけなので、区間の情報がなくてもいい。
（追記）競プロに対してやる気が起こらず、区間をsetで管理するライブラリを自分で書かずに他人が作ったものを使って解き直した。プログラミングというのは一度書けば将来に渡って使えるからこそやる気が出るのだが、競プロを長く続けると思えない状態だった。ライブラリがあればACするのはとても簡単だった。
F - Cat exercise
5,3,1,2,4みたいになってると答えが大きくなる。よく考えると、猫が移動するたびに盤面が分割される。左右どちらに行くかで問題を分割できそう。実際、右に行かせたいなら左を全部撤去してしまえばいい（今考えると、全部でもいいけど現在位置のすぐ左だけ撤去でいい）。最大値とその位置をセグ木で求められるようにしておいて、再帰。呼び出しで要素が1減るから、呼び出し回数はO(N)、1回の呼び出しではセグ木がネックになってO(log(N))。
簡単だったなと思って解説見たらO(N)で解けるらしい。確かに550点くらい難しそう。
G - Domino Arrangement
DPで簡単じゃんと思ったら、色毎に区間が指定されていた。同じ色は2個の塊になっている。ということに気づくまでにもかなりの時間がかかった。何もできなくて時間が余ってしまった。2乗のDPくらいは書くべきだったか。
