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 問題が自然とダブリング解法になったのは、たくさんのクエリに答える必要性からだったと思える。たくさんのスタート地点があり、たくさんのなもりグラフがあるときに、連結成分の形をひとつひとつ調べてはいられない。考えるより高速でシミュレーションを回したい。センサーが車を検知して……」のような記述を読んで、「ほらほら」と俺にはわからない理由で謎の確信を得ている。「センサー」とだけ書かれてるけどそれが何を検出するセンサーなのか気にはならないのですか。センサーに検出できる限界があるとは思わないのですか。ロック板が上がったり下がったりする時間を設定で「いい具合」に調節するという事実が、仕組みの限界や避けられない(けれど最少化しようとしている)落とし穴の存在を示唆しているとは思わないのですか。こんな具合に機械のやることだからという理由にならない理由で人閒より上位に機械を置く人閒が身近にいたことが怖かった。仕組みが想像もできない機械は魔法で動いていると思ってるんだろう。俺もたった今魔法という言葉を、人間業ではないから間違いのないもののたとえとして使っている。実際に魔法を使う人間を知っていれば、その人間の為す他のことと同じ程度に魔法も信用のおけないものになるはずだ。機械も具体的に知れば知るほどありとあらゆる失敗が想定できるのにな。■お前は人閒一般の話にしたがっているが特定の人閒=お前に信用がないってだけなんじゃないの、という突っ込みはあろう。だったら判断力の怪しい盲信的な人閒はいなかったということで、良いですね。AI の御託宣を鵜呑みにして他人の話を聞かない人閒が多数派になる未来は怖いもんね。
言い換えると……」があまりにも親切。それなしでは理解できなかった。時間大丈夫かなと不安に思いながらとりあえず 12 分で出したものは WA だった (TLE はなし)。手元ですぐにダメケースが作成できた。それは異なる Ai が同じ列である場合。再帰関数で実装したので自然と DFS 順に答えが出てくるのだけど、同等の数列を束ねる BFS 的な処理順も必要だった。完全に BFS というわけでもなかった。難しいよー。結局追加で実装に 14 分かけた。合わせて 26 分＋ペナルティ５分。■F 問題 Manhattan Christmas Tree 2。45 度傾けるというあれですか？ 傾け方はよくわかりませんが、見たことのある x+y と x-y のそれぞれに対して最大値を取得するものと最小値を取得するものの２通り、全部で４つのセグメント木を用意して、やってみたらサンプルが合ったので提出して AC。手を動かすだけで 14 分。■G 問題 Colorful Christmas Tree。２乗が許される制約。木 DP でできるんかなというかそれ以外にやりようが思いつかないんだけど、３値の子供の処理順をやりくりするだけでもたいへんなのに、どこに親との辺を取り除く処理を挟むかという可能性まで関わってくると整理しきれない。おてあげ。■自分のすべての提出。手も足も出ない G 問題を前に時間を持て余していたのが先週と同じだったように、順位とパフォーマンスも前回と似たものだった。前回と違う点を探すと、６完最速との順位差が 200 番程度ではなかったということ。なんと６完最速は順位表の２ページ目、38 番にいる。今日は G 問題の崖が一際険しかったと言えそう。F 問題を 1500 人以上が解いているのは先週今週変わらず。■■■匹と頭について。検索すると一筋縄ではいかない。まず伝統的には匹のみが長く使われていた。特に馬と匹の結びつきが強い。しかし頭がある現在は、大型の獣にはもっぱら頭が使われる。しかし対象が小型でも頭が正式に採用されているケースがある。つまりどちらをつかっても間違いではない。現代的な感覚で判断すると頭になるというだけのことだった。■■■F 問題。自分は C++ 用語で言うと２種類のセグメント木クラスをインスタンス化して解いたんだけど、動画やテキストで見かけたのは、コードは１種類だけで保持する値の符号をあれこれして４通りの結果を得るやり方だった。難しすぎると思うんだけど、どういう脳内モデルがあると初手がそれになるんだろう。……と書いてから再度訪れてみたら、答えがまんま書いてあった。「二つの座標 (X,Y) と (x,y) のマンハッタン距離は ∣X−x∣+∣Y−y∣=max((X+Y)−(x+y),(X−Y)−(x−y),(−X+Y)−(−x+y),(−X−Y)−(−x−y)) と表せることが良く知られています。特に難しい理論が必要なわけではなく、絶対値が二つあるのでそれの正負の組みせで展開するとこうなります。」 式を操作していたのね。
1 回目の操作としてあり得る操作の数を求めてください」。要するに、答えに近づく１手であれば何でも良い。無駄な操作でなければ何でも良い。無駄でない操作とは何か。第一感は「交換した結果少なくとも一方が正しい位置に納まる操作」だった。嘘くさいなー。N=3、N=4 で嘘を暴こうとシミュレートしていて思い出したのが、すべての並べ替えは平行して存在する単数または複数の玉突き位置交換ループの足し算だということ。ということは数列を漏れなく玉突きグループに分けたときそれぞれの大きさがわかれば、グループ内で位置を正す操作の選び方は、２個を選ぶ組み合わせの数……だと思って AC だったんだけど、今になってわかっていなかったことがわかってきている。グループ内でどの２個を選んで位置を交換しても必ず正しい位置に近づいてるんですか？ わかりません。こうである必要がある、を答えにしてたまたま AC だったけども、それだけで良かったのかどうかは考えていなかった。■F 問題。提出前に 1+L+R+L×R の式を見て一度だけ因数分解を考えて捨てていたのだけど、他の人の提出を見て (L+1)×(R+1) で表せることに気がついてしまったね。第２案で無駄に -1 をして答えを間違えていたことも、因数分解をしようとして失敗していたことも、とにかく中学生レベルの数学ができないことが露呈している。コンコンコン……入ってますか？(入ってません)■F 問題。通り数の計算式以外にもバグらせていた。処理の昇順と降順が反対だった。原因はたぶんだけど、明るさの表現として「１番明るい」と「明るさが N (最大)」の２通りを混同して区別なく使用していたのだろう。■自分のすべての提出。平均すると１問あたり８分で解いてるんだけど、その短時間でこんなにもバグがてんこもりなことに我がことながらあきれます。■■■E 問題みたいな並べ替えについては過去に散々苦しんだ経験がある。第二回全国統一プログラミング王決定戦予選-C「Swaps」(20191111p01、20200826p01)から始まって ARC120-C「Swaps 2」(20211022p01)、ARC124-D「Yet Another Sorting Problem」(20211125)。Swaps 2 だけ毛色が違うけど他の２問は E 問題に繋がる問題だった。そこで散々数列をこねくり回した経験からひとつの見かたを獲得した。過去の日記でも触れてるけど、「競プロerのための群論 (swapと順列と対称群) - little star's memory」のようなありがたい記事を読んでも全然理解できないし身にもつかないのです。
単位が kg であることに注意してください」と注意があるなんて学校の問題よりなんと親切なことか。小学生は 1000 を掛けるのか 1000 で割るのか迷うんですよ。でもそれだけ。■B 問題 Bird Watching。数と大きさの和がわかれば平均が計算できる。■C 問題 Flapping Takahashi。高橋君が存在しうる下限と上限を更新しながら判定をする。判定条件に一瞬迷ったけど、下限≦上限で間違いではなかった。いつものように
all?、any?、none? といった Array のメソッドで入力を受け取りながら同時に判定をすると入力を受け取り切らなくて次のケースが狂うことに注意した。■D 問題 Clouds。計算量の見積もりができなかったのが敗因。2000×2000 の二重ループも、全体で N に収まるループも許されているけど、それらが組み合わさって 2000×N のループになっていることに気づけなかった。気がついたらやりようはある。雲のひとつひとつにハッシュ値を割り当てて重なり合いを xor で計算するならグリッドを走査するのに伴う雲の足し引きは定数時間の計算になる。提出 #71342582。どこかのブログを読んだ限りではもっとオーソドックスな解法があるなんてことない D 問題だった雰囲気があるけども、グリッドではなく雲の座標を伝っていくようにすると間に合うんですか？■E 問題 Distribute Bunnies。終了後に読んだけどわからなかった。似た問題が ARC-A あたりにあったのは知っている。たくさんの二択。UnionFind だと見かけたので UnionFind で解いた。でも UnionFind でいけるということが見抜けるようになったことを意味しない。カードに関する問題だったと思ったから AtCoder Problems で問題名を検索したら ARC111-B「Reversible Cards」がそうだった。400 点問題。４年半前の自分の提出 #21761198。ストレートに UnionFind ではないけど UnionFind っぽい処理をしている？ 解説によれば連結成分ごとに DFS などで木かどうか判定すれば良いと書いてある。自分の今日の提出 #71357456 が木の判定をしているのかどうか知らないので２つが同じ問題なのかどうかも確かではない。■D 問題。雲が何枚重なっているかをマス目ごとに数えた後で、雲の厚みが１のマスの２次元累積和を作成し、雲ごとに、領域内に厚み１のマス目がいくつあるかを数えるらしい(「ABC434 振り返り - naoya - Obsidian Publish」)。厚み１のマス目の２次元累積和を用意するステップが完全に想定外だった。グリッドを走査するときに同時に１枚だけの雲がどの雲かを特定しようとしていたから TLE になっていた。その段階では枚数だけを数えておけば良かったのだ。２次元累積和を使って A-B-C+D の式で任意の矩形領域の和を得るのなんて簡単だよ。■■■D 問題。雲にハッシュ値を与えて XOR で重ね合わせをしたと書いた。実は最初は足し算と引き算で雲を重ねたり取り除いたりしていて、それでもサンプルが合っていた。なぜ足し算引き算ではなく XOR なのか。たとえば雲をたくさん重ねた状態のビット長がコントロールできないのが不都合なのかと思った。雲のハッシュ値が 40 ビット長だとして 1000 個の雲を足し算で重ねるとざっと 50 ビットがないと状態が保持できない。では雲の最大数が決まっていてビット長が足りているなら足し算で問題ないのだろうか。むしろ状態が 40 ビットを超えると発行済みの雲のハッシュ値(単独)とのかぶりが考えられなくなるのが嬉しいのではないか、と一瞬思ったけど、それなら最初から 50 ビットのハッシュ値を配っておいて XOR で重ね合わせをするのがビットの効率的活用なのかなというところに落ち着いた次第。■D 問題。単に雲の番号を足し合わせたものを状態として持っておけば良い。ハッシュ値はいらない。重なっている層数をあわせて管理しておき、雲が１枚だけのときにだけ雲の番号の和を参照するのだから、雲１＋雲２が雲３と判別不可能だろうと関係ない。……ということが復習を終えた段階でもわからないんだなあ。