単位が 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 問題。単に雲の番号を足し合わせたものを状態として持っておけば良い。ハッシュ値はいらない。重なっている層数をあわせて管理しておき、雲が１枚だけのときにだけ雲の番号の和を参照するのだから、雲１＋雲２が雲３と判別不可能だろうと関係ない。……ということが復習を終えた段階でもわからないんだなあ。