脳log[20250712]

2025年07月12日 (土) [AtCoder] 今日はミラティブ プログラミングコンテスト2025（ABC414）があった。C 問題に殺された。■A 問題 Streamer Takahashi。日をまたぐことはないので単純に比較するだけ。■B 問題 String Too Long。Ruby なのでオーバーフローを気にしなかったけど、ひとつの数字の上限が 60 ビット(+符号ビット)ってやりすぎじゃない？ 100 個足したら 64 ビット超えるよ。■C 問題 Palindromic in Both Bases。全部列挙して積集合を求めるのだと思った。列挙するのが難しかった。いざ列挙できたら実行に時間がかかりすぎだったし最後のサンプルが合わなかった。C 問題に取り組んでいた 55 分がまるまる無駄になった。■D 問題 Transmission Mission。電波強度とは基地局がカバーする幅のことらしい。基地局はどの位置にも置けるので、１つの基地局がカバーする範囲(家から家の距離。重ならない)の総和が答え。基地局が N 個置けるなら答えは０。基地局の数が足りない分だけ１つの基地局が複数の家をカバーすることになる。家ごとに左隣の家との距離を持って、距離が小さい順に左隣の家と基地局を共有する体で距離を強度として答えに計上する。プライオリティキューすらいらない。55 分かけて解けなかった 350 点問題に対してこの 400 点問題は提出まで５分なんですよ。難易度評価どうなってんだ。■E 問題 Count A%B=C。まず愚直解を書いた。b を固定したとき、a が 1 から n の n 通りをとり c は自動的に決まるのだが、b 未満の a から a==c となる組を除外する(ん？ 全部だこれ)。また、c==0 となる b の倍数も a から除外する。これらは排反。そうすると 2..n なる b に関して n-(n/b)-(b-1) を足し合わせたものが答え。定数や１次式のシグマの計算はいいが、n/b の合計を愚直に線形時間で求めることはできない。ABC172-D「Sum of Divisors」の高速化と同じことをする (20200628p01←あんまり覚えてないけど雰囲気で)。提出まで 25 分。■F 問題 Jump Traveling。K が 20 以下という制約がくさい。距離 K の隣接頂点があるなら頂点１から BFS をするだけ。距離 K の頂点集合を得る方法はあるか？ 終了後に愚直にやって TLE を出した (#67561329)。まずはここから。■直径が小さい木なら N 回の DFS が O(N^2) になる。どうしようか。頂点１を根としたときの深さだけでなんとかできる？ ある深さに兄弟がいないときに選択肢を奪われるのがやっかいだし、そうでなくてもよくわからないな。偶奇が合わないと無理っぽい？ これが 625 点問題じゃないのはおかしいでしょ。■■■C 問題。WA のち AC。昨日も今日もバグの元は９行目にあった。昨日サンプルが合わなかったバグは、"11,22,33,44,..." の種となる [0,1] と、"1d1,2d2,3d3,4d4,..." の種となる [d,10] (d=1..9) は用意したけど、"101,202,303,404,..." の種となる [0,10] が用意できていなかったこと。そして今日のバグも９行目にあって、N が９未満のケースで N より大きい回文数をうっかり計上してしまっていた。一日空けて落ち着いて清書してなお間違えるこれが C 問題で 350 点だというなら、相性が悪いとしか言いようがない。棒に当たったと思ってもう忘れました。来週また同じ問題が出ても解けません。■D 問題を二分探索で解く。提出 #67586675 (AC)。貪欲法では間違えないけど二分探索だと間違いやすいのは３つ以上の家と家が等距離にある場合だと思う。ある距離を境にして家と家を同じ基地局でカバーするかしないかを分けるとするじゃない。家が等間隔に配置されていると、必要な基地局の数が M より多いと思った次の瞬間には M より少なくなるという状況が起こりうる。同じ距離だけ離れているけど、基地局がいくつか余っているのでそのうちのいくつかだけ個別に基地局を割り当てますよ、という状況が起こりうる。貪欲法だと基地局の数をベースに答えを求めるので間違えないけど、二分探索だと距離をベースに基地局を数えるので、同じ距離だけ離れてるけど基地局を分けたり共通化したりと扱いを変えてちょうど M 個の基地局を使い切らなければいけない、というところに難しさが生じる。自分の提出では４行目で距離を N 倍して N 未満の添字を加えることですべての距離を区別可能にしてから二分探索をしている。そして総和を求めるときには N で割ったものを足す。たいへんですよ。未満と以下を間違えて一度 WA も出したし (#67586560)。判定関数はこちらのツイートと同じはず。「岩井星人さん「@4C3pfotQDj26958 ありがとうございます！ 座標の左から見ていって、「幅X以内であれば一つの電波塔で賄う」を決めていって、電波塔の個数がM以上ならXを大きくするってやってました」」 自分のは左から見ていく代わりにソートして二分探索をしてるけどそれは単なる効率の違いなので……と思ったけど、logX と logN の違いだけで効率もほぼ同じ？■二分探索がダメな例としてこういうリプがついている。「hibitさん「@yiwiy9 6 3／1 4 5 8 11 12 正しくは 5 になりますが、恐らく最小値の二分探索だと 7 になります 正：{1},{4,5,8},{11,12} 誤：{1,4},{5,8},{11,12}」」 「幅X以内であれば一つの電波塔で賄う」の解釈が自分と違うんだよな。前から見ていくと、(1,4)←距離３以下だから同じ基地局、(4,5)←距離１だから同じ基地局、(5,8)←距離３だから同じ、(8,11)←距離３だから同じ、(11,12)←距離１だから同じ、結局「幅３以内であれば一つの電波塔で賄う」ことにすると {1,4,5,8,11,12} になって必要な基地局が１つだけなので条件が緩い。次は０と３の中間である１か２を条件にして二分探索を続けよう、ってならない？ その後幅１と幅２のどちらを条件にしても今度は必要な基地局が {1},{4,5},{8},{11,12} の４つになって使える基地局の数(３)を上回ってしまうので、解は２と３のあいだ！(困る) というのは別の話でありもう書いたこと。