TopCoder SRM 532 Div1 - simezi

252.86 / Opened / Unopened
0チャレンジ

147位 1960 -> 1995
前回大敗北したので酷い順位なのにレート上昇した……

3つの輪がつながったものがいくつかある。
それぞれの輪は、綺麗であるか、汚れているかであり、
綺麗な輪には美しさが定められている。

輪がつながったものを好きな順に一列につなげる。
そこから「綺麗な輪が連続する部分」を切り出す。

切り出したものの美しさの和の最大値はいくつになるか、求めよ。

3つの輪がつながったものの個数≦50
美しさは0から9の数字

全探索は…無理で、
えーと、それぞれのパーツが左側に来うるか、右側に来うるか、列の間に来うるかで分類して、
左側で最大値のやつ、右側で最大値のやつ、間に来る奴は全部つなげる、
とすればいいのでは。

あ、いや1.1みたいなパーツは左にも右にも使えるのでうまく行かない。
どうするんだろう。

左に来るパーツと右に来るパーツを固定してしまえばよい。
間に来うる奴は貪欲に全部つないでOK。

結構実装めんどい。書いた。
サンプル会わない。

左にも右にも使えない奴.1.みたいなのしかない場合に対応してなかった。
あぶねー、サンプル親切でよかった。
送信。

N個の町があり、1番からN番の番号がついている。
そこに双方向に通行可能な道路M本を引く。

道路は、異なる町A,Bについて|A-B|≦Kのときに引くことができる。
また、全ての道路を引き終えた後で、全ての町から出ている道路の数は偶数でなくてはならない。
同じ町のペアに複数本の道路を引くこともできる。

このとき、道路の引き方は何通りあるか、mod 10^9+7で求めよ。

N,M≦30
K≦8

なんかぱっと見DPぽい感じの問題。
dp[町][道路]とかするんだろうか。

でも奇数本の町を覚えておく必要がある……
dp[町][道路][奇数の町の個数][偶数の町の個数]みたいにやる？
うーんそれだと、同じペアの町同士に道路を複数回引くときに順番が考慮されてしまう。

最後にM!で割るとか……いやいやそんなバカな。
ていうかこれじゃKの制限どうにもできないじゃん。

あれ、K≦8か。
なんかじゃあ直前の都市8つについて偶奇を覚えておけばいいのでは。
dp[町][道路][mask]みたいなかんじ？

更新どうなるんだろう。
新しい都市から道路を引くとき……
なんだこれ2段階にDPしないとダメ？
dp[町][道路][mask]から
次のi+1番目の町から道路の引き方を考えて
dp2[町2][道路][mask]？
これじゃ計算量が1000億とかになって間に合わない。

dp[町][道路][mask][道路をつないだ町]みたいに、道路をどこまでつないだかを最初のDPに組み込めばよい気がする。
書いてみよう。

サンプル合わずにデバッグし続けて終了。

あけてない。

寝てた。

300通ってたらしい。