TopCoder SRM 682 (Div. 2) Hard. FriendlyRobot
かなり苦戦。
解法
自明な DP は次のようなもの。
- dp[ i 番目まで見た ][ 現在の x 座標 ][ 現在の y 座標 ][ 変更した回数 ] := 原点を通った回数の最大値
しかし O(n4) なので間に合わない。
少し考えると現在の x 座標と y 座標はなくても更新できることがわかり、次の DP ができる。
- dp[ i 番目まで処理した段階で原点にいる ][ 変更した回数 ] := 原点を通った回数の最大値
これは O(n3) でできる。
いま i 番目まで処理しており、j 番目で再び原点に戻すことを考える。
i 番目 から k 番目をシミュレートした結果 (x,y) に辿り着いたとする。 これを強引に (0,0) に辿り着くように書き換えよう。 なお x, y は絶対値をとっても問題ないので、(x,y) は第一象限にあると考えて解説を進める。
(x+y) mod 2 != 0 のとき
どうやっても (0, 0) に戻すことは出来ない。
x mod 2 == 0 and y mod 2 == 0 のとき
x/2 個の R を L に、y/2 個の U を D に書き換えればよい。
x mod 2 == 1 and y mod 2 == 1 のとき
(x-1)/2 個の R を L に、(y-1)/2 個の U を D に、1 個の U を L に書き換えればよい。
以上を踏まえてコードを書くと次のようになる。
TopCoder SRM 679 (Div. 2) Hard. FriendlyRobot
苦戦したけど何とか解けてよかった。