DDPC本選参加記
参加しました。予選で30位よりもちょっと下くらいの順位だったけど、東京に呼んでいただき、交通費と宿泊費とうまい昼飯を得た。感謝。
B問題
なんか、「あなたは以前にトレーに載せた料理と同じ種類の料理を載せてはならない。」を、「各料理は高々1回しか取らない」ではなく「2回連続で同じ料理を取らない」みたいな意味にとってしまい、死んだ。普通にもうちょっと落ち着けばよかったですね。
ただ、元の問題とそこまでかけ離れていない誤読だったため、サンプルが全部通り、テストケースの大半もACだったので、コーナーケースにハマっていると勘違いしてしまったというのも死んだ原因の一つかもしれない。
嘘コード
http://discovery2016-final.contest.atcoder.jp/submissions/640913
誤読しているのに(おそらく)想定解の「二分探索+後ろから決めていく」というのに辿り着いていて虚しさがある。
ちゃんとしたコード
http://discovery2016-final.contest.atcoder.jp/submissions/642320
解法としては、普通に前から決めていくと貪欲出来ない(料理が消滅していくので頭良く取っていかないといけない)ので、後ろから決めればいいのでは？ということに気付くだけです。ここで、後ろから決めるといってもどこを始点とすればいいのかわからないので、最初に始点を決めつけてやろうという感じになります。始点が決まれば、料理を優先度付きqueueに入れながら貪欲できます。なんとなく始点の位置について二分探索できるので、やればACします。
C問題
帰り道で考えたらいけた。
括弧の列をstackを使いながらエイってやると、いくつかの根つき木からなる森を作れます。森の中のそれぞれの木は独立に決めていいので各木ごとに問題をといて組み合わせをかけ合わせればいいと分かります。(一組の括弧のペア"()"を頂点とみなし、その括弧の中にある他の括弧たちを子とみなせば木になる)
dp[i][hoge+j]:=頂点iを根とする部分木で、(赤の数-青の数)=jとなるような組み合わせ、とする。(jは負にもなるが、適当な定数hogeを足して正にする)
このdpを愚直にやるとO(N^3)だが、マージテクを用いるとO(N^2logN)となりACする。
コード
http://discovery2016-final.contest.atcoder.jp/submissions/641763
マージテクするの人生で2回目くらいな気がする
※追記
O(N^3)に見える木DPが実はO(N^2)みたいなテクっぽいです。camypaperさんありがとうございます・・・
D,E問題
きっと解けないのでまともに読んでない。D問題は頑張ってやろうかなあ
その他
本番こんな感じになってつらかった
