B - Tree Burning (agc030_b)

Quiz

間違った解答

最も離れた木に向かうのではダメだという例

f:id:peroon:20181230025905j:plain

  • 前者:左右左左右=30
  • 後者:左左右左右=34

解答pdfについて例を考えてみた

  • 簡潔に書かれすぎていてイメージできなかったので例で考えた
  • 上記の木の場合、X=2の木、X=4の木、X=13の木と来て、このまま前に進むのかどうかを考える
  • 後方にある木とはX=2の木を指す
  • X=2(左), 4(左), 13(右), 12(右)と進んだ場合の距離は2+2+5+1=10
  • 一方、それならもっといい解がある
  • X=2, 13, 4, 12の順に進めば1+3+2+6=12

反省点

  • 複雑に理解して複雑な実装にはまり込んでいく・・・
  • そういう時は「もっといい解があるのでは?」と1度立ち止まった方がいいかも

翌日 6:56 ACした

  • https://atcoder.jp/contests/agc030/submissions/3898038
  • めっちゃ大変だった
  • サンプルで通って「1度出してみよう。たぶんWAだけど」→通った・・・🙏
  • 最初、ターンしないでそのまま直進した回数を「直進数」として定義して使った
    • (N - 直進数) が累積和をどこまで使うかに効いてくる

テストケース・サンプル2の正解の移動

  • 右右左右左右
  • 距離 = 27

ノート

f:id:peroon:20181230070142j:plain

  • 「累積和がどこに出てくるねん?」の参考になれば。

追記:2020/10/18

  • これを読んでもわからんな。ゴメン
  • アルメリアさんの記事を読もう!