ABC325

6完。おとといPCが壊れたけど、データは救出できたのでようやく気持ちが落ち着いてきた(それまでは食欲もなかった)。借りたPCも競プロができる程度には環境整備できて、いいコンディションで臨めた。結果は普通。たまには橙パフォ取れるのがABCじゃなかったか?

A - Takahashi san

名字に" san"を追加する。名前は使わないのがいいね。

B - World Meeting

半端な時間に会議を始めるメリットはないので、長さ24の配列を用意して該当する場所にW_iを足していく。9時から18時まで(半開区間)、世界標準時で何時か求めてそこへ足す。24個のうちの最大値を出力。

ABが実装軽くていいね。

C - Sensors

UnionFindするだけだが、実装方針でやや迷う。4方向を手で書くか、2重ループで9通りをやるか。後者にした。センサがあったらインクリメントして、mergeされたらデクリメントする。枠内チェックしかせずセンサがあるか見てなくてサンプル合わず。

D - Printing Machine

区間を左端の位置でソート、末尾に番兵を入れておく。右端が左のものから使ってよさそうなのでpriority_queue。実装がかなり難しい。左端が同じものをまとめて入れる必要がある。その時刻までに処理できるものはしてあるようにする。次に処理する時刻を持っておき、今の左端の位置より左ならそこまで進めて、あとは次の場所に届かない範囲でpriority_queueから出していく。ここがハチャメチャに難しく、だいぶ時間を使ってから無理だとあきらめた。

Fまで通してから戻ってきた。次に処理する時刻に間に合わないならpop、そうではなくてかつ次の集団が来る場所より前に処理できるならする(このときも当然popする)。そうでないとき、つまり処理できるものが残っていながら次の区間たちを待ってから判断する必要がある場合は、popせずループを抜ける。これを正確に書くのほんとにやばいよ。

E - Our clients, please wait a moment

辺が多いけど普通にダイクストラで間に合いそう。辺の長さがintに収まるとは限らないので注意する。辺が200万あって100ms切るのか。O(N^2)でそういえばできるんだったな。どうやるんだろ。

F - Sensor Optimization Dilemma

i個目の区間まで見てセンサーを使った個数としてありえるものを持つ?さすがに間に合わない。なんかセンサーが2種類なので2次元で考えてしまったが、センサー1をj個使ったときのセンサー2の個数の最小みたいにDPすればいい。100万回の遷移を100回だからまあ間に合う。これも45msでマジこのジャッジ速いな。

G - offence

区間DPはちょっと考えたけど、全部消えるときとoが残るfが残る色々あってなあ。時間がほとんど残ってなかったのであまり考えてないが。