脳log[20250719]

2025年07月19日 (土) [AtCoder] 今日は日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（ABC415）があった。４完緑パフォだけど寝る前に E と F が通ったので気分がいい。どんどんハードルを下げていこうぜ。■A 問題 Unsupported Type。なんで X を最後に与えるのだ。明確な作為を感じる。■B 問題 Pick Two。問題を読みたくありません。# の添字番号を２個ペアにして出力しろという問題だった。読むのに２分、書くのに１分といったところ。■C 問題 Mixture。問題を読みたくありません(※「(読みたく)ないです」は拙く見えるので使いたくないです(←ほら)。意識して避けています。意識しないとうっかり出てきます)。２進数と10進数と指数と 01 文字列が入り乱れて何が何やら。(2^N)*T はやばい大きさだけど状態数が 500000 を超えないというのだからシミュレートする。01 文字列だから２進数として扱おうとしてやばすぎる大きさだと気がついて配列にして、でも配列の添字を２進数の添字(Integer#[])に合わせようと反転したらそれはまったく余計なことで、最後まで混乱しながらの実装だった。提出まで 24 分。■D 問題 Get Many Stickers。値が大きすぎるのでシミュレートはできない。計算でステッカーを数える。交換すると必ず空き瓶が増える(※)。空き瓶の増え方が少ないのを優先して交換を繰り返す。罠があるのかな。空き瓶 10 本を 9 本の瓶コーラと交換できるとして、差し引き１本のマイナスでステッカーが１枚もらえるけど、10 本の元手で 10 枚のステッカーが得られるわけではない。大雑把に計算したあと１回程度愚直に数えるなどした。提出まで 16 分。※日記を書いている今に至るまで問題設定を理解していないことが露呈している。交換しても空き瓶は増えない。瓶が減るだけ。■E 問題 Hungry Takahashi。順方向にシミュレートするとパラメータが２つになるのが困る。ひとつは現在の手持ちのコインで、もうひとつが過去に不足したコインの総数。コンテスト中はやるだけに見えた F 問題に行ってしまったけど、終了後に考えたら逆向きでうまくいけそうだった。いくらあればゴールまで行けるという金額をゴールからスタートまで更新しながら持ち運んでいけばそれがまさしく求める答えになっている。ループの書き方に迷ったのだけど、H*W-1 から 0 までの１重ループがシンプル。ループ変数から行と列と経過日を求めるのは容易。■F 問題 Max Combo。文字の変わり目と連続する数をセグメント木で管理すればいいんじゃないかな。添字からその添字が属する同じ文字が連続する区間を得る方法をバグらせまくって二転三転するうちに時間が終了していた。まさか BIT 上の情報だけでは区間を特定できないと思わなかったんだよなあ(グラフを想像して人間の目では判断できるので、情報の持ち方が下手で不可能なほど難しかったというのが本当のところ。たぶん区間の末尾ではなく区間の先頭を持ち上げるべきだった。そうすれば値が同じ範囲が求める区間になる。なぜそうしなかったのか……)。終了後にランダムテストでバグ取りをしても最初は TLE で、BIT の呼び出し回数を節約したら AC になった。提出 #67766369 (AC / 3233 Byte / 3996 ms)。制限時間は４秒です。BIT とその上位互換であるセグメント木の両方が含まれているのはいかにも無駄なのだけど、BIT の定数倍の軽さがないと通らなかった。BIT で区間の管理をし、セグメント木で連続数の最大を管理している。■F 問題。Ruby から C++ に翻訳したもので AC をとっているこちらの提出 #67766753 (AC / C++ / 912 ms)。セグメント木に６変数を乗せてうまくするとシンプルに解けるらしい。わかりません。文字と連続数と連続数の最大と？ 文字と連続数はセグメントの左右の分がそれぞれ必要？ セグメントの全体が同じ文字の場合の扱いが特例っぽくなりそうだけど、それは連続数とセグメントの幅を見比べたらいいのかな。一応これで６変数だけどまだよくわからない。Ruby で定数倍チャレンジをしながら確かめる。■■■F 問題。やや時間に余裕をもって通りました。提出 #67790188 (AC / 2091 Byte / 3186 ms)。セグメントの全体が１つの文字のときのマージがバグ続きでくじけそうだったけど、昨日見当をつけたことは外してはいなかった。だけどセグメント木のマージをがんばればいける、ということは見えなかったんだよね。６変数のマージでいけると知ってから考えたわけで。■G 問題を読んだ。昨日の D 問題への提出 #67734593 のほぼコピペがこちらの提出 #67791166 (WA×4/AC×36)。これが AC だったらあまりにも報われないので WA で逆に嬉しい。