■ [SRM][本番]SRM438
2009-04-19 25:00-(JST)
システムトラブルで開催が1日延期になりました。
Level | タイトル | 試合中 | あとで | 感想 |
---|---|---|---|---|
DIV1 500 | EndlessStringMachine | 途中 42min | - | recursion。$が1つの場合は単純に実装するだけでOK。 $が2つ以上の場合は、programの先頭が$なので、長さが10^9を超えた時点の文字列について目的の位置を調べればよい。 目的の文字列は置換済みの形から逆向きに再帰させて計算可能そう。 文字列長は高々30数回の置換で10^9を超えるので、sが大きくても大丈夫。 というくらいが残り15分の時点で見えたけど、この残り時間では書き上げられず |
DIV1 300 | UnluckyIntervals | × 27min | - | brute-force + Math。 greedyに追加してたらコーナーケース(整数が1つだけのインターバルがある)の考慮が足りておらず落ちた。 正解は、めぼしいところを全部保持しといて最後にまとめてソートする方法。PriorityQueueでもよい。 前回の250と同じで「計算量に問題なければ全部調べとけ」パターンか |
- Challenge:
- 300のサンプルが、luckySetを前もってソートしてあるやつばかりだったので、きっとソートしてない人がいるはず!
- いなかった
- 300を細かく見ていると、インターバル1の場合を無視している人を発見して撃墜成功
- スコア:50.0
- 順位:162位/531人
- レート:1585->1644
今回は参加者の6割方がスコア0以下だったので、撃墜1つだけでもそれなりに上がりました。