tessoku-book A45 - Card Elimination の別解
鉄則本こと「競技プログラミングの鉄則 | マイナビブックス」のA45 - Card Eliminationという問題に関して、考察したことを記しておきます。
Google で検索してみましたが、あまり記事もヒットしなかったのでもし誰かの役に立てばと思い。
ChatGPT による本記事の要約
競技プログラミングの問題、Card Eliminationの解法を考察する記事です。問題はW, B, Rの3文字で構成された文字列を特定のルールで結合し、最終的に残る一文字を予測します。解法は二つあり、一つは文字を数字に置き換えてmod3を取る方法。もう一つは結合法則を利用する方法で、どの順序で文字列を結合しても結果が同じになるという性質を利用します。
どんな問題?
WBBBBBRRBRBWWRB
のような W B R の3文字のいずれかで構成された文字列がある。(それぞれ白、青、赤を意味する) この文字には以下の操作を行い、2文字を1文字に変えることができる。
-
WW→W -
BB→R -
RR→B -
WB→B -
WR→R -
BR→W
この操作を繰り返して、最後に残る一文字は3文字中のどの文字になるか?
実際は、最後に残った文字が、入力で与えられた文字
書籍で示されていた解法
この問題は書籍の中では「考察テクニック」の章に位置付けられていて「不変量に着目する」というテーマの問題。解法としては
-
Wを0 Bを1 Rを2 - それぞれの操作を足し算
+ 0 3 \mod 3 - ので、文字列全てを足し算して
mod 3を取れば最終的な色がわかる
というものでした。
Haskell で実装すると以下になります。
toInt :: Char -> Int
toInt 'W' = 0
toInt 'B' = 1
toInt 'R' = 2
main :: IO ()
main = do
[_, c] <- map head . words <$> getLine
as <- getLine
let s = (sum . map toInt) as
putStrLn $ case (c, s `mod` 3) of
('W', 0) -> "Yes"
('B', 1) -> "Yes"
('R', 2) -> "Yes"
_ -> "No"
私の初見の感想としては「なるほどー。でもこれは思いつかない」というものでした。同じような問題に遭遇したときに「よし、数字に置き換えて mod を取ればいいな」となれる気がしません。
別解 「操作は二項演算であり、結合法則を満たす」
もうすこし観察していたら、別解を思いつきました。ので、以下それを記します。
改めて、操作を見てみます。
-
WW→W -
BB→R -
RR→B -
WB→B -
WR→R -
BR→W
これは、二つの要素を持ってきて結合して一つの要素にするという操作ですから、二項演算に相当します。(なので、書籍の解法でも二項演算の
そして、この二項演算は結合法則を満たしている、つまりどんな順序で文字列を結合しても結果は同じになります。これはパッと見で超能力で「すわ！結合法則!!」とわかるというよりは「二項演算による結合だと考えると、結合法則を満たしている可能性がありそうだな?」という思考で仮説を立てて考える感じです。
例えば入力例にある WBBR は左から結合していっても、右から結合していっても、真ん中の BB を最初に結合しても、結局 B になることがわかります。この辺から結合法則を満たしていると当てに行っても、問題ないでしょう。
- 結合法則を満たしているんだから、実際に結合してしまえば良い。計算量は
O(n) - 文字種は
3 2^3 = 8
というわけで結合操作を定義して、愚直に結合操作 (畳み込み) をして判定することでも問題が解けます。
combine :: Char -> Char -> Char
combine 'W' 'W' = 'W'
combine 'R' 'R' = 'B'
combine 'B' 'B' = 'R'
combine 'R' 'B' = 'W'
combine 'B' 'R' = 'W'
combine 'W' 'R' = 'R'
combine 'W' 'B' = 'B'
combine 'B' 'W' = 'B'
combine 'R' 'W' = 'R'
main :: IO ()
main = do
[_, c] <- map head . words <$> getLine
as <- getLine
let c' = foldl1 combine as
putStrLn $ if c == c' then "Yes" else "No"
なお、この操作は結合法則を満たしているだけでなく W はどんな色に結合しても W になるということで単位元になっています。つまり
モノイドであるという性質を使えば、他にもいろんな解法があると思います。書籍で示されていた解法もその一つかと思います。
二つのものを選択して一つにする、という問題は AtCoder でもときおり見かけますが、この問題のように操作を二項演算として捉えることで、結合法則 (あるいは交換法則なども) を満たしているか調べる、つまり代数的構造を調べることによって問題の構造を明らかにできることがあります。
代数的構造を調べて解法を導くアプローチは応用性も高いですし、思考プロセスとして何かをトリガーに発想しやすいと思いました。
追記
モノイドなので Haskell の Monoid クラスを使うと、こんな風にも実装できます。
data Color = W | B | R deriving (Show, Eq)
toColor :: Char -> Color
toColor 'W' = W
toColor 'B' = B
toColor 'R' = R
combine :: Color -> Color -> Color
combine W x = x
combine x W = x
combine R R = B
combine B B = R
combine R B = W
combine B R = W
instance Semigroup Color where
(<>) = combine
instance Monoid Color where
mempty = W
main :: IO ()
main = do
[_, c] <- map head . words <$> getLine
as <- getLine
let c' = mconcat $ map toColor as
putStrLn $ if toColor c == c' then "Yes" else "No"
まあ、コンテストの本番中にここまで丁寧に実装する余裕はないわけですが、参考まで。
Discussion