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

苦戦したけど何とか解けてよかった。