脳log[20250315]

2025年03月15日 (土) [AtCoder] 今日はオムロンプログラミングコンテスト2025（ABC397）があった。■A 問題 Thermometer。２番目の条件を else にするとタイプ数が減る。■B 問題 Ticket Gate Log。WA を出しました。愚直に現在が奇数番目か偶数番目か、１文字足すか足さないか、判定をすれば良い。WA の原因は現在が何番目かを操作前の入力に基づいて判定してしまったこと。文字を足せば偶奇が変わるでしょ。■C 問題 Variety Split Easy。Hash で左右の要素をカウントする。種類数は Hash#size で知る。■D 問題 Cubes。解けなかった。５秒かかる。数が大きくなっていくと、x と y の差が１だとしても N より大きくなるので、これを上限にして x を線形探索、y を二分探索しようとしたが、これが TLE だった。N が 10 の 18 乗以下で、x の探索範囲は 10 の 6 乗以下になるかなと思ったんだけど、実際は 577 メガだった(irb で簡単に計算できる。でもコンテスト中はまず提出しちゃう)。次に x と y の差を線形探索し、x と y を二分探索しようとした。差の探索範囲は N の３乗根以下でいいので、今度こそ 10 の 6 乗のオーダーで探索できるんだけど、そこに二分探索の log が付くと５秒かかるのだった。ところで、Ruby だから気にしてないけど、x^3 と y^3 の差が最大で 60 ビットになるというとき、x (と y)を探索するのって難しいよね。x^3 と y^3 を 64 ビットの範囲に収める方法も、収めていいかもわからない。■E 問題 Path Decomposition of a Tree。WA をいっぱい出した。最初は子を組み合わせて K をいくつか作る DP をするのだと思った。そのうちに K は１個しか作れないと気がついた。終了後に、K を作る方法は２つ以下すべての子を足し合わせるしかないとわかった。K 未満の子が３つ以上あればそれでもう満足なパスは作れない。K 未満の子が２つあってその和が K-1 でないなら、もう満足なパスは作れない。それほどに長さ K のパスを作る条件は厳しい。終了までずっと大きさ K の部分木を作ろうとしていた。パスは一本道。パスは一本道。■F 問題 Variety Split Hard。C 問題が２分割だったのに対してこれは３分割。C 問題同様に２分割しながら、右側の範囲のベストな分割を遅延セグメント木で見つけられるのではないかと考えた(終了後にね。時間内は DE にかかりきりで 550 点問題を読む時間を惜しんだ)。たとえばある値 a がいくつかあって l..r の範囲に分布しているとする。l の右側から r-1 の右側で分割するのなら、分割の左右で a を種類数 1 としてカウントできる。結果は (TLE×13/AC×32) だったから、外してはいないと思う。■D も F も TLE を解消する方法がわからない。E が得点できなかったのは考察が甘く条件を絞りきれなかったせいであり完敗。不満の漏らしようがない。■F 問題。提出 #63857023 (AC / 1949 ms)。制限時間きわっきわで AC。クラスを剥がして演算を埋め込んだ(手動インライン化)。それとセグメント木の初期化をサボらずに O(N) でやった。サボると O(NlogN) になる。全体が O(NlogN) ならサボってもオーダーは変わらないんだけど、定数倍が TLE と AC の分かれ目ならサボってはいけない。残るは D 問題。Ruby で２桁ミリセックで解けるらしいので、純粋に数学力が足りていない。■■■X 拾い読み。「ABC397 E 、K 頂点を K-1 辺で結んだ直鎖を長さ K のパスと呼んでるの違和感あるな」という意見を見かけた。真意はわからないけど、それはパスはパスでも単純パスと呼ぶのではないかという疑問なのではないかと想像した。なんでそう思うかというと、自分もちらっと単純でない(交差のある)パスが答えになることがあるか考えてみて、NK 頂点を長さ K の N 本のパスに分解するのだから、それは単純パスに違いないなとすぐに納得したからだった。単純パスだと限定しているのは文章のその部分ではなく、その他の条件の帰結としてだと思うんだよね。単純パスのことを書いているのかどうかはわからないけど(X の閉鎖性のため前後の文脈を読むことができない)、違和感は自身で解消できるのではないか。■■■精進。D 問題。５秒を２秒以下に抑えた２つのポイント。１つ目は、１から Math.cbrt(N) の範囲で線形探索する x と y の差分だけど、N の偶奇を見れば対象を半分にできる。これで 2.5 秒になる。２つ目は、コンテスト中にはついに突き止められなかった二分探索の上限。x と y の上限を低く見積もりすぎて答えが見つからないということを繰り返していた。式をよく見よう。(y+d)**3-y**3 を展開して整理すれば dyy+ddy+ddd になる。d=1 のとき y が最小になり、これが N を超えないのだから、yy+y+1<=N の範囲で解を探すことになる。N のルートが上限だった。Ruby には上限を指定しない二分探索があるんだけど、これは遅い。上限を指定することで 2.5 秒が 1.7 秒になった。提出 #63960582 (AC / 1678 ms)。２桁ミリセックには遠く及ばないけどね、ちょっとした工夫で Ruby でも十分に間に合う制約でありました。Ruby での他の人の提出を見た。自分のが一番遅い。一番短い人の提出 #63901879 を見ると３乗根の範囲で線形探索をし、上限を指定しない二分探索をしているところは自分の５秒の解答と変わらない。それが 146 ms で済んでしまう理由は、５行目の早期の判定だと思う。線形探索範囲が半分になるどころではない。x と y の差分 d で N が割り切れないならそもそも二分探索を試す必要がない。それは xxx-yyy = (x-y)(xx+yx+yy) = d(xx+yx+yy) = N と因数分解すればわかる。この因数分解はコンテスト中にやっていたけど、xx+yx+yy を解の公式で解くというはおろか、x-y = d であり、N が d で割り切れるということもわかっていなかった。自分は、頭を使って問題を解こうとしていないな。手を動かしてとにかくやってみて運良く正しい答えが出るといいなあ、という態度で問題に当たっている。悲しいことにこれは怠惰故ではなく、頭の使い方を知らないということなのです。考えてるふりしかできない。だから下手の考え～って言われるのです。