\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 ？ 総当たりでもなんでもやれば通るんだ？