Magicode logo
Magicode
2 min read

5人の海賊と100枚の金貨を雑に解く

https://cdn.magicode.io/media/notebox/85061d0f-b567-451d-860c-029dada1616b.jpeg

論理クイズ

有名な問題である海賊と金貨 が再帰で簡単に書けそうなので解いてみる
過半数で可決と、過半数では否決の2パターンあるので両方に対応したい
 ー 可決するための数を求める関数を少しいじるだけで対応させる

再帰

5人組での最適解は4人組での最適解を見て考え、4人組での最適解は3人組での ... というような線形再帰的な考えが自然だが、「金貨5枚と100人の海賊」のように最初の何人かがどうあがいても否決されてしまう場合に無駄な計算をさせたくなかったので末尾再帰で考えることにした
haskell
import Data.List ( sortOn, unfoldr )
import Data.Bifunctor ( Bifunctor(first, bimap) )
import Data.Ord ( Down(Down) )
type Gold = Int
-- ランク1がボス2が次のボス ... 
type Rank = Int
type Pirate = (Gold, Rank)

-- 配分を考える
shareStep :: Gold -> [Pirate] -> [Pirate]
shareStep g [] = [(g, 1)]
shareStep g pirates =
    (g - golds, 1):(proponents ++ opponents)
    where
        -- 安い順に並び替え、過半数をとれるように分割
        (cheapers, highers) = splitAt (majorityNum (length pirates)) $ sortOn fst pirates
        proponents = map (bimap (\x -> if x >= g then x else succ x) succ) cheapers -- +1金貨で買収して位を下げる
        opponents = map (\(_, r) -> (0, succ r)) highers -- 金貨没収して位を下げる
        golds = sum $ map fst proponents

-- 過半数+1で可決にする
majorityNum :: Int -> Int
majorityNum len = len `div` 2 + len `mod` 2
-- majorityNum len = len `div` 2 こうすれば過半数可決の方になる

-- 末尾再帰で考える
share :: Gold -> Int -> [Pirate] -> [Pirate]
share g n pirates
    -- マイナスになったら終わる
    | any (\x -> fst x < 0) pirates = share g (n-1)  []
    -- 基底
    | length pirates == n = pirates
    | otherwise = share g n (shareStep g pirates)

-- 回答
solve :: Gold -> Int -> [Pirate]
solve g n = sortOn snd $ share g n []
print $ solve 100 5

[(97,1),(0,2),(1,3),(0,4),(2,5)]

感想

過半数で可決の方だとただ"0", "1"が交互になるだけだけど、過半数では否決される方だとなかなか面白い規則が見られる
いろいろ変えて動かしてみてね

Discussion

コメントにはログインが必要です。