ABC095

README

ABC095過去問感想

• A, B問題は特になし。
• C問題は定数時間で解く方法を選んだ。
• D問題はさっぱりだった。
  • 部分点が設定されている問題は積極的に愚直解を追い求めたい（満点はその改良であることも多そうなので）。
    • 大学入試の数学の小問題が次のメインのヒントになっている感覚に近い気がする。

D.Static Sushi(2020-01-11)

流石に1年も経つとだいぶ簡単になっている。 とはいえ実装量は多めなので、注意深く勧めていく。

とにかく、累積和や累積Maxといったものを効率良く使うことが大事。

通った区間の寿司はすべて食べることを意識して、以下の4つに場合分けするとよい。

1. 時計回りにのみ進む。
2. 反時計回りにのみ進む。
3. 時計回りに進んでから引き返し、反時計回りに進む。
4. 反時計回りに進んでから引き返し、時計回りに進む。

1, 2のケースは累積和を使って簡単に計算できるが、 後半の往復ケースのために、ある寿司の位置に関して、獲得できる正味のカロリーの累積Maxを計算しておく。

この前処理によって、1, 2のケースは O(1) で答えを取得できる （ maxCal[n-1], revMaxCal[n-1] のようなものにアクセスすれば良い）。

また、往復ケースについては、「最初の片方向でどこまで進むか？」という部分を全探索することを考える。 これを固定すると、原点から逆方向にどこまで進むべきかは、 前半で求めた累積Maxを使うことで判断できる。 すなわち、まだ食べられていない寿司までの idx に関して maxCal[idx], revMaxCal[idx] といったものにアクセスすれば、そこに獲得できる正味のカロリーが入っている。