ABC218

ABCDEGを解いて、なんとか6完。CDEに同じくらいずつの時間をかけ、残りの1時間でFGをがっつりやってGだけ解けた。

A - Weather Forecast

nから1引いたうえで s[n] == 'o' で判定。早解きに成功。

B - qwerty

順番に出力していくだけ。早解きに成功。

C - Shapes

!?全探索とはいえCでここまで面倒なことさせるか(更に90度回転はけっこうむずい)。で、90度回転させながら4回ループまで書いて気づく。全探索では間に合わない。200の4乗はダメ(実際は間に合うかもしれないけど)。3乗に落とすなら図形の一番上の位置を調べるか。一番左も求めれば2乗に落ちるか。そもそも一番上/左とかは実装が面倒なんで、'#'のときに座標を上書き記録するのを全部やれば一番下の中で一番右の位置がわかる。あとはそれだけずらして比較だが、ここの実装もかなり力が問われる(最初から恐れていたパート)。プラスマイナス、どっちにずれるかわからない。'#'性が一致するかを見る。TはそのままN*Nを見るとして、Sは「ずらしてN*Nの範囲内かつ'#'」というbool値にして一致するか見る。最近こういうのもちゃんと短時間で書けるようになってきた。とはいえ14分弱かかってるけど。実装は仕方ないとして、考察にけっこう時間かかってるよなあ。

D - Rectangles

これTwitterで見た気がするけどまるっきりスルーしてたなあ。x座標が同じものとy座標が同じものを集めて?それだと1個当たり2乗になってしまわないか。座標圧縮すれば定数倍を気にしなくてよくなるけど結局しなかった。けっこう悩んで、左上から右下への対角線を全列挙する方針に落ち着いた。これは長方形と一対一対応しているので、あとはそれぞれ残りの2頂点が存在するか見ればいい。unordered_setにlong longを入れた。TLが4秒なの気づかなかった。

E - Destruction

罰金を払ったとき報酬が減った扱いになるかどうかがわからなくて怖かった。結局それは答えに関係なかったけど、だからいいというわけではないと思う。少し考えると最小全域木は見える。ただ、罰金があるので木になるまで辺を取り除くとは限らないのが難しい。難しいというか、怖かった。全域木(この中からは取り除かない)を一つ固定したとき、そこに含まれなかった辺のうちプラスであるものだけを全て取り除くのが最善。よって、最初に固定する全域木は、コストを max(C_i, 0) としたときの最小全域木とすればよい(マイナスは関係なくて、プラスを全域木の外にたくさん残したい)。解けているけど、なかなか感情的にしっくりこなくて自信が持てなかった。

F - Blocked Roads

Fをがっつり考えて、わからないのでGを読んで、わからないのでFに集中して、わからないのでGへ浮気した。

愚直にBFSすると4乗で間に合わない。辺毎に1乗かけるか、頂点毎に2乗かけるか。スタートとゴール両方からBFSしとくとして、どっちかでは解けると思ったけど、何も見えなかった。

G - Game on Tree 2

要するに根から葉までのパスのうちどれかを選ぶことになる。ただそこからが難しい。DFSしていくにも、分岐でどちらを選ぶかわからないし、中央値の変化の挙動も複雑そうだ。Fを考えているときにふとGの木の絵が目に入り、「結局どの葉を選ぶかで争っているだけだ」と気づき、そこからGに専念した。

根から各葉までのパス上にある数たちの中央値がわかれば、あとはミニマックス法でDFSするだけだ。中央値は、2本のpriority_queueでできると聞いたことがある。それで実装する。均等に入れていく(同じだったら1本目に入れる)。1本目には小さい半分が入っており、そのtop(最大)より2本目のtop(最小)が小さければ入れ替える。ミニマックス部分は、手番が変わる毎に符号を逆にするやつできれいに書ける。コンピュータ将棋の経験が生きる。サンプルが合わず、入れるだけでDFSの中でpopしてなかったことに気づく。入れた処理の逆を書きサンプルが合って提出するが盛大にWA。逆を書けていなかった。STLのpriority_queueはtop以外の要素の削除ができないので、これはダメだ。急いでmultisetに書き換える。multisetからのeraseは昨日のyukicoderでやったのでその経験が生きた。終了6分前になっていたが、どうにかAC。

(追記)ユーザ解説を見て、トライ木を使えば小さい順に並べてk番目の要素が得られると知った。言われてみれば。定数倍はmultisetを使ったものより重い。

H - Red and Blue Lamps

読んだだけ。それにしても簡単そうな見た目をしている。どんな方法で解けるのかわくわくするな。