TopCoder SRM 527 - simezi

230.63 / 292.09 / Opened
82位 2037 -> 2097

簡単なのにあせってハマった。

n+1個の頂点とn個の辺からなる連結なグラフで、
次数がdの頂点にはscore[d-1]の点数がつく。

グラフ全体の点数は各頂点の点数の和である。
グラフの点数の最大値を求めよ。

n≦50

うげげ。
dpだろうか。

頂点を一つ決めてグラフをそこで切ると、森がいっぱいできる。
んで再帰的に問題といて、うまくつなげる……のだろうか。
つなげられない。

全次数の和って2*nじゃん。
ってことは頂点i個で次数合計jのときのグラフの得点の最大値をdp[i][j]にするようなDPでいいのでは。
書いてみる。サンプル合わない。

しばらくはまる。
初期化ミスってたらしい。直して送信。

'0'と'1'からなる行列が隠されている。
それぞれの行ごとの情報がrowsにより与えられる。
'0','1'はそれぞれの成分が'0','1'であることをあらわし、
'?'は未確定なことをあらわす。

列ごとの情報がcolumnsにより与えられる。
列ごとの情報は、行ごとの情報と同様の形式で与えられるが、順序が入れ替わっていることがある。

元の行列としてありえるもののうち、辞書順で最小のものを求めよ。

行,列≦30

どうみても二部グラフ最大マッチング。
だけど辞書順最小ってどうするんだろう。

1列greedyに決めて、もう一列greedyに決めてってやるのかな？
でもそれだとタイの場合がよくわからなくなる。

あー'?'ごとに'0'を入れてそのつど完全マッチングがあるかどうかを探していけばいいのか。

書いた。
動かない。
再帰でvisitedのフラグ立てるの忘れてる。

直した。答えあわない。
ループまわす回数間違えてる。

あわない。なんでやねん。
しばらくハマる。
行列を全部出力させたりしてみる。

初期化忘れてるだけやん
てかまたかよ。
直した。サンプルあった。計算量も大丈夫、たぶん。送信。

コインを合計でsumになるように作る。
コインの額はvalues[]のどれかから選ぶ。
何通り作れるか。

sum≦10^18
values[i]≦10^18
valuesの要素は50個以下

どうすんだろう。
部分的にメモ化したりするんだろうか。

わからない。

メモ化してなくて計算量まにあってない275がある。
落とそう。
他の人に落とされた。

怪しい275が一つあるけどなにやってるかよくわからないので落とせない。

275,450両方通った。