Quiz
間違った解答
- WA https://atcoder.jp/contests/agc030/submissions/3897783
- 現在地点から離れている木の方に行けばいいのでは？
- 実装も複雑になってしまい、サンプルテストケース3も通らないという結果に
最も離れた木に向かうのではダメだという例
- 前者：左右左左右=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
ノート
- 「累積和がどこに出てくるねん？」の参考になれば。
追記：2020/10/18
- これを読んでもわからんな。ゴメン
- アルメリアさんの記事を読もう！
- （なるほど、切れ目N箇所を全探索して「円を切り開く」）
