M-SOLUTIONS プロコンオープン 2020

ABCEの4完。難しい問題と実装が重い問題ばかりでつらかった。

A - Kyu in AtCoder

全部200ずつ変化していることを目視で確認。200の倍数でもあるので、単に200で割ればいい。とりあえず200で割っただけのものを出力すると、大小関係が逆なので何かから引く形だとわかる。適当に設定して差をソースに反映させるのでもいいが、1800が1級なので10から引くだろうと推定しサンプルが合ったので提出。まあ、問題文の数字を見ずに自分の知識を信じてもよかったけど、今回はこういう解き方だった。

B - Magic 2

A, B, Cと赤, 緑, 青の対応が不安になる。A, B, Cが小さいのでオーバーフローの心配はない、Kが小さいので全探索できる。よって解けたが、もう少し実装を簡単にできないか。操作は可換だし、緑は赤より大きくなるまで操作する必要がありそこから更に操作するメリットはない(青と緑も同様)。よってそのように操作をシミュレートして、操作回数がK以下か確認すればよい。

C - Marks

状況が飲み込みにくいが、要するに幅Kの区間の積が評点で、N-K+1個の評点の隣同士の大小関係がわかればよい。隣ならK-1個が共通していて、制約を確認すると親切にもA_iは正の数なので、共通してない1個を比較すればよい。

D - Road to Millionaire

あつ森をやってる人有利そうだなあと思いながら解いていた。自分は、おい森とび森をプレイ済みだが、本格的にカブを運用した経験はない。

まず、2日で倍になっても64bit整数には収まることを確認。かなり難しいし、考えた経験がないのでまともにやったらとんでもなく時間がかかる。ということで雑に考えていく。カブを買うときは半端が出る可能性があるけど、売るときは全部ベルにできる。半端の埋め方が難しいかと一瞬思ったが、安いほうを買って損しない。つまり、ベル振りとカブ振りの2通りの最善を持ち更新していけばよさそう。提出してWA。

苦手なタイプの考察と実装で頭が限界になりながら20分以上かけてWA。軽く見直してわからなかったので、すっぱりあきらめた。Dをやり続けるのは楽しくないという状況であり、コンテスト中は楽しむことを優先するのがよい(貴重なコンテスト中の時間を有効に使う、コンテスト後の気分が違う、レーティングも少なくとも大きな損はない)。

(追記)各日全部売ってから買い直しても同じだと気づいていたのに使ってなかった。使えば見通しが立つ。使わないと難しくなり誤ったコードでWAになっていた。下のケースで落ちていた。カブを買ったあと何日か何もせずすごすケースを処理していなかった。そのカブ+半端ベルの価値の比較が、全部売ると簡単にできる。
3
100 101 200

E - M's Solution

Nが小さいので2^N回の全探索ができる。元から鉄道路線があるのが難しそう。意味がとれず「通り」で問題文内を検索したりした(その結果意味がわかった)。少し考えて、鉄道路線は集落を通るものとしていいと予想する。この問題の場合は、一定以上遠くなるとそれより遠くなっても影響が出ないという性質があるので難しいが、色々考えて悪影響はなさそう(証明できなかった)。さて、通りが縦か横かも全探索すると4^Nになってしまう。どちらかだけの探索で済まないか考えるがうまくいかない。ところで、Kを固定したときにN個からK個を選ぶことになるが、これKを0からNまで動かしたときの総和は2^NなのでOK。ということを考えていると、3^Nでやることを思いつく。K毎にやるのではなく、3^Nでまとめてやって、K本の鉄道路線を建設していたらそこを更新するみたいにすればいい。元からある鉄道は最小距離の初期値の計算に使う。N*3^Nなら大丈夫だと思っていたが、実装を進めていくとN^2*3^Nになってしまうことに気づく。とりあえず定数倍改善をしようとするが、そもそもの実装がそこそこ複雑だ。理解を深めることで高速化しようとするが、できない。そこで、定数倍高速化は少し妥協してでも楽な実装で書き切ることを目指した。サンプルが通ったので提出、ジャッジの時間のかかり方が不穏だが、2977msでAC(TLは3秒)。時間がないので仕方なかった。

F - Air Safety

なんか分類できそうだと思う。次に図を描いて、ある飛行機と衝突する飛行機がどう分布しているかを見る。t秒後に衝突する飛行機はななめの正方形の形に分布している。このななめの線を見ると、その線上の飛行機同士が(特定の向きなら)衝突するとわかる。別方向のななめと縦と横も同様だ(ななめと縦が似てるの意外だった)。20万通りくらいしかないのであとは分類して処理するだけ。しかしまとめて処理するのがかなり難しい。vectorを40万*4個持つことになって焦ったが、まあ3秒だし大丈夫でしょ。MLEはやや不安もあるがさすがにO(N)の処理なら大丈夫と信じるしかなかった。std::setのほうがいいということもあるのかなとか思いながら。方向はc['R'] = 0;などとテーブルを作って数値に変換。分類後の処理は、左から見ていってx座標最大のLを保持して出会ったRの座標との差の最小値でいいかな。分類も何とか書けるが、時間はかかったし、分類してからの出会える向きの組み合わせも上手い処理がすぐにはわからない。ということでコンテスト終了。

(追記)こういうstd::unorderd_setにstd::vector乗せる的な処理は全部まとめてソートしちゃえばいいんだよな。