ABCEの4完。Fを解けたつもりがWAだった。なかなか取り切れないね。嬉しさが得られない。
A - Chinchirorin
ループを使うよりはベタ書きが速いと判断。
B - AtCoder Condominium
不安になるくらい簡単だが、1からNではなく0からN-1でループを書いてサンプル合わず。
C - Friends and Travel costs
これもえらく簡単に見えてその通りの内容なのだが実装が思ったより重かった。友達をAでソートし、到達できる限りお金を管理しながら進む。目的は友達に会うことじゃなくて、可能な限り大きな番号の村まで進むことなのね。
D - Pond
マスの個数64万だし、区画の選び方もそれに近いくらいある。それで中央値。これは不可能でしょ。最小だから何とかなるのかなあ。
(追記)ACした。二分探索は思いついてたけどそうか毎回累積和作れるのか。広さにビビってた。2次元累積和書くの久しぶりだから手間取ってしまった。
E - White Pawn
DEFを並列に考える感じになった。しばらくしてEに注力しACしたがその時点で1時間使っている。
N*2+1というサイズが意味深だが大した意味はなさそう。盤面は大きいが、そもそもM回しか斜めに動けないから、最終的に到達できる範囲をM*2+1マスに絞れる。最初、後ろからシミュレーションできそうだと思って実装したが、通り数じゃなくて種類数なのでこれは上手くできない。Fを考えてから戻ってきて、順方向のシミュレーションに切り替え実装していく。黒ポーンはXでソートしXが同じならYでソートする。1行ずつやっていくイメージ。そこで問題になるのはすぐ左のマスの状況が上書きされているかもしれないということ。直前に処理した黒いポーンの位置と到達可能かどうかを記録しておき、すぐ左のマスが書き換えられていたら記録しておいた情報を使う。
F - Weed
Aはソートしてしまっていい。高さがHの半分以下の草だけ残る。青木君は抜く本数を決めたら貪欲に高いほうから取っていくだけか?いや、反例がある(1 5 6 の3本から1本取るなら1)。まあ取るのは両端だろうと予想し考えていく。一番高いのがi番目であるとき、1回の操作で何番目の草まで残るかは二分探索で計算しておける。DPを使えば距離がわかるし、これで指定区間を残したときの回数がO(1)でわかるようになるか?いや、どこまで残したかによって1回ぶんずれたりしそう。ダブリング(嫌い)か?いや、高さの最大値が半分以下になっていくからK回のシミュレーションが間に合う!最小値はpair
(追記)ああ、普通に間違ってた。1 1 2 4 4 の5本から1本を抜くとき端から取っても3回かかるが2を抜けば2回だ。それっぽいのに飛びついちゃうの酷い。
(追記)解けた。ダイクストラ法を思いついて、高々K本という条件を処理できないことに気づいて困ったが、高橋君の操作は高々30回だから(N+1)*31個の頂点で青木君の抜く本数をコストとし01BFSをすればいい。気になるのはメモリだが、頂点数6Mちょっとなら行けるだろうと思って投げたら249MBだった。