JOI2013予選のおはなし
概要
JOI2013の予選。
たぶん4完だと思われるので人権喪失確定。提出ミスをしていたら予選敗退もメニーチャンシズなので震えてる。 昨年度より成績悪いとさすがに落ち込むぽよ。
とりあえず思ったこととか適当に書いておく。
問1
やるだけ。問1にしてはひねってある問題だと思った。
問2
数え上げやるだけ。意外とめんどくさいコードを書いてしまい実力不足。
問3
文字列処理。つらぽよ。配列のサイズを間違えたのでたぶん0点。
問4
典型DP。問3よりやさしめ。
dp[day][c] := day日目にc番目の服を着た時の最大の累積派手さ としておくと各要素についてO(N)で計算できる。 着られない服に関しては -inf とか置いてやると場合分けせずに楽にかけるはず。
問5
座標圧縮するだけ。前日に座標圧縮の問題をすこし解いていたので余裕だった。 N=50と小さいのでいもす法を用いずナイーブに数え上げをしていってもO(N**4)で間にあう。 どうでもいいけど半開区間は楽ですね。
問6
問1-5までわりと簡単だったので問6もすぐ終わるだろ、と思い2時間を費やすも解けず。実力不足。 周囲10マスぐらいの状態を覚えておけばいいのかなーとか思ったけど激遅だしバグるし死。 すぬけ氏のぶろぐを見ると綺麗な解法載ってるし参考になるんじゃないでしょーか。