最終更新: 2021-06-08T15:27+0900
ABC の４問目で 400 点問題。しかし青diffではある。
時間制限を 10 秒にしてくれたらたぶん通る。しかし実際の制限は２秒であり、３秒ですらない。慈悲はないのか。
Ruby の提出一覧を見ると AC していても軒並み１秒越えであり、処理量がしんどい問題なのは間違いないのだけど、その中にあって１秒を切っている提出もある。ということは、己の考えが足りないのである。ぐぬぬ。
入力を正負ゼロに分けて、正負ゼロの積がそれぞれいくつ作られるかをまず求めた。
負の積が K 個かそれより多いならば、正の数と負の数のペアを考える。ゼロは特に考えることがない。K 番目が正の積の中に含まれているなら、負の数同士のペアと正の数同士のペアを考える。
これで考えるべき組み合わせが多少は減ったつもりになるが、入力次第では何の足しにもならない。本質的に計算量を削減する方法がわからなかった。
それでどうしているか。
K 番目の数を -10^{18} から 10^{18} の範囲で二分探索している。
ペアを、ある数とそれに掛け合わせるソート数列として持っている。K 番目の数の候補となる数が与えられたとき、その数以下の積がいくつ作られるかは、これまたソート数列を二分探索することでわかる。
ペアの数が馬鹿にならない。N (≦2×10^5) のオーダーで存在する。だから「ある数」と「ソート数列」に注目して、ペアをソートされた状態で持っている。そうすると K 番目の数の候補となる数が与えられたとき、かすりもしないペアを予め除外して考えることができる。かすらないとは２通りあって、すべての積がある数以下となるか、すべての積がある数より大きくなるか。全か無か。ここで累積和と、三度目になる二分探索を使っている。
とまあ、こんな感じ。(３つだが三重ではない)二重の二分探索のあいだに、範囲を絞っているとはいえちまちまと順番に数え上げる線形時間の処理が挟まっているのがいただけない。一番重たいケースで 10 秒はがんばった方だと思うよ。知的方面でのがんばりではないけども。
ソート列とソート列の組み合わせでペアを作っているのに、そのときに一方のソート列をばらばらにしてしまっているのが悪いのか？ (短い方を選んでバラすようにはしている)
この回 は「C 問題が解けなくて大爆死した回の ABC」。その後 C 問題を解いて、F 問題も解いたけど、「F 問題が解けたら D と E も解けたつもりでいいんじゃないかな？」と書いたように、F の後でも D と E が解けていなかった。不思議なもので、D 問題は緑埋めをしていた先月に普通に解いていた(提出 #21267825)。緑がほぼ埋まってきて次なるターゲットは水色下位に移ってきている。E 問題 Logs である。解けない緑より解ける水色なのである。
えー、解けました。解けなかったときは何を考えて行き詰まっていたか。
今日の日記のタイトルは「D 問題 Pairs」です。関連は？
これまで二分探索といえばソート済み配列から特定の閾値をまたぐ値を選び出すのに使用してきたのだけど、実はそれだけではなかった。何もない空中から特定の値(解)を見つけ出すのにも利用できるのだった。順序さえ与えられるなら、解が -10^{18} から 10^{18} の範囲に存在すると判っているなら、たったひとつの意味のある値(解)を二分探索してもいいのである。
という気付きが Pairs を解く過程で(まだ解けてないけど)得られていたので、今度はごく素直に、解を決め打ってから最適な切断をすると切断回数の合計が何回になるかという逆算的な解法を発想することができた。そういうことができるとわかっていた。
二分探索を使った解法でかつて最も衝撃を受けたのは Vacant Seat というインタラクティブ問題に対する提出 #2057817 と #2064531 だった。bsearch メソッドから呼び出されるブロックの中でクエリを行っている。いやね、自分も提出 #7970588 の中で二分探索を使って答えを出してるんだけど、そのことと、対象となる具体的なソート列がないまま空中で二分探索を行う、順序はクエリで動的に決定するということの間に、どれだけの隔たりがあることか。
脳みそが不自由だと存在しない制約で思考が枷をはめられてしまうのだなあ。最も基本的なツールといえる二分探索も、まだまだ使いこなせていないのだった。
ところで 350 ms は Ruby で２番目に速い提出なのだけど、どんぐりの背比べである２番目とそれ以降から頭ひとつ抜けて速いのがこの 提出 #15632506 (sushibon さん / 219 ms)。二分探索は行っていない(ソートはしている)。
二分探索というのは人間が考えることを放棄して機械に試行錯誤させる解法なのだけど、人間が頭を使えば無駄なく速く答えを求めることができるのですね。まあ、何をどう考えればいいのかわかりませんけども。
これも空中二分探索。解を決め打ってから考える。もはやおなじみである。
Ruby では唯一３桁 ms に入った(他は４桁)。log１つ分の差だと思う。Nlog^2 と Nlog。単にソートする方のやり方を思いつかなかっただけなんだけど。
同じ青diffでもこちらのほうが Pairs よりわずかに難しいことになっている。
しかしこれは簡単な Pairs ということでいいんではないか？ だって同じように二重の二分探索の真ん中で線形時間の足し合わせを行っていて、TLE にならないんだもん。
概ね 300 ms から 500 ms の間におさまっているから、自分の 1489 ms は最も遅い部類に入る。Pairs を解くヒントが(Pairs の提出一覧はもちろん)ここにもあるのでは？(だったら読むわけにはいかない)
ループの構成は変わらないまま脳筋的努力を重ねた結果、倍近く速くなった。しかし 300 ms にも 500 ms にも及ばない。やっぱり計算量のオーダーを減らす手がどこかにあるのだろう。それがわかれば Pairs が AC できるぞっ。
やったど。246 ms は Ruby では僅差で一番速い。
どこでオーダーが改善できるか。解法の根幹をなす大外の二分探索の log は欠かせない。入力をなめる N もなくせない。なら内部の二分探索を削るしかないのはわかってたんだけど、「log を削らなければいけません」「はい、削りました」ができるなら脳みそはいらないわけで……。
ヒントはこの問題の前に解いた射撃王にあった。log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ……でなんとかなるなら脳みそは(略)
実際のところ、二分探索の代わりに shift/pop を繰り返すようにしただけ。
261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。
言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた。
やったど！ たまたまぶつかった別の問題ばっかり３問片付けてきたけど、とうとう本丸の Pairs をクリアしたぞ！ (提出日時を見ればわかるけど、今日は５月の下旬なのだ。日記とは？)
これもやっぱり Handshake と同じように二分探索の代わりに shift/pop を繰り返すようにした。Pairs は Handshake と違って A 数列の値の上限が 10^9 なので、逆引きインデックスを用意しておく方法は使えなかったのではないかと思う。
ところで、ぎりぎり３桁 ms には入ったけど、759 ms には負けました。配列の操作でなく添字の操作をしているところが効いてるのかな？