Coder-Strike 2014 – Round 2

A. Data Recovery

min より小さいものや max より大きいものがあると矛盾です.min, max はなければ追加する必要があります.あとはたとえば min をたくさん追加すれば個数が合わせられます.

B. Spyke Chatting

各 chat ごとのメッセージ数を集計しておき,そこから答を求めます.

C. Jeopardy!

選ぶ問題順をスワップする議論で最適解の構造を考えると,regular question を最初に全部とってしまい,その後 auction question を降順に使えばよいと分かります.

D. 2048

一度列の状況が $\ldots, a, b, \ldots$ かつ $a<b$ となったら,この $a$ から左は二度と変化することはないので,ゲームから除外して考えればよいです.

このように除外しておくと,列の状態は常に単調減少列で,値の総和と一意に対応します.状態が $0, 2, 4, \ldots, 2048$ のどれかとして表せて,あとは dp で答えが求まります.

E. Maze 2D

変更クエリがない場合,左から順に $2$ 状態の dp で解けます.これは,min-plus semiring 上の $2\times 2$ 行列の総積という形で答が求まることを意味します.これをセグメント木で持てばよいです.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました