SRM 387 300pt: MarblesRegroupingEasy
問題概要
N(<50)個の箱がある。各箱には種類i(0<=i
考えたこと
- とりあえずJokerをどれにするか全探索する方針が見える。
- Jokerを固定したときの移動回数をどうやって求める?
- 1種類しか無いときは基本的に動かさなくてよくて、それ以外の時は全部Jokerに放り込む。
- ただし1種類しかないときも、それと同じ種類の箱が既にある時は移動しなければならない。
- っていうかこれ数は関係ないよね。
- 後は実装するだけなんだけど、妙に読みづらいコードになってしまった。
- 提出したけど自信がない。でも一応大丈夫そうなので再提出はしない。
- 無事通ってた。こういうのもっとスマートに書きたい。
SRM 387 500pt: IntervalSubsets
問題概要
[start, finish](0
考えたこと
- 解き方とかはまだ全然分かってないけど、とりあえず半開区間にデータ構造を変換しよう。ユニークもしなくちゃいけないし。
- 極大と言うのが面倒くさそう。それが無ければDPで行けそうだし。区間の上限100とかもそれっぽい。
- 今考えたら区間の上限100云々は本質ではなかった(座標圧縮でどうせ50*2=100に落ちるんだし)。
- えーと、最初に区間をソートしておいて分割統治法でいけそう?
- でもこれだと、真ん中の区間を選んだときは分割できるけど選ばなかったときに分割もマージも難しい。
- というか、「最後にカバーされているのがどこか」というのが重要なので、やっぱDPが本筋くさい。
- 状態は(今いる座標、最後にカバーされた座標、今覆われているかどうか)で行ける?
- いやいや。最後にカバーされた座標は今いる座標より左側なんだから今覆われているかどうかなんて情報は要らない。
- だいぶ見えてきた。状態を(今いる座標、最後にカバーされた座標)でDP。状態数O(100^2)。
- 状態遷移はO(N)位でいけそう。間に区間が含まれてしまったらその状態はinvalidなので遷移を打ちきる。
- 新たに区間を加えるときは終点までいっきに遷移すれば良い。でもこのときも極大になってるかチェックしなくちゃいけないのでそのチェックはO(N)?ということは全体で遷移の計算量はO(N^2)か。
- 計算量としてはO(MAX_LEN^2 * N^2)で一応間に合いそうではある。
- 区間が含まれるとか毎回書いてると読みづらいので関数にする。
- 書けた。あれ、コンパイル通ってない。uniqueって==を定義しないとダメなのか。
- コンパイル通ったけどサンプル通らない。調べてみたら重複は別々にカウントするらしい。えーーー。
- ユニークの部分消したらサンプル通った。提出したら無事通った。