3完。始まる前は、終わったら「常軌を逸したコーディング速度」のネタツイートしようかなとか考えてたけど、とてもそんな雰囲気じゃない。maroonのARCが空気を変えた。
ARCもカロリーメイトを食べるようになってきた。最初に詰まった段階で食べる感じ。今回だと開始10分とか。
A - Please Sign
問題文が何を言っているのかさっぱりわからない。図を描いて、愚直コードを書く。愚直を書くのは良い。コードを書けば強制的に理解されるし、サンプルで確認もできる。10分くらい経ってもよくわからずふわふわしていたので、つらいけど本腰を入れて考える（は？）。N個のノードがあって、左端を除く各ノードから右へ矢印が出ている（これを理解するのに10分かかってる）。右端のノードへ入ってくる矢印はないので、そこの値は変化しないとわかる。よってそこから出ている矢印の先のノードの変化のうち右端のノードによるものがどんななのかはわかった。これを右からDPみたいに見ていって、プラスとマイナスどっちが大きいかを見える？実装して気づいたが、何段にも重ねることで寄与がめちゃくちゃ大きくなる。足されてるやつに足されると大きい、くらいにしか思ってなくて、段数も考慮すると長さO(N)の多項式みたいのを管理しなければならず計算量がやばい。これは解けないと思いBに行った。ここまでで20分かかっている。なめていた。どうせそのうち解けるだろと。実際には、時間をかければ解けるのかもわからず、貴重な時間も問題の基本的な部分を知るだけで20分使ってしまった。
Bを通して戻ってくると、あーグラフかあ、あー木かあ、となった。なんかプラスとマイナスに分けて考えてたけどそんなの必要ないね。元の左端の値が0次のもので、ここは他の値が干渉してこない。それも含め、木をDFSして深さ毎にA_iを足していくだけ。終わったら後ろから見て最初の非0。
B - Subsegments with Small Sums
しゃくとりで全区間について求めると3乗になり間に合わないが、その様子が似ていることに注目する。貪欲に取っていいので、区切り位置が一度同じになったらその後の区切り位置は全て同じになる。区切り位置はO(N)個しかないから可能性がありそうだ。区切り位置をまたぐ毎に、そこで終わったときのfの値が1増えて、1,2,3,4みたいになる。もう1個手前の区切りからだと1,2,3,4,5になる。これを足すのはきつそうだが、もう少し考えるとそもそも区間の開始地点からその区間へ「連続部分列の個数1の寄与」を持っていると考えることができる。その後、最初の区切りまで来たら、そこから始まるのも前から始まってるやつの区切りになるのも同じことだから、その最初の区切りに託せばいい。つまり、そこが区切り（開始地点含む）になるのが何通りかを（次の区切りへ足すことで）求めていけば、あとはそれに区間数（端までの距離）を掛けるだけ（新たな連続部分列が始まる個数がわかればいい）。
DPではあると思うけど、自分の中ではこういうのDPと呼んでないな。DPだと思ってないから変数名もdpじゃない。DPはブラックボックスって感じ。うまく説明できてない気がする。
（追記）解説のコードを見てよくわかんないので自分なりに。いつもは開始位置を0からN-1まで動かすしゃくとりをしているが、終端位置を1からNまで動かすのでやってみた。その位置で終わる区間たちのfの合計を値として前からDP。現在の位置から左へ貪欲に取った最初の区切り位置の値を使えば、そこより左ならそれぞれ+1だし、そこまでは1ずつなので、結局前の値に区間数を足すだけでいい。けっこうシンプルになるんだね。DPの持ち方もシンプルだ。
C - Not So Consecutive
一転して簡単そう。DPっぽい。現在の位置から2が始まるとき、連続した2は次で終わるか次の次で終わるかの2通り。そこから2以外の数が始まる。愚直に配ると3乗になってしまうので何らかの工夫が必要で、何らかの工夫がありそうだ。各数について、いもす法みたいにした。何か以外の通り数が求まったとして復元できるのか？N*Nに丸を描いて対角線を消す、全部足すとN-1個ずつになるから、N-1で割れば合計が求まる（図はそうなんだけど間違っていた）。N-1で割る！？制約を確認するとN=1のケースがある！必要かわかんないけど場合分けしておく。N=1のとき答えは1。DPするとき何か以外のもの1通りずつから始めるとN-1倍になるので最後に割る。答えを求めるときは、右端の右隣から開始する通り数を考えてできそう。「以外」というのがややこしくて手間取ったけど、落ち着いて考えると、何か以外で始まる通り数をN本のいもす法みたいので動的に求めていき、そこから何かで始まる通り数を求めてまたいもす法のタネを仕込んでという感じに。
自信のないコードを書いてサンプルも全く合わないという状況。DPの初期値を全部1にしていたが、いもすパートで-1するのを忘れていた。Aを使うのを忘れていたが、これはまあよくて、それを実装して開始位置でしか考慮してなかった。例えば3だったら、開始位置の他にその次の位置と次の次の位置も（Aを見て必要なら）禁止しなければならない。これに対応するため、後ろから見て-1とその数以外の数が最後に現れた場所のテーブルを作った。何か以外の合計からただの合計を求めるところ、よく考えたらここに入れる数がN-1通りあるってだけでN-1倍はされていない。何かで終わったのが何通りというだけ。よって単に足すだけで合計が求まり、1以外と言わなかったやつの合計が今回1で始まる通り数だから合計から1以外を引けばいい。現在位置の数を決めたらN-1倍になっている。このタイミングを間違えた。最後、いもす法でマイナスするところの位置をN+1にしようとして（位置Nは答えを求めるのに使うので）、「最後に現れた場所」のやつにN+1を入れてしまい、別の数がAにあってもその前で終わってそこから別の数を始めるパターンはあってマイナスは更にその次のマスの最初にやるので+1するんで、ほんとはN+1ではなくNを入れて位置計算で他のケースも全部まとめて+1するべきだった。かなり時間を食ってしまったが、どうにかAC。
ARCを戦って頭がやばい（疲労で）ので文章がやばい。
D - Add to Make a Permutation
何を何に変えるか色々あるのに25万は無理だろって思ったけど、よく考えるとN個の箱に入ったN個のボールを移動させて各箱1個ずつにするという問題だ。順番は関係ない（Aは例えばソートしてしまっていい）。操作でAの合計のmod Nがどう変わるか見てできないやつを落とす。できそうならとりあえず一番近い空き箱に移動させ、移動距離の分布がMずつになっていればよし。そうじゃないときどうすんだろ。なんか適当にＮ遠い場所にするとかして合わせるとかだけど、移動してないやつを動かすことにするとか移動元と移動先の対応を付け替えるとかありそうでなあ。
