\(3S\leq W\) のとき、スコアの自明な上界である \(64S\) を達成できます。以降は \(W\lt 3S\) を仮定します。

解法は単純ですが、証明が非常に長いです。

最初の証明

突然ですが、カード w,s,w,s の順に出す部分が存在しない最適解が存在することを証明します。

そのような部分のうち、最も早くに登場するものを取ってきます。それが ...w,w,s,w,s となっているなら、代わりに ...w,w,s,s,w にすることでこれらの s からの寄与が変わらないまま最後の w をひとつ後にずらすことができて、スコアは同じか改善します。

そうでないとき、最も早くに登場するものを取ってきたはずなので、w,s,[w,s,w,s] とはなっていません。そのため、w,s,w,s の前の方の s に w は一回しか寄与していません。このとき、w,s,w,s の代わりに w,w,s,s とすることでスコアは悪化しません。二個後に s があるとき、その s のスコアは \(9\) または \(12\) 下がりますが、前の方の s のスコアの上がり幅 \(12\) よりは下がらないので、悪化しません。

この操作をすることで w,s,w,s の出現位置がより前になることはないので、この操作は有限回で終了します。よって、カード w,s,w,s の順に出す部分が存在しない最適解が存在します。

問題の言い換え

この証明は何のためにしていたのでしょうか？

ここで、自然に思いつくであろう言い換えをします。

以下の \(11\) 種類の節を適切に組み合わせて、スコアを最大化せよ。

• w：スコア \(0\)
• s：スコア \(27\)
• ws：スコア \(36\)
• wss：スコア \(72\)
• wsss：スコア \(108\)
• wws：スコア \(48\)
• wwss：スコア \(96\)
• wwsss：スコア \(132\)
• wwws：スコア \(64\)
• wwwss：スコア \(112\)
• wwwsss：スコア \(148\)

ただし、これはある節から別の節への「波及」を考えていません。たとえば、節 wws と節 s をこの順に選ぶ時、節 s のスコアを \(27\) として計算してはいけないように見えます。

波及としてありうるのは以下の \(3\) 種類です。

• w の次に w が \(2\) 個以下の節をくっつける
• s が \(2\) 個以下の節の次に s をくっつける
• ws で終わる節に ws で始まる節をくっつける

ただし、\(1\) 番目と \(2\) 番目については、最初からくっつけた後の節を選んでおけばいいだけの話です。それでスコアは良くなるので、この違反を無視して計算しても最適解は変わりません。

\(3\) 番目についても、先程の証明によりこれに該当しない最適解が存在することがわかったのでした。ので、この違反を放置しても最適解は変わりません。

結局、何も気にせずに言い換えた後の問題を解けばよいです。

選び方を絞る①

w について

まず、w の節を \(3\) 回以上選ぶことはありえません。もし \(3\) 回以上選んでいるなら、

• s が \(2\) 個以上の節があるなら、その節から s をひとつ取ってきて wwws にして改善する。
• w が \(2\) 個以下の節があるなら、その節に w をひとつ追加して改善する。

ですので、w を \(3\) 回以上選んでいるなら残りの節はすべて wwws になっているはずですが、\(W\lt 3S\) よりこのようなことは起こりえません。

ws について

ws の節を \(2\) 回以上選ぶことはありえません。このときは代わりに wwss にすることで改善します。

wss について

wss の節を \(3\) 回以上選ぶこともないとしてよいです。このときは代わりに wsss, wwsss にすることで改善します。

wwss について

wwss の節を \(3\) 回以上選ぶことはありえません。このときは代わりに wwwsss \(2\) つにすることで改善します。

wws について

wws の節を \(2\) 回以上選ぶことはありえません。このときは代わりに ws, wwws にすることで改善します。

総括

これらをまとめると、以下のようになります。

• w は \(2\) 回まで
• ws は \(1\) 回まで
• wss は \(2\) 回まで
• wwss は \(2\) 回まで
• wws は \(1\) 回まで

これらを選ぶ回数は全探索してしまい、以降 s, wsss, wwsss, wwws, wwwss, wwwsss のみ使うことにします。

選び方を絞る②

s 単体を使う場合を考えます。

このとき、wwws, wwwss を使うことは考えなくてよいです。

wsss と wwwsss を両方使う場合、wwsss \(2\) つに置き換えると改善します。よって、wsss と wwwsss のどちらかしか使わないとしてよく、これは全探索します。

wwsss を使う場合

wwsss を使い、なおかつ s を \(3\) 個以上使う場合、wsss \(2\) つに置き換えると改善します。よって、s を選ぶ回数は \(2\) 回以下でよく、その回数を全探索します。残りは wwsss +（ wsss と wwwsss のどちらか）になり、これですべて使い切らないといけないのでしたから、連立方程式を解けばよいです。

wwsss を使わない場合

このとき、s +（ wsss と wwwsss のどちらか）を組み合わせてすべて使い切る問題になり、これも両方について連立方程式を解けばよいです。

選び方を絞る③

さて、残ったのは s 単体を使わない場合です。選べるのは wsss, wwsss, wwws, wwwss, wwwsss で、さらに以下の観察を得ます。

• wsss と wwws は同時に使わない
  • 代わりに wwss を \(2\) 回使うと改善します。
• wwsss と wwwss は同時に使わない
  • 代わりに wwss と wwwsss を使うことにしてよいです。（wwss と wwwsss を wwsss と wwwss に変えることはなかったので）
• wwwsss と wsss は同時に使わない
  • 代わりに wwsss を \(2\) 回使うと改善します。
• wwwsss と wwws は同時に使わない
  • 代わりに wwwss を \(2\) 回使うと改善します。

ということで、考えるべきは（ wsss と wwws のどちらか）+（ wwsss と wwwss のどちらか）またはwwwsss +（wwsss と wwwss のどちらか）の \(6\) パターンになり、すべて連立方程式を解けばよいです。

楽な実装

以上で \(O(1)\) の時間計算量でこの問題を解くことができましたが、これを直接実装するのは面倒です。代わりに、以下のようなアルゴリズムにします。

• 以下を全探索する。
  • w は \(2\) 回まで
  • ws は \(1\) 回まで
  • wss は \(2\) 回まで
  • wwss は \(2\) 回まで
  • wws は \(1\) 回まで
  • s は \(2\) 回まで
• すべての節の組み合わせについて、連立方程式を解く。

依然として時間計算量は \(O(1)\) で、しかも上に挙げたすべてのパターンは網羅できています。ただし相当定数倍が重いので、TLEとなったら無駄なペアを探索しないよう多少の改善をするか、直接実装する必要があるかもしれません。