SRM484

解ける問題を落とさないようにはなってきたけど、解けない問題が多いのと、解くのが遅いのが困ったものです。

• LayCurse先生と同じ部屋。どきどき。

250: RabbitNumber

• RabbitでTaroでHanako。りんごさんセットなのかうさぎさんセットなのか判断に迷う。
  • どっちでも怖いけど。
• 問題読む。なるほど全探索ゲーですよね。
  • って、え？ high <= 1,000,000,000 ってどういうこと？どうしよう・・・。
• ...
• n が大きくても S(n) ってそんなに大きくならないよね。
  • そんな大きなRabbitNumberって存在しないんじゃないの？
• 1,000,000 超えたらRabbitでないと信じて全探索。
  • うさぎさんセットだったら、でかい入力はフェイクではないかと疑うのは基本中の基本です。書いた。
  • Sampleの最後があわない。
  • え、ああ、うん、あってないね。どうしよう。
    • 大きなRabbitNumberは 100... の形に限られると信じて特別扱い？
      • あってる気もするけど違う気もする。
• ...
• せっかく全探索書いたんだから、手元で全部計算して埋め込んでしまおうか。
  • 適当に書いたところをちょっとだけ最適化して。実行っと。
    • さすがに時間かかるなぁ。
• あれ？実行結果見てみると、RabbitNumberって0,1,2,3しか含んでない？
  • これが正しいと信じて全探索すると間に合いそうだけど、いくらなんでも反例あるだろ常識的に考えて。
• ...
• ...ぐぬぬ。
• 全探索終わんないし、とりあえず書くだけ書いてみるか。
• 書けた。全生成するときにleading zeroesを除いてなくてしばらくバグってた。
  • Sampleは通る。愚直な全探索はまだ2億ぐらいまでしか進んでない。
    • とりあえず、0,1,2,3以外を含んだRabbitNumberが見つかってないかチェック。大丈夫っぽい。
• えぇい、Submitしてしまえ。

550: PuyoPuyo

• 残り30分。だというのに部屋で誰も出してない。
  • 無理ゲーの予感！
• ちょっと考えてどうにもならなかったのでスルー。

950: NumberMagic

• 何人か出してるけど、Division Summary見るとそれほど多くない。
  • やっぱり無理ゲーの予感。
• がりがり手計算するだけの問題に見えるけどよく分からない。
• そっと問題を閉じたのでした。
• 250でもテストするか・・・。

Challenge Phase

• 950を狙うか250を狙うか。250にしよう。
  • あれ、みんな0,1,2,3でやってる・・・。なんでみんなすぐに気付くの？
  • 境界値とかオーバーフローとかを狙おうとしたけど、それはsampleにあったんだった。sample親切。

Result

• oxx +0.0 115.86
• 1697 -> 1669
  • 思ったより下がらなかった。1撃墜でもしていれば上がってたのかも。