TopCoder SRM 496 - simezi

221.88 / 187.93 / Unopened

0チャレンジ
170位
1621->1691

久しぶりに簡単な回だったのに500遅すぎて死亡。
ほんと実力がゴミだ。

赤4人部屋。

近頃あまりに成績がクズなのでMediumから開けてみることにする。

数直線の座標が整数の点に玉がいくつかおいてある。
それぞれ速さvで数直線の正または負の方向に動いている。

玉がぶつかった場合、速度は変化せずにお互いをすりぬける。

一定時間が経ったあと、玉を数直線上にいくつか追加する。
それぞれの玉の座標が与えられる（玉同士は区別がつかない）とき、元の玉と後の玉の対応関係として考えられる場合の数は何通りか求めよ。

2部グラフの最大マッチング？でも場合の数を数えないといけない。そんなこと出来ただろうか。
ビットDPもnが最大50なので無理。

普通のDPで出来たりするんだろうか……
dp[i][j]に、i番目まででj個対応関係がついたときの場合の数、みたいな。
漸化式はどうなる？
i番目とj番目が対応付けられる時と付けられない時がある。
付けられるときはdp[i][j]+=dp[i-1][k]（0≦k≦j-1）とかになる？？

いやまて、対応が複数の場合があるからこういうDPだとダメな気がする……うーん。
dp[i][j]でiがjにつながってi-1まではj-1までのどっかにつながるとか。
いやだから、i-1までの玉の対応関係がjを飛び越える場合があるからダメなんだって。

グラフの特殊性を利用できないか。
そもそも対応関係がかぶりうるのは二つだけ。

……ここまできて時間が残り25分くらいに。もうだめだ、Easy解こう。

（Easy解いてきた）
あと15分で解けるかしら。

元の玉ひとつにつき対応可能な後の玉は最大二つ。
逆に、後の玉ひとつに対応する前の玉も高々二つ。
しかも、対応関係をグラフにしたとき、グラフにループはない。

対応関係が独立してるとこは分けて考えて掛け算して良い。
対応関係がつながってるとこをそれぞれ抜き出して、
前の玉L個、後の玉R個とかだったら？

L=Rの場合とR=L+1の場合がある。
前者のときの対応のさせ方は1通り、後者の場合一個対応がつかないのを決めればいいからR通り。

解けた！
急いで実装。サンプル合った。
何回か見直して送信。残り5分。危ない。

nxmのグリッドの各マスが'.'または'R'または'B'または'G'である。
最初全部のマスは'.'で、与えられた状態になるよう線を描く。

Xx1の縦の線はBの色でのみ描けて、1xXの横の線はRの色でのみ描ける。
1x1の線はどちらの色でも描ける。

縦の線と横の線が重なるとそのグリッドはGの色になる。
与えられた状態の線を描くのにかかる最小の手数を求めよ。

n,m≦50.

Greedyでおｋ.って久しぶりにずいぶん簡単な250だ。
書いてみる。バグった。添え字とか括弧のつけ方とか間違ってる。
直した。また添え字間違ってる。直した。

サンプル合った。よく確認して提出。

500の方針がみんなと違うぽくて不安になる。一人同じ人がいた。
250とかさすがに落とせそうなのがない。

二つとも通って一安心。
部屋で250落ちてる人が二人もいる。そんなばかな。