ABC115 あと8分あればD解けてた・・・

beta.atcoder.jp

  • Cまでは一瞬で解ける
  • D問題
    • ハンバーガーの問題
  • ナイーブに生成すると250層に達する
    • long longには収まるが、再帰的に解けそう
  • ラスト2分でサンプル3が通り「できた!」と提出
  • 最後の4テストでWA

タイムアップ後

  • 簡単な例でテストを足してみると、間違う場合が再現できた
  • 再現できれば直せる
  • 直して提出、AC

解法

  • LVごとの層数、パティ数は事前にLV50まで求めておく
    • intではなくlong long
  • 対称性から「半分以上食べる場合」は「半分未満食べる場合」から求まる
  • 半分未満食べる場合、LVを1つ下げた問題に帰着する
  • 再帰的に関数を書けば解ける

順位

  • 2000人くらい参加
  • 600点/1000で950くらい。中間・・・
  • Dを解けていたら680位くらい
    • レートも上がっていただろう
  • レート 1061 -> 1037 落ちた・・・
    • しかし惜しかった。善戦した感はある。上達を感じる

参加しているのは学生が多い

  • 上位しか見ていないけど、東京大、東工大など
  • 年代は1990s, 2000sまでいる
  • 初心者しか参加していないと思ったが、上位はオレンジの人たちが沢山
  • タイムアタック的に楽しんでいるのだろう
    • 1位は9分でAからDまで解いていた
  • 私はCまでで17分
    • 手の速さに差がある
    • Dは分析までに時間もかかった。9分ってすごい

学び

  • 対称性により場合分けを単純化できた。バグも減る