D - Moving Piece [ABC175]感想

ぐえー1周で得られる得点は正だが一部だけ回ると1周より多く得点を得られる場合を見落としていた n周できるならこれだけ考慮しないといけないのか

• 1周未満移動する
• n周して残り移動する
• n-1周して1周未満移動する

ぐえー1周で得られる得点は正だが一部だけ回ると1周より多く得点を得られる場合を見落としていた

n周できるならこれだけ考慮しないといけないのか
* 1周未満移動する
* n周して残り移動する
* n-1周して1周未満移動する#AtCoder #ABC175Dhttps://t.co/xEMNilYYxS pic.twitter.com/6RjaTOQv9T

— 🍀🟠🔮 (@hotarunx) 2020年8月16日

D - Moving Piece

問題へのリンク

問題概要

円形で周回できる有向グラフがある。 グラフ上でコマを移動させる。 頂点には数が書かれており、その頂点にたどり着いたときその数だけスコアが増える。 好きな場所にコマをおいて1回からK回だけ移動できる。 最大スコアは？

解き方

Kが非常に大きいため、すべての移動をシミュレーションするとTLEしてしまう。 移動は周期性がある。 1周で得られるスコアは同じだから何周もシミュレーションする必要はない。 これを利用して高速化する。

感想

自分の考察が至らなかった。 最大スコアを取る移動方法はいくつかある。 そのすべてを考察しきれなかった。 そのためWAしてしまった。

1周できないとき

できるだけ移動する。 移動中のスコアを調べて最大スコアを更新する。

1周できるとき

1周するのに何回移動しなければならないか調べる。 N周できることにする。

次のいずれかの移動方法が最適。 この移動中のスコアを計算して最大スコアを更新する。

• 途中まで回る
• N周して残りの回数だけ移動する
• N-1周して途中まで回る

途中まで回るのが最適なケース。

3 7
2 3 1
100 1 -999

N周して残りの回数だけ移動するのが最適なケース。

3 7
2 3 1
100 -99 0

N-1周して途中まで回るのが最適なケース。

3 7
2 3 1
0 100 -99

実装の注意

実装では0回移動時のスコアは0としているだろう。 しかし1回は移動しなければならず、さらに負のスコアが最大なケースもある。 そのようなケースで最大スコアが0とならないように実装する。 具体的には0回移動時のスコアで最大スコアを更新することを避ける。