TopCoder SRM 432 DIV1
SRM初め。
Coding Phase
- 250点問題
- ランプがN行M列に並んでいる。初期状態でランプはそれぞれついてたり消えてたり。「ある列のランプすべてのオンオフを切り替える」という操作をK回繰り返したあと、全てのランプがオンになっている行の数を最大化する問題。
最初かなり難しく考えてしまっていたが、落ち着いて考えられれば簡単。
初期状態が異なる行が、任意回の操作の後に同時に全部オンになることはないので、同じ初期状態の行が一番多いものを探せばよい。Kの偶奇と、その行が全部オンになるために必要な操作の最小値（=初期状態でオフになっている数）がKを超えてはいけないことに気をつけつつ。 - 500点問題
- 文字列が何個か渡されるので、それらをうまく並び替えてつなぐことで、全体を同じ文字はひとかたまりになっている文字列にできるか、という問題。たとえば、["abc", "cd", "cc", "a"] => "aabccccd" みたいに。
渡される文字列は最大50個なので、ナイーブに実装すると最悪["a", "a",…,"a"]というふうに同じ文字だけの文字列がたくさん入力に来た場合、計算量が 50! になってとても無理。
というわけで、単一の文字だけからできているものは他の入力文字列と併合するという最適化を施してから深さ優先全探索しました。がっ、答えは合っているものの大きい入力が来るとやっぱり実行時間オーバー。ううむ。 - 1000点問題
- 問題文を読んだだけ。すごくややこしそうだが、それなりに書けている人はいる。
Challenge Phase
僕の500点問題はちょっと工夫した大きい入力を投げると時間オーバーで落ちるものなんですが、コードが長かったせいか誰からもチャレンジされず。
ということは、みんな向こう見ず突撃チャレンジしてないのかーと思い、他の人の時間オーバーしそうなやつを狙ってみるも失敗。
System-Testing Phase
250は確保。500は落ちた。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Passed System Test | 15:18 | 198.56 |
| 500 | Failed System Test | 48:39 | 0.0 |
| 1000 | Opened | 02:52 | 0.0 |
チャレンジ1回失敗 -25
スコア 173.56 / 534人中291位 / レーティング 1731→1707
チャレンジが失敗した分少し下がったといったところ。前回がちょっと上がり過ぎだったのでまあこんなもんか。
