脳log[20250921]

2025年09月21日 (日) [AtCoder] 精進。昨日あった AtCoder × Engineer Guild オンサイトコンテスト ～集結！高レート人材～予選（ABC424）-E「Cut in Half」。K と X の上限の高さに対処する問題。問題に二等分と書いてあるからじゃないけど二分探索を考えた。何を？ たとえば長さの上限を探索するとしたら……Ai を何回二等分する必要があるかがわかって、何回倍々に本数が増えるかがわかるので、増えた本数の総数が N+K を超えたかどうかで判断できる。ところで、倍々はビットシフトで計算できるけど半分半分を右シフトでやると小数部分が計算できない。右シフトして消えたはずの部分も固定小数点数みたいに保持したらソートできるかなと考えたりもしたけど、答えが小数なのだから半分半分は小数で計算することにした。自分の解答で探索する上限がストレートに長さの上限(小数)ではなくビット長の上限なのは、思考の回り道の名残か。小数を引数にした２の累乗が普通に計算できると知らなかったことも理由にある。■提出 #69507299 (WA×21/AC×15)。時間内の提出は WA だった。ミスが２つある。■提出 #69515602 (WA×2/AC×34)。１つ目のミスを修正したら WA が２つまで減った。差分は何か。倍々に増えていく棒がぎりぎり N+K を超えないボーダーを探索したあと、ちょうど N+K 本になるように長い棒から半分にしていくシミュレーション部分で慎重さを欠いていた。同じ長さの棒について何本まで折るかという判断をせずに全部折るか全部折らないかで判断していた。ちょっとくらい N+K 本を超えてもええやろの精神。あとで X 番目を数えるのだからダメです。■提出 #69515755 (AC)。２つ目のミスを修正したら AC。18 行目に長さ a の棒を半分半分にして倍々になった本数をカウントする処理があるけど、a よりも探索した上限が大きい場合は手を加えずそのままの a を１本計上するのが正しい。ビットシフトで計算する本数にはシフト数が負にならないようにリミットがかけられていたけど、a の値を増やしてしまうかのような逆二分割を防ぐリミットがなかった。こんなんでは D 問題に費やして無駄になった１時間があっても時間内に AC できたかは怪しい。■提出 #69518302 (AC / 2000 ms)。一番最初に考えたプライオリティキューを使ったシミュレーションは K の大きさを見てすぐに捨てたのだけど、実は倍々で増えていく同じ長さの棒をまとめて操作できるので K の大きさはそれほど問題ではなかったのだった。これは 10 分で書けてバグもなかった。しかし実行時間が２秒ピッタリ！ 制限時間は長めの３秒かなと確かめてみたら２秒！ プライオリティキューにソート済みの配列を渡して初期化しているのだけど、これが空のキューに１つずつ追加していくようになっていたら間違いなく TLE だったね。Ruby だと想定解法が通らない通っても記述の違い定数倍の違いでふるいにかけられる最近の AtCoder の制約は今回も精度が高い。高精度で確実に Ruby を締め出してくる。何が想定解法かこの E 問題に関しては知りませんが。■■■F 問題「Adding Chords」。セグメント木だと見かけたので何を乗せるのか考えた。提出 #69576332 (AC / 533 Byte / 812 ms)。使ったのは BIT。線分同士の関係は何が許容されているか。交差はダメ。隣接と包含は OK。１本の線分は円を左右２つの領域に分ける。領域の境界をまたぐように新たな線分を引くことができない。しかし同一領域内に新たな線分を引くことはできる。２本の線分が作る４個の領域の関係は？ 一方が一方を含んでいるか交わらないかのどちらか。BIT で領域のスタックを管理する。新しく線分を引きたいとき、始点と終点の土台が構成を同じくする領域のスタックであれば既存の線分と交差なく線が引ける。領域をどのように表現し重なり合った構成を区別するか。１領域に１ビットを割り当てるとあらゆる重なりが区別できるけど、N ビットは大きすぎる。大きな素数で割った余りを領域の ID とし、(領域 A)+(領域 B) が (領域 C)+(領域 D) とたまたま一致する偶然が起こらないことに期待した。前々回の ABC422-E「Colinear」に関連して「確率的な操作を書いたことがない」と書いたけどあれは嘘だ。ローリングハッシュを２回くらい書いて提出したことがある (z-algorithm が理解できないので必ずロリハになる)。