[1] 最終結果の観察

最終的に全員がスプーンを取る方法としてありうるのは，

• 全員が左側のスプーンを取る
• 全員が右側のスプーンを取る

のいずれかです．よって，これらの結果になるような利き手の総数をそれぞれ求めて足し合わせればよいです．

[2] 数え上げ

以下では，全員が左側のスプーンを取るような利き手の総数を求めます．全員が右側のスプーンを取る場合も同様に求まります．

方針としてはシミュレーションを行います．\(1, \dots, i - 1\) 番目の行動で全員が左側のスプーンを取っているとします．このとき，\(i\) 番目の行動において人 \(P_i\) の左右にスプーンが残っているかを考えると，人 \(P_i\) の左側のスプーンは常に残っていて，右側のスプーンが残っているかどうかは人 \((P_i + 1)\) がまだ行動していないかどうかに対応します．ここで，人 \((N + 1)\) は人 \(1\) を指します．

人 \(P_i\) の行動時点でのスプーンの残り方が分かったので，人 \(P_i\) の利き手としてありうるもののうち人 \(P_i\) が左側のスプーンを取るような利き手を考え，答えを数えます．具体的には，答えを \(1\) に初期化して，以下の処理をシミュレーションと並行して \(i = 1, \dots, N\) の順に行います．

• 人 \(P_i\) の右側のスプーンが残っている場合
  • 人 \(P_i\) は左利きである必要があります．文字列 \(S\) の対応する文字が R なら答えに \(0\) を掛け，それ以外なら何もしません．
• 人 \(P_i\) の右側のスプーンが残っていない場合
  • 人 \(P_i\) はどちらの利き手でも問題ありません．もし文字列 \(S\) の対応する文字が ? なら答えに \(2\) を掛け，それ以外なら何もしません．

以上の処理を，全員が右側のスプーンを取る場合についても同様に行い，結果を足し合わせることで，本問題を \(\mathrm{O}(N)\) 時間で解くことができます．

実装例 (Python)