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 問題に繋がる問題だった。
単位が 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 問題。単に雲の番号を足し合わせたものを状態として持っておけば良い。ハッシュ値はいらない。重なっている層数をあわせて管理しておき、雲が１枚だけのときにだけ雲の番号の和を参照するのだから、雲１＋雲２が雲３と判別不可能だろうと関係ない。……ということが復習を終えた段階でもわからないんだなあ。\1,\2...)とかぶっているのが気に入らない。それに文字列リテラルのエスケープ文字として \ が消費されてしまうことへの配慮がないのも問題。だから必ずブロックを与えてグローバル変数としての $1,$2... を参照するんだけど、忘れていました。■C 問題 Candy Tribulation。19 分かかった。ずっと手が動かなかった。大きい飴の数を最大化するというからまずは個数のすべてを大きい飴に寄せた。そこから総重量を揃えるために小さい飴に置き換えていく。その刻みは必ず Y-X ずつなので、まずは不可能なケースとして Y-X で割った余りがすべて同じでないといけない。最も個数が少なく従って最も軽い人の総重量に揃えられるのかな？ 個数が多すぎるとできないけども。提出後も半信半疑でジャッジの進捗を見守っていた。WA が出て全く不思議がなかった。■D 問題 Suddenly, A Tempest。大きな海苔を縦または横にスパッと切ってずらす。それを最大で 14 回。2 の 14 乗でもそれほど大きくない。矩形の切断と移動をシミュレートして許されそう。矩形クラスを用意させられているあたりでもう実装が大変なんだけど、まだ後半パートがある。細かく刻まれた矩形の隣接判定と UnionFind がしたい。しかし組み合わせの総当たりは (1<<14)**2/2 > １億3000万なので許されないと思った。刻まれた矩形の１枚１枚は重なっている部分がゼロのはずで、隣接のしかたは右辺と左辺もしくは上辺と下辺が１差で隣接している場合に限定できるので、X(Y) 座標で分類して Y(X) 座標でソートすれば総当たりの２乗ではなくソートの NlogN のオーダーで判定ができると思った。ところが自分は分類だけしてソートも尺取りもしなかったのでオーダーが改善しておらず最悪で ((1<<14)/2)**2 ≒ 6700 万の計算量で危なかったけど、45 ms で余裕だった (#70980315)。ギリギリの計算量で落とす意図はなかったみたい。■E 問題 Clamp。クエリ２の式の意味を理解するのに時間を要した。なるほど上と下をクリップするのねと理解した瞬間に問題名の Clamp が目に入って悔しい思いをした。式を読まずに Clamp の一語ですべてが伝われば早いんだけど、そういう順番での理解はありえないんだろうな。でも苦労してたどりついた結論が問題名に書いてあるっていうね。クエリ２に罠があります。l と r の大小関係に制約がありません。そういうときはクランプするのに min と max をとる順番に応じた定数になる。問題自体はいつもの BIT で和と個数を管理するやつ。お前 F 問題の常連ではなかったか。■F 問題 Candy Redistribution。N の制約が 20 以下と小さいけど何が難しいのかがわかっていません！ たくさんの飴を持っているなら、自分か相手のすくなくとも一方の個数をちょうどにできる。あまりにも多くの飴が足りないなら、複数の人からかきあつめる必要がある。これはどちらも避けられない操作なので差はつかない。差がつくのは余りと不足がぴったり一致している二人のあいだで受け渡しを行うときで、１回の操作で２人が満足する。だからたぶん難しさというのは、たくさん持っている人がうまく分配することで、たとえば X 回の操作で自分を含む X+1 人が満足するケースをどのように実現するかだと思った。まるで見当がつかないので BFS をして経路を復元する方法を書いている途中で時間切れ。BFS のキーはソートして正規化したいけど並べ替えをしてしまうと操作列の復元が難しくなる(不可能ではなさそう)、というところで足踏みをしている。■順位表を見ると 86 分の遅遅５完でも意外に高くて 585 位だった。E 問題を 2294 人が通しているのに対して D 問題を通しているのが 732 人ととても少ない。自分では ABCDE で一番頭を使った C 問題を 4429 人が通しているのはちょっと信じたくない。もっと自分と同じように苦しんでほしかった。■■■D 問題ってもしかしてカットして倍々に増やしていくことってできない？(日曜の朝最初に頭に浮かんだこと) X カットと Y カットがそれぞれ n 回と m 回なら(n+m=N)、(n+1)*(m+1) が精々？ 矩形の数が最大で 64 ？ 総当たりでもなんでもやれば通るんだ？