\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 ？ 総当たりでもなんでもやれば通るんだ？(N-M+1).times (0 から N-M までの繰り返し) から [*0..N-M+1] (0 から N-M+1 までを値とする配列) に書き換えたときに off-by-one エラーを仕込んでしまって合わないサンプルに困ってしまった。デバッグプリントで解決。■C 問題 Truck Driver。しばらくわからなくて目の前に沼が広がって見えた。今日はここまでかと。２つの条件に合う範囲をそれぞれ二分探索で求めて考え合わせる。気がつけばこれだけ。■D 問題 Neighbor Distance。お隣さんがわかれば差分更新できる。SortedSet がないから BIT で管理するんだけど X の値が大きいので座圧が必要。今でこそ座圧なんてやるだけ面倒なだけに見えて制約で手軽にいじめられてるなこのひと手間必要でしたかなんて考えてしまうけど、「座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ」なんて初々しい感想を書いていた時期が自分にもありました。座圧ができれば橙 diff の F 問題「. (Single Dot)」が解けた時期が AtCoder にはありました。WA になった最初の提出まで 24 分かかってるんだけど、実装に取りかかる前に強制うんこ休憩に襲われて急いで E 問題を読んで駆け込んだのだった。なお E 問題のロリハ方針が決まってもまだ出られなかったもよう。WA の原因は番兵が小さすぎたこと。番兵との距離が１しかないならいないはずの番兵との距離を答えに計上して間違える。修正に２分。■E 問題 Shift String。入力が素直に２進数に見えるのでハッシュ値を比較するのもハッシュ値を差分更新するのも自然に行えると思う。マルチテストケースであり問題の見た目から基数に２が選ばれやすいだろうから、ありがちな素数の組に対してハッシュの衝突が狙いやすいと思ったけど、AtCoder で最も有名な２つの素数を使っていても大丈夫だったみたい。■F 問題 Back and Forth Filling。50 分弱残して解けなかった。似た設定でこれより答えやすい問題を見たことがある。自分の左右に最低いくつ最大いくつの数があるかを DP で求めて BIT で区間 add をすれば答えの C 数列が得られると思ったけど、サンプルが合うところまでいかなかった。■コンテスト成績証。737 位、1502 水パフォ。■■■F 問題。昨日はこう書いた。「左右に最低いくつ最大いくつの数があるかを DP で求めて……」。最大でいくつの数が置けるかを管理する必要はないのだった。最低限必ず置かなければいけない数がいくつあるかだけで良かった。前から４変数、後ろから４変数で DP をしていたものを、前から２変数、後ろから２変数に書き換えたらするっと答えが一致した。BIT もいらなかった。変化量の累積和で十分。提出 #70649443 (AC)。■■■@2025-11-11 ABC431 の結果が消えていて、ABC430 の結果は順位が同じまま 1587 パフォに上がっている。何があったんだろ。Array#index に投げるのはケチだから。■C 問題 Odd One Subsequence。数列から(位置が)異なる３つの要素を選ぶ方法。Array#tally で集計して計算する。同じ数字を２つ選ぶ方法は nC2 で、残りの数字の選び方は N-n。■E 問題 Hit and Away。難しいから 425 点になっている D 問題と、E 問題だから 450 点の E 問題。解きやすいのも解いて得するのも明らかに E 問題なので D 問題を読まずに先に E 問題を開いた。最初は危険な頂点を起点にしてじわじわ広げていく陣取り的な操作を考えた。UnionFind かな、重み付き UnionFind かなと考えていって、いつもの UnionFind を書いたりもしたんだけど、詰めていくと、安全な頂点を始点にして始点により区別されるパスに先着２つまで訪問を許す BFS になった。■D 問題 On AtCoder Conference。実数 x で定義されるけど実際に求めるのは M 未満ゼロ以上のすべての整数についての合計。M が大きい。そうすると N 人の人の立っている地点と地点のあいだをすべてひっくるめて処理する必要がある。隣り合った人と人のあいだを始点とする X はどれも同じ値になるので。人と人のあいだと日本語で書くときはいいけど、実際に書く処理ではどちらかを含まない半開区間にする。どちらかっていうか、仲間はずれは区間の右端なのでそれを含まないようにする。A 数列は M を足した２周目を加えて倍加して計算しやすくする。複雑だけど 17 分でサンプルがあったから提出したら TLE×3 (#70444180)。手元でいくつかの種類の最大ケースを作ってみたけど再現できず。たぶんだけど C 人先の人が C-1 人先の人と同じ値のときはもう一人先を見る、という繰り返し処理を毎回律儀にやっていたのが良くなかった。尺取りなんだけど一端を進めたときにもう一端を(添字に C を足して) C 人先にリセットするとそれが手戻りになることがあり重複処理がかさんで TLE になっていたのだと思う。６分で修正して AC (#70446347)。■コンテスト成績証。