問題概要
リング状の物体がある．このリングは $n$ ($n \geq 3$) 個のパーツからなり，パーツ $i$ とパーツ $i + 1$ ($1 \leq i < n$) の各組およびパーツ $n$ とパーツ $1$ は隣接している．
今，左手でパーツ $1$ を，右手でパーツ $2$ を把持している．この状態から始めて，次の一連の「操作」を任意の回数行うことができる：
- 片方の手を選ぶ．
- 1. で選んだ手を，それが把持しているパーツに隣接するパーツに移動させる．
- 移動先を他方の手が把持していない場合に限る．
以下の形式で表される $q$ 個の指示が順に与えられる：
- $( H_i, T_i )$ : $H_i$ が
Lなら左手，Rなら右手が，パーツ $T_i$ を把持している状態にする．
全ての指示内容を達成するために必要な操作回数の最小値はいくらか？
制約
- $3 \leq n \leq 3{,}000$
- $1 \leq q \leq 3{,}000$
解法
初期状態あるいはある指示を達成した直後の状態を考えます．このとき，各手の位置が同一であるような達成方法が複数あったとすれば，それらの内で操作回数が最小でないような方法からは，（それ以降の最適な手順は同じなので）全体で最適にはできません．よって，次のように状態をとる動的計画法を考えることができます：
\begin{equation}
\mathit{ dp }[t][l][r] := \text{$t$ 個の指示を達成し，左手がパーツ $l$，右手がパーツ $r$ を把持している状態にするための操作回数の最小値}
\end{equation}
この DP で答えを計算すること自体はできますが，本問に AC するためには 次の 2 つの問題があります：
- DP テーブルのサイズが $\Theta( q n^2 )$ になっていて MLE する．
- 全状態からの遷移を計算すると $\Omega( q n^2 )$ 時間かかって TLE する．
逆に言えば，これらを解決できればこの方針で問題を解けます．
テーブルサイズについては，flying table と呼ばれる[誰によって？]テクニックを使うことで解決できます．これは，$\mathit{ dp }[t][*][*]$ が $\mathit{ dp }[ t - 1 ][*][*]$ にしか依存しないことを利用して，$t$ が偶数である状態たちと $t$ が奇数である状態たちのそれぞれで DP テーブルを使い回すものです．つまり，$\mathit{ dp }[ t \bmod 2 ][*][*]$ から $\mathit{ dp }[ ( t + 1 ) \bmod 2 ][*][*]$ を更新し，その後 $\mathit{ dp }[ t \bmod 2 ][*][*]$ を初期値（というか，今回の演算 ($\min$) の単位元（と見なせる値））で埋めるということをします．これで，DP テーブルのサイズは $\Theta( n^2 )$ になりました．
計算量の削減にはある観察が必要です．$t$ 番目の指示を達成した直後の状態を考えると，その指示で移動先を指定された手の位置は固定されています．よって，$\mathit{ dp }[ t \bmod 2 ][*][*]$ の内，考慮するべき状態の個数は $O( n )$ 個しかなく，いわゆる「配る DP」をやるとして，DP の更新元としてはこれらのみを参照すればよいです．「必要なところだけ見る」を実現する方法はいくつかあると思いますが，「$\mathit{ dp }[ t \bmod 2 ][l][r]$ に意味がある $( l, r )$ の集まり」を保持する構造（std::vector とか）をもちながら「$\mathit{ dp }[ ( t + 1 ) \bmod 2 ][ l' ][ r' ]$ に意味がある $( l', r' )$ の集まり」を構築する方法が考えられます．このための補助的なデータ構造として，「$\mathit{ dp }[*][l][r]$ が最後に更新されたときの $t$」を覚えるサイズ $n \times n$ の配列を用意して管理しておけば，遷移先を次回のイテレーションで参照するべきかどうかを判別できます．以上により，各イテレーションで参照する状態の個数が $O( n )$ で抑えられるようになりました．
まとめると，2 つの工夫によって $\Theta( n^2 )$ 空間・$O( q n )$ 時間のアルゴリズムが得られたので，問題に正答できます．
コード
constexpr auto INF = LIM<>::max() / 2; int main() { IN( int, N, Q ); const auto dist = [&]( const int d, int a, int b ) { if ( d ) { swap( a, b ); } return a <= b ? b - a : ( N - a ) + b; }; static int dp[2][ 1 << 12 ][ 1 << 12 ], last_updated[ 1 << 12 ][ 1 << 12 ]; fill( AALL( dp ), INF ); dp[0][0][1] = 0; VPII currents, nexts; currents.EB( 0, 1 ); REP( q, Q ) { const int cur = q % 2, nex = 1 - cur; IN( char, H ); IN( int, T ); --T; for ( const auto &[ l, r ] : currents ) { REP( d, 2 ) { const auto [ tar, opp ] = H == 'L' ? MP( l, r ) : MP( r, l ); const int pushed = d == 0 ? 1 : -1; const int opp_t = dist( d, tar, T ) == dist( d, tar, opp ) + dist( d, opp, T ) ? ( T + pushed + N ) % N : opp; const auto [ nl, nr ] = H == 'L' ? MP( T, opp_t ) : MP( opp_t, T ); if ( chmin( dp[ nex ][ nl ][ nr ], dp[ cur ][l][r] + dist( d, tar, T ) + dist( d, opp, opp_t ) ) && chmax( last_updated[ nl ][ nr ], q + 1 ) ) { nexts.EB( nl, nr ); } } } for ( const auto &[ l, r ] : currents ) { dp[ cur ][l][r] = INF; } swap( currents, nexts ); nexts.clear(); } int res = INF; for ( const auto &[ l, r ] : currents ) { chmin( res, dp[ Q % 2 ][l][r] ); } cout << res << endl; return 0; }
