p(S.size-T.size+1).times.map{...}.min と p (S.size-T.size+1).times.map{...}.min の違い。スペースの有無で解釈が変わる。ふりかえれば今日はスペースが抜ける日だった。入力を受け取るテンプレ N = gets.to_i が N= gets.to_i のようになってしまい離すために戻るということを今日は少なくとも２回やっていた。gets が gest になるみたいなミスはいつものことだけど、スペースが抜けるというのはこれまで例がない。親指のコントロールが失われているのか寒くて指がかじかんでいるのか。■C 問題 1D puyopuyo。前から順番にくっつけて消す。連鎖はない。■D 問題 Tail of Snake。前から順に３つの値を更新していくだけで答えが出るらしい。自分は一度に全部考えることができなかったので、必要な情報を分けて予め準備していた。どういう情報か。ある要素(２番目から N-1 番目までのどれか)を胴体に選ぶとして、それより左で最も効率良く頭と胴を分けたときの最大値が何か。これは２要素の DP でできる。右側についても同様に求めて、左右を足し合わせたときに最大になる要素を選ぶ。サンプルの１と２が合って３だけが合わなかった原因は何か。左側について頭と胴の組み合わせを前計算し、右側については尾と胴の reverse で前計算をしなければいけないところ、尾の数列をどこにも使っていなかった。頭と胴だけで計算してどうしてサンプルの１と２が合うのか、役に立たねーサンプルだ。必須条件の扱いについて。３つの数列の１要素目については頭専用として予め取り除いておいた。N 要素目についても尾専用として取り除いておいた。胴についてはどれを胴にするのがいいかを総当たりするということでクリアしている。■E 問題 Heavy Buckets。ややこしいのでじっくり読んで問題を理解する。バケツリレーが行われる。バケツの行方を追跡したい。たらい回しのルートは決まっている。バケツの位置が即ち水の加算量。問題がわかれば１分もかからずにダブリングだなと見当がつく。固定され循環する未来が先読みできない道理がない。実装には 30 分かかる。１個先、２個先、４個先の位置はどこか。１個移動する、２個移動する、４個移動するあいだに加算される水の量はいくらか。この２つを 30 ビット分前計算した。■F 問題 Sum of Mex。40 分手が動かなかった。考えていたけど、傍目には寝ていたのと同じだった。前にも書いたけど、MEX って性格が悪い。物事を定義するのに否定で定義するんじゃあないよ。ないものは具体的に掴まえられないんですよ。一応しっぽはつかんだ。f 値が N になるのは一直線のグラフだ。1 から k-1 までの k 個の頂点(＋中間に余分があっても良い)がまっすぐ並んでいるとき、両端の２頂点に繋がる頂点の組み合わせが f 値を k にする。ここから考えるのをやめたくなったのは、k より小さい m があって、f 値が m になる頂点の組み合わせを考えるとき、f 値が k だった頂点の組み合わせがまた出てくるよね、というところ。嫌だ。■F 問題。「1 から k-1 までの k 個の頂点(＋中間に余分があっても良い)がまっすぐ並んでいるとき、両端の２頂点に繋がる頂点の組み合わせが f 値を k にする」と書いた。中間の余分の頂点が k と k+1 を含んでいたら f 値を k+2 にしなければいけない。■■■E 問題。類題として２問、ABC179-E「Sequence Sum」と ABC241-E「Putting Candies」が挙げられていた。過去の自分はどうしていたかなと見てみたら、ABC179 は D 問題で撃沈されていて E は D ともども翌日に通していた (提出 #16923150)。ABC241 の方は D をあきらめて E をやっていたらしいが AC は終了 11 分後だった (提出 #29711639)。どちらも解法はサイクルとサイクル長を検出するグラフ解法だった。まだダブリングを知らなかったと見える。ダブリングを最初に覚えたのは LCA を求めたかったとき。それだって LCA を求めるのにダブリングでないといけない理由はないので、オイラーツアーより後だったと記憶している。噂に聞こえるダブリングというものを実装してみるチャンスだと気が付いてやってみたら、最初は BIT やセグメント木や std::set の外側で二分探索のループを回すような、log が二重に付くやり方をしてしまって TLE になって、何かが間違っていると気が付いたのだった。今回の E 問題が自然とダブリング解法になったのは、たくさんのクエリに答える必要性からだったと思える。たくさんのスタート地点があり、たくさんのなもりグラフがあるときに、連結成分の形をひとつひとつ調べてはいられない。考えるより高速でシミュレーションを回したい。