ARC096-D Static Sushi
検索用ワード
円弧上の移動距離 前計算
概要
弧長C(long long サイズ)の円上にいる。最大20万個の、時計回りで距離x[i](long long サイズ)に栄養v[i(max_int サイズ)]カロリーの寿司がある。あなたは距離1歩くごとに1カロリーを消費する。あなたがこのすし屋に入って好きなだけ歩いて食べた時に得られるカロリーの利得の最大値はいくつ？もちろん、何も食べなくてよいし、食べ終わったら始点に戻らず、その時点での利得を見る。
ACするまで
1.昔見たことあるなぁー。どうせ始点から時計or反時計 -> 方向転換して始点まで一回戻って反対側まで行って終わるパターンかな。こういうパターンは先に時計か反時計か、両方探索しておけばどっちから始めるとか気にしなくていい。{一旦始点に引き返しす距離も、両向きのスタートを全探索すれば、簡単に計算できる。
}
2.区間に対する寿司の栄養は累積和でO(1)、1の考察だと寿司が食べられてる区間は連続な始点を通る円弧で、その始点と終点としてありうるのはO(N^2)
}
2.区間に対する寿司の栄養は累積和でO(1)、1の考察だと寿司が食べられてる区間は連続な始点を通る円弧で、その始点と終点としてありうるのはO(N^2)
3.計算量落ちねえなぁーー
4.一回反時計行って、時計周りに方向転換して始点に一回戻ってそのまま時計回りするときのパターンでは、反時計周りのターニングポイントに関しては、事前で計算できそう。
5.best[i] := 反時計でi個目の寿司まで考えた時に、それまでに食べて引き返すときのカロリーの差の最大値は貪欲かつ順番に計算できる。 -> 前計算してオーダー落とす
考察
ほぼACするまでと同じことである。
先に反時計回りをして、のちに時計周りをすることとする。
時計回りで0-idxのi番目の寿司まで泊まるのなら、5.のbestの定義のとおりに、best[i + 1]を反時計回りで得られる最大の利得とする。
事前にbestを計算しておけば、右端を固定するごとに左端の最善がわかる。
先に反時計回りをして、のちに時計周りをすることとする。
時計回りで0-idxのi番目の寿司まで泊まるのなら、5.のbestの定義のとおりに、best[i + 1]を反時計回りで得られる最大の利得とする。
事前にbestを計算しておけば、右端を固定するごとに左端の最善がわかる。
先に時計周りの方も、これと非常に似たことをやればよい。
一言：
これを寿司バイキングといいませんか？
これを寿司バイキングといいませんか？
