やっと、ratedコンテストのやり方を思い出した気がする。コンテスト中に、「ああ、AtCoderってこんな感触だったな（集中する感じ、考察する充実感）」と思っていた。パフォーマンスも2000に乗せ、結果も出たことで、だいぶ気が楽になった。今週は、解けなかった問題の復習をぼちぼちやれていて、時間的にはぷよぷよがメインだったけど、まあそういうことをして普通に時間を使えていたので、いけそうな雰囲気はあった。
A - Candy Distribution Again
ソートして小さい順に取るという方針はすぐ見える。問題は、ちょうどa_i個にしないといけないことだ。答えがNでないときは、余ったお菓子を喜ばない子供に押し付けることができるので、お菓子が足りないときもちょうどのときも多いときもこれでいいかなという感じにソースを修正。ソースが冗長になっている感覚はあったが、少し見直して提出、AC。あとから考えると、お菓子の数がちょうど以下なら簡単で、そうでなければN-1なので、簡単だ。
B - Garbage Collector
(k+1)^2というのを見て、最小二乗法みたいに（ていうか分散の式変形みたいな）上手いことできるのかなあと思った。状況がけっこうつかみにくいので、ソースにコメントをどんどん書いていった。考察は紙のノートでやっているが、文章はPCのほうが速く書けるし取り回しも便利だ。まず、どんなトレードオフがあるかを頑張って認識する。ゴミをまとめると、移動距離と捨てるコストで得して、移動コストで損する。捨てるコストの部分がXに依存してる。各ゴミには距離の違いしかないというのを忘れがち。部分点の制約を見るとO(N^2)みたいだが、ゴミを拾う順番の通り数はめちゃくちゃ多いのにどうなってるんだろう。貪欲でいいのに俺だけそれに気づかないとか嫌だなあ、とか思ってた。ただ、一番遠いゴミを最初に拾うとしてよいことには気づいた。行きに拾う意味はないから。さて、例えば1往復で4個のゴミを拾うとき、2個目があることでコストがどれだけ上乗せされるか？2乗の差なので奇数の列が出てくる。単独で拾うなら2*X+2*x_iのコストがかかるが、ついでに拾ってもらうことでX+3*x_iの追加コストになる（と思っていたのだが、実際は2*X+5*x_iとX+5*x_iだった、確認のために部分点を実装したときにサンプルが通らず頑張ってデバッグして気づいた、書いた図が4個の点から成っていたが左端はゴミじゃなくてゴミ箱だった）。3個目以降はその奇数の部分が2ずつ増えていく感じ。2乗だからそういうふうになりそうだと思ったし、計算したらそうなった。これで、単独で運ぶよりいいかどうかの判定はできるが、だから何だ。単独で運ぶよりいいからといって他のゴミとの兼ね合いもあるので手順は何も決まらない。これが解けるなら、ばらばらに取っていくような複雑な手順であるはずがないと思うのだが。
ついでに拾ってもらったときの追加コストが計算できてるのだから、何番目に拾われるかに注目すればいいのでは？そうだ、何番目に拾われるかさえわかれば合計コストが計算できる！何番目を選ぶかには制約があるはず（それこそ貪欲でよくなってしまう）。制約を考えると、k番目よりk+1番目の人（ゴミ）のほうが多いのはダメ、そうじゃなければよい。1番目がいい人は1番目にしてよくて、2番目がいい人がそれより多いなら、1番目か3番目に回ってもらう。特に、3番目は2番目に対してデメリットしかない。ゴミは距離だけなので距離でソートして（入力がソート済みなのでreverseするだけ）遠いのを1番に、近いのを3番に、3番も一杯なら4番に。境界が曖昧で、これも全然解けそうにない。ただ、よく考えると1番目のゴミの数を決めれば全部決まるんだった。遠い順に1番2番としていくだけ。これで部分点はいけそうなので、提出するかはともかく、書いてサンプルを試す。今回はグローバル関数ではなくラムダ式を使った（なんかメモリ使用量が増えるので最近は敬遠していたがきれいに書けるので）。コストを計算する関数を書いたら、あとは1番目のゴミの数を1からNまで全探索するだけ。ここで上述のバグに出くわす。コストを細かく表示させて、1番目のゴミの移動コストを計算に入れてないことに気づいた。単独で運ぶのにもけっこうコストがかかるのね。そこを直すとサンプルが通った。さて、三分探索が現実のこととして迫ってきた。そういえばごく初期の段階で三分探索は頭をよぎっていた（どういう探索をすると思ったのかは覚えていないが）。とりあえず三分探索をしない解法を少し考えてみる。AtCoderならそういう解法がありそうだし、まあ見た目もO(N^2)から落とせそうな気はする。でも差分計算とかしようにもガンガン変わっていくので無理っぽい。じゃあ書くしかない。原理的にはできることなのだ。見た目にこだわらなければ書けない理由がない。とりあえずライブラリから自作のupper_boundを持ってくる。傾きの二分探索というのが記憶にあった。計算量の定数倍は考えず、とにかくシンプルに。f(k + 1) - f(k)が初めて負でなくなる場所を見つける。範囲は1からn。kには1からn-1までの値が入り得る。戻り値は1からnまで。nが返ったときは、ずっと負だった、減り続けていたということだから、f(n)が最小になる。あれ、そのままf(k)が答えでいいんじゃね。なんか超シンプルに書けた。サンプルも通った。正しいように思える。三分探索が使える証明はできてないけど、どう考えても使える。少しソースを確認してから提出、ドキドキ、AC。えー、恐れていた整数三分探索これだけか。はー。
ここ数日は「Median of Medians」をやってて、解説を見て解けそうだと思っているのに全然進まなくて、整数の三分探索もそんな感じで恐れていたけどやればできるんだな。
ただし、三分探索が使えたのは結果オーライなだけ。感覚的に三分探索が使えるに決まっていると思ってもそれが正しくないことはある。感覚が正しくなかったというのはAtCoderでも何回か経験していたはず。
ソースがきれいだったので、Cに行く前にソースを少し見直した。
C - ABland Yard
無向グラフと書いて有向グラフと読んでいた。1時間以上あったけど、気づいたときには残り20分だった。Bを解ききったことについて、難しい問題でありがちな問題文の勘違いをよく1回もせずにできたなと思っていたのだが、Cでそれをやってしまった。900点は解けないと思っていたのでやや集中を欠いていたかもしれない。でもそれはあんまり関係なさそう。
有向グラフだと難しい。文字列を作ることに貢献するところだけを抜き出した部分グラフを考えると、その各頂点はAにもBにも行ける。そういう頂点たちだけで構成されている。と考えて間違いに気づいた。ある頂点がAとして、AAとABのルートがあればいいけど、ABとAAAとAABでもいい。AとB片方にしか行けないような通過点があってもいいのだ。なんか足して1になるイメージで、長さlogMまでの文字列を保持し合併が1になるかを1つの頂点になら計算できる。DP的な工夫をすれば全頂点についてもできるのではないかと考えていた。
無向グラフだとすると異様に簡単そうだ。AからBに行ったとして、そのBからはAに行ける。あとはBに行ければいい。そしてBに行ける必要がある。そう考えると、AABBの繰り返しで（1番目のAと2番目のAは区別した上で）元の位置に戻ってくればOKということになる。なんかDFSを4回やるだけで行けそうなので、時間はないがとりあえず書いてみる。しかしYesとしか出てこない。ああそうか、フラグを4層に持っていたがこれではごちゃまぜになってしまう。ダメだと気づいたときには残り1分だったので終了。
