TopCoder SRM 495 - simezi

143.82 / Opened / Unopened

336位
1627->1621

どんどんレートが下がる。
結局才能ない人間がいくら努力したところで無駄なんだよね。ほんと。

部屋に赤がいねえｋｔｋｒｗｗｗ
mkutと一緒の部屋！

m枚のカードがある。表には1〜Nの相違なる数字がひとつ書かれていて、裏は表の数字が素数なら赤、そうでないなら青の色が塗られている。

カードを小さい順に並べ、裏返したときの色の並びが与えられる。
それぞれのカードについて数字が一意に定まるならその数字を、そうでないなら-1を出力せよ。

N≦1000,m≦50

i番目のカードについて、そのカードの数字をjと決め付ける。

1〜jまでの素数の数と合成数の数と、1〜i番目のカードの素数の数と合成数の数が等しい、かつ後ろ側についても等しいならカードの数字は一意と言えるんじゃないか。
ということで実装。

バグバグでサンプル合わない。色々直したんだけどどうも合わない。
前のカードの素数の数と、合成数の数のどっとかが等しい（かつ後ろも同様）ければいいのか。

いや、それでもサンプル通らないな。
あー、赤と青の並び順も考慮しないといけないから単純に数だけ見ちゃだめじゃん！

ということは、1〜j-1までの数字の色の列の中に、1〜i-1番目のカードの列がぴったり収まってて、逆側も同じなら数字jはカードiの候補になる。
最長共通部分列的なことをするのかな。DP?いや、Greedyでおｋ.

全面的に書き直し。書いた。
カードiの候補が複数ある場合最初の数字を出力してる。-1に修正。サンプル全部通った。

提出。時間食いすぎだ。今回も終わった。。。

N個の箱があって、その中のランダムな一つが空箱。
空き箱じゃない箱には他の箱の情報が入っている。
他の箱の情報が入っているかどうかの行列が与えられたとき、
最善の戦略を取って、空き箱を開けずに空き箱を特定できる確率を求めよ。

N≦50

ある箱から直接または間接で情報を得られる箱は一纏めにしてよさそう。
強連結成分分解するとDAGになる。

んーと、要素少ないからSCCはワーシャルフロイドで良くて。
DAGを作ったらどうするんだろう。一番情報が多いとこから順に取って行けばいいのかな。

書いてみる。サンプル合わずに時間切れ。

部屋全体で全く撃墜が起こらない。
rng回だしねえ。

部屋の500が2人落ちてる。Greedyだとダメだったらしい。
自分のは時間内にバグ取れててもダメだったぽい。