ABC095 D Static Sushi
D
Submission #2398508 - AtCoder Beginner Contest 095
所感
累積和をすぐ思いつけたのは成長を感じる。が、累積和だけでは足りない感
問題概要
円形の長さCのテーブルの上にN個の🍣が置いてあり、🍣iは評価値viを持つ。取ることができる🍣の評価値の総和-総移動距離を最大化する問題。
制約
(正確な制約はAtCoderを確認してほしい)
取った方針
同じ場所を3回通る場合、その経路は短くすることができる(例えば、時計回りにC,A,B,Dの順に点が並んでいるとき、A->B->A->C->Dと移動する場合、A->C->Dとすることができる)ため、方向転換は一度行うのが最適である。
入力値は整数なので、スタート地点からの距離ベースで右回りと左回りで得られるカロリーの累積和を計算し、時計回りの最大値取ってから戻るパターンと反時計回りの最大値取ってから戻るパターンの両方を試し大きい方を選択した。
この方針には二つ誤った点がある。
一つは、Cは1014であるため、O(C)のアルゴリズムではそもそも通らない。
もう一つは、必ずしも時計回りの最大値を取ってから戻るパターンと反時計回りの最大値を取ってから戻るパターンが最適とは限らない。(例:サンプル2)
正しい方針
🍣の数Nが105であり、折り返し地点と退店する地点は必ず🍣がある場所であるので、🍣がある場所のみを考えればよい。
すべての🍣の場所について上記のアルゴリズムを適用することもできるが、必ずしも時計回りの最大値を取ってから戻るパターンと反時計回りの最大値を取ってから戻るパターンが最適とは限らないため、そこの全探索が必要となりO(N2)となり通らない。
そこで、累積和の感覚で「その場所に行くまでに手に入れることができる最大のカロリー」を求める。これを左回りの場合について計算しておくことで、右回りに全探索する際、「🍣を取得してから折り返し、右回りで取得した最後の🍣の一つ隣の🍣までに得られる最大のカロリー」のをO(1)で求めることができる。(この計算に累積和を用いた)
よって、全体ではO(N)で計算でき、満点が得られる。
得られた知見
・制約をちゃんと見る、1014みたいな明らかにヤバい制約の場合はほかの文字についてO(N)にならないか？とか
・円上で同じ場所を3回通る場合は最初の2回を省略できるので最短経路にはなりえない。
・累積和
・累積和の応用、「その場所までの最大値」を記憶しておいて辞書のような使い方をする
解くのに必要な要素
・累積和
・弧上の点(not 端点)からスタートし、与えられた弧上を塗りつぶすときの最短経路
・累積和っぽい最大値の管理
(例:配列aが与えられた時、aのインデックスiまでの最大値をb[i]に格納しておくことで、インデックスiまでの最大値をO(1)で求めることができる(事前計算はO(aの長さ)))
こういうデータ管理の仕方、名前がついてそう
周辺調査によって得られた知見
特になし
