TopCoder SRM 427 DIV1
今日は通院のため有休を取っていたので、平日午前のSRM参加。ちょっといけない気分。
Coding Phase
- 250点問題
- ある惑星の公転周期と自転周期が与えられて、閏年の周期は何年かを答える問題。
最大入力が10億なのに最初ループで一つづつ調べるコードを書こうとしてしまった。あほだ。冷静に考えると、公転周期と自転周期の最小公倍数を出せば良いだけの問題でした。 - 600点問題
- 原点からスタートして、上・右・下・左・上…の順番に、ある規則で決められた距離を進んでいく。最終到達地点はどこか。
進む回数は最大10億なので、brute-forceは無理。進む距離の変化はループすることを利用して、まとめて計算できます。これ600点になるほどの問題じゃないような…。ただ、「ループに入る前に何回かループの一部にならない変化を経由する」という可能性を見落としていて、システムテスト落ちてしまいました。 - 900点問題
- 整数の集合が与えられる。それらを一列に並べるとき、隣り合ったもの同士の差が、与えられた数の倍数にならないようにする方法は何通りあるか。
適当にメモ化して数えるコードを書いてみたんですが、大きな入力では2秒を超えてしまう。やっぱりHard問題は単純なメモ化みたいなんじゃ無理だなぁ。
Challenge Phase
600のコードは複雑でちょっと読めない、250点のほうを見ていく。
ループで調べている人を見つけたので、大きな入力を投げてTLEに。初のチャレンジ成功、やったね。
System-Testing Phase
600落ちた。周囲も落ちてる人多い。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Passed System Test | 11:04 | 218.68 |
| 600 | Failed System Test | 24:46 | 0.0 |
| 900 | Compiled | 34:49 | 0.0 |
チャレンジ +25pt
スコア 243.68 / 486人中151位 / レーティング 1528→1605
チャレンジの+25が効いたか、やや上昇。2問目が解けるようになるまでもう少しなんだけどなあ…。
