2022-09-01 ABC263 の E を解いた
LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263) の E を解いた。
- E - Sugoroku 3
https://atcoder.jp/contests/abc263/tasks/abc263_e
- 提出: https://atcoder.jp/contests/abc263/submissions/34492207
- 解説 AC
- 本番でも解けず
- こういう場合に後ろから考えるのは分かる
- また DP なのも分かる
- とりあえず求めたいものを DP に入れて
DP[N] = 0
からはじまってDP[1]
が答えになるのは分かる - あとは式を書いて変形・整理すると TLE だが解ける
- AC するためにはあとは区間の和が高速に求められれば間に合うことが見える
- DP で貰う DP にして区間の和や最大値などを累積和やセグメント木などと組み合わせて高速化するのはよくある形
- 今回は累積和と DP で解いた
- 式を書いて変形・整理するところができなかった (うーん……)
今日のコミット。