SRM498 div1

LayCurseさんとかtsukunoさんが居る部屋。

250

• グラフが条件を満たしているか判定する問題
  • 50^4くらいかかっても大丈夫な筈なんでa,b,c,dを全探索
  • 書いた。50^5になったけど気にしない。

450

• 条件を満たす石の置換はどのくらいあるか？
  • マークされた場所と石の距離を全部調べればいいだけ？
  • 書いた。合わない。よく見るとsx,syが1-originだったので修正してサブミット

1000

• なんか40分くらい時間がある。
  • 条件を満たす飛び方は何通りかという問題。
  • なにも考えずにDPだと800^4くらいかかって死亡
  • どうにかできないか考える。badな奴は後で取り除くとかどうか？
  • そうすると1次元にできて計算量が削減できる！
  • それでも800^3くらいかかってない？
  • 尺取メソッドでオーダーをもう一つ落とせそう。
  • badな奴は包除原理で取り除けそう。
  • 書いた。バグッた。間に合わなかった。

Challenge Phase

• 250で要素数が1の場合、500でオーバーフローくらいしか思いつかん
  • 500を見ていると階乗を500までしか計算していない人がいたので落とす。+50
  • 250でseq[1] - seq[0]ってやってる人がいたけど、手元で試してみたところセグフォにはならないっぽいので見送り

結果

oox 610.97pts 73位 2322→2355。
1000が解けそうで解けなかったのがもったいない。