Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング

)BTLFMMͰΞϧΰϦζϜΛந৅Խ͢Δ ؔ਺ܕݴޠͰڝٕϓϩάϥϛϯά /BPZB*UP !OBPZB@JUP

ࣗݾ঺հ • גࣜձࣾ Ұٳ ϗςϧɺϨετϥϯͷ8FC༧໿ࣄۀͷձࣾ Ͱಇ͍͍ͯ·͢ • झຯͰڝٕϓϩάϥϛϯάΛᅂΜͰ͓Γɺ)BTLFMMͰࢀઓ͍ͯ͠·͢ • ݱࡏͷϨʔτ͸ਫ৭
Ͱ͢ – ڭՊॻʹग़ͯ͘ΔྨͷΞϧΰϦζϜ͸೉ͳ͘࢖͍͜ͳͤΔϨϕϧ

࿩͍ͨ͜͠ͱ • )BTLFMM ͰڝٕϓϩάϥϛϯάʹࢀՃ͍ͯ͠ΔɻΞϧΰϦζϜΛந৅Խ͢Δͱɺͦͷ࣮૷͕ ࣅͨΑ͏ͳΠϯλϑΣʔεʹͳΔ͜ͱΛܦݧͨ͠ – ߴ֊ؔ਺ͱͯࣸ͠૾ Gͱ݁߹ͷೋ߲ԋࢉ͕ύϥϝʔλͱͯ͠Α͘දΕΔ • ͦΕ͸ۮવͳͷ͔ɺ͍΍ɺۮવͰ͸ͳ͍
– )BTLFMMͷࠜఈʹ͋Δ࠶ؼσʔλߏ଄ɺͦΕʹ࠷దͳૢ࡞Ͱ͋Δࣸ૾ͱ৞ΈࠐΈ NBQSFEVDF • ࣸ૾ͱ৞ΈࠐΈʹΑΔؔ਺ͷΠϯλϑΣʔε͔ΒΞϧΰϦζϜͷ୅਺తߏ଄͕ݟ͑Δ • ؔ਺ܕϓϩάϥϛϯάɺ)BTLFMM͸ΞϧΰϦζϜΛΑΓந৅౓ߴ͘ଊ͑ΔࢥߟΛิॿͯ͘͠ ΕΔ

໨࣍ • ࣸ૾ NBQ Ͱ໰୊Λղ͘ • ྦྷੵ࿨ uuu GPMETDBOMʹΑΔʮ৞ΈࠐΈʯ •
ΞϧΰϦζϜΛந৅Խ͢Δ uuu ೋ෼୳ࡧΛߴ֊ؔ਺Ͱந৅Խ͢Δ • #'4Λந৅Խ͢Δuuu ؔ਺ GΛʮ͋Δঢ়ଶ͔Β࣍ͷঢ়ଶ΁ͷঢ়ଶભҠʯͱଊ͑Δ • ಈతܭը๏Λ )BTLFMMͰΠϛϡʔλϒϧʹղ͘ uuuঢ়ଶۭؒͷ৞ΈࠐΈɺͦͯ͠୅਺తߏ଄ ͕ݟ͑Δ • ͳͥΞϧΰϦζϜΛந৅Խ͢ΔͱɺNBQSFEVDF GPME ΍୅਺తߏ଄͕ uuu ؔ਺ܕϓϩά ϥϛϯάɺ)BTLFMM͕ͦΕΛଅ͢

ΩʔʹͳΔεϥΠυΛઌʹ

໋ྩܕ ୹໋σʔλ uuuҰ࣌తͳதؒঢ়ଶΛ܁Γฦ͠ॻ͖׵͑ͯ౴͑ʹ޲͔͏ ؔ਺ܕ Ӭଓσʔλ uuuঢ়ଶΛ࣍ͷঢ়ଶ΁ࣸ͢

ࣸ૾ͱ݁߹ ू໿ uuu NBQSFEVDF GPME • ؔ਺ܕϓϩάϥϛϯάͰ͸ʮࣸ૾ͱ݁߹ ू໿ ʯͷϝϯλϧϞσϧͰ໰୊Λղ͘ •
ࣸ૾ͱ݁߹ ू໿ uuu NBQSFEVDF GPME • ͳͥ NBQSFEVDF͔ – )BTLFMMͷෆมσʔλߏ଄͸୅਺తσʔλܕʹΑΔ࠶ؼσʔλߏ଄ – ࠶ؼσʔλߏ଄ͷૢ࡞ʹ͸ NBQSFEVDF – -*41ͷ௚ײ͔Βʜ ͋ͱͰ

#'4ʹ౉͍ͯ͠Δؔ਺ GͷҙຯΛߟ͑ͯΈΔ let dist = bfs f (+) (-1) bounds
[(1, 0 :: Int)] • f Λهड़͢Δ͚ͩͰ໰୊͕ղ͚Δ͕ɺf ͸Կऀ? • (v -> [(v, e)]) • (ঢ়ଶ -> [(࣍ͷঢ়ଶ, ભҠίετ)]) ͱ͍͏ঢ়ଶભҠͷࣸ૾ ঢ়ଶ͔ΒભҠީิ΁ͷࣸ૾ ͱߟ͑Δ͜ͱ͕Ͱ͖Δ

݁߹ͷ࢓ํͱঢ়ଶભҠͷؔ਺ ͋ͱॳظঢ়ଶ Λએݴ͢Ε͹ɺ%1͕ղ͚Δ main = do [n, wx] <- getInts
items <- replicateM n getTuple let dp = accumArrayDP @UArray f max 0 (0, wx) [(0, 0)] items where f (w, acc) (wi, vi) = [(w, acc), (w + wi, acc + vi)] print $ maximum (elems dp)

͜Ε͸ۮવͳͷ͔ • )BTLFMMͰΞϧΰϦζϜΛந৅Խ͢Δͱɺ݁߹ ೋ߲ ԋࢉɺࣸ૾ ͋ͱॳظ ঢ়ଶ ͕ύϥϝʔλԽ͞ΕͯΠϯλϑΣʔεʹදΕΔ • NBQSFEVDF
• ͦͯ͠ΠϯλϑΣʔε͕ʮ୅਺తߏ଄ΈʯΛଳͼΔ

ͳͥͦΕ͕ɺ୅਺తߏ଄ͱ݁ͼͭ͘ͷ͔ • લड़ͷ௨Γ ࠶ؼతσʔλߏ଄͸ࣸ૾ͱ݁߹ʹࣗવʹؐݩͰ͖Δ • ঢ়ଶͷʮ఻ൖʯͱʮू໿ʯ͸୅਺తੑ࣭Λඞཁͱ͢Δ – ʮ఻ൖʯ֤ঢ়ଶΛ৽͍͠ঢ়ଶʹࣸ͢ ˠࣸ૾ –
ʮू໿ʯෳ਺ͷ݁ՌΛҰͭʹ·ͱΊΔ ˠ݁߹ – ͜Ε͕݁߹తͰͳ͚Ε͹࠶ؼɾޮ཰Խ͕೉͍͠ ˠ୅਺తߏ଄ͷཁ੥ ΞϧΰϦζϜΛந৅Խ͢Δͱࣸ૾ͱ݁߹͕ܭࢉͷຊ࣭తͳߏ੒ཁૉͱͯ͠ݱΕΔ ঢ়ଶۭؒΛू߹ͱΈͳ͢ͱɺ୅਺తߏ଄ʢ'VODUPS .POPJE 4FNJSJOHʣʹରԠ͢Δ )BTLFMMͷܕͱߴ֊ؔ਺͸ɺͦͷߏ଄ΛࣗવʹΠϯλϑΣʔεͱͯ͠࿐ग़ͤ͞Δ ந৅Խ͸ʮܭࢉͷ୅਺ʯΛՄࢹԽ͢ΔաఔͰ΋͋Δ

ࣸ૾ NBQ Ͱ໰୊Λղ͘

https://atcoder.jp/contests/abc081/tasks/abc081_b

8 12 40 4 6 20 2 3 10 ۮ਺͔͠ͳ͍ͷͰૢ࡞͢Δ
·ͩۮ਺͔͠ͳ͍ͷͰૢ࡞͢Δ ح਺͕ग़͖ͯͨͷͰऴΘΓ

໋ྩܕϓϩάϥϛϯάͰ࣮૷ uuu ୹໋σʔλߏ଄Λ܁Γฦ͠ॻ͖׵͑ͯ౴͑ΛಘΔ count = 0 while all(a % 2
== 0 for a in as): for i in range(n): as[i] //= 2 count += 1 print(count)

ؔ਺ܕ Ӭଓσʔλϓϩάϥϛϯά ͳΒʮࣸ૾ NBQ Λ܁Γฦ͠ద༻͢Δʯͱߟ͑Δ let res = takeWhile (all
even) $ iterate (map (`div` 2)) as print $ length res

ؔ਺ద༻ʹΑͬͯ஋ΛಘΔ ؔ਺ʹΑͬͯ஋Λม׵͢Δɾࣸ͢ ࣜ͸ඞͣ໭Γ஋Λฦ͢ɻҾ਺ͷ஋͔Β໭Γ஋ʹ஋Λม׵ͨ͠ɺࣸͨ͠ɺͱݟΔ͜ͱ΋Ͱ͖Δ 𝑓 ؔ਺ܕϓϩάϥϛϯάͱܕγεςϜͷϝϯλϧϞσϧ https://speakerdeck.com/naoya/guan-shu-xing-puroguramingutoxing-sisutemunomentarumoderu

໋ྩܕ ୹໋σʔλ uuuҰ࣌తͳதؒঢ়ଶΛ܁Γฦ͠ॻ͖׵͑ͯ౴͑ʹ޲͔͏ ؔ਺ܕ Ӭଓσʔλ uuuঢ়ଶΛ࣍ͷঢ়ଶ΁ࣸ͢

)BTLFMMͰڝٕϓϩάϥϛϯάΛ΍͍ͬͯ͘ɺͱ͍͏͜ͱ͸ • ෆมͳ஋ɺෆมͳσʔλߏ଄ ӬଓσʔλɺӬଓσʔλߏ଄ Λલఏʹ΍͍ͬͯ͘ • ෆมͳσʔλͷૢ࡞ମܥ uuu NBQSFEVDF GPME
– ৄ͘͠͸͋ͱͰ

ྦྷੵ࿨ uuu GPMETDBOMʹΑΔʮ৞ΈࠐΈʯ

۠ؒ࿨ʹ͸ྦྷੵ࿨Λ࢖͏ͱΑ͍ let ds = [3, 1, 4, 1, 5, 9]
:: [Int] s = scanl' (+) 0 ds -- [0, 3, 4, 8, 9, 14, 23]

໋ྩతʹ࣮૷͢Δ p, q = input().split() ds = [3, 1, 4,
1, 5, 9] # 累積和 s = [0] * 7 for i in range(6): s[i + 1] = s[i] + ds[i] pi = ord(p) - ord('A') qi = ord(q) - ord('A') print(abs(s[qi] - s[pi]))

໋ྩܕ uuu Ұ࣌తͳঢ়ଶΛ܁Γฦ͠ॻ͖׵͑ͯɺྦྷੵ࿨ͱ͢Δ # 累積和 s = [0] * 7
for i in range(6): s[i + 1] = s[i] + ds[i]

ؔ਺ܕͰ࣮૷͢Δ main :: IO () main = do (p, q)
<- auto @(Char, Char) let ds = [3, 1, 4, 1, 5, 9] :: [Int] s = listArray @UArray ('A', 'G') $ scanl' (+) 0 ds ans = s ! q - s ! p print $ abs ans

݁߹ ͷ࠶ؼతͳؔ਺ద༻ uuu ʮ৞ΈࠐΈʯ foldl (+) 0 [3, 1, 4,
1, 5, 9] ==> ((((((0 + 3) + 1) + 4) + 1) + 5) + 9) scanl (+) 0 [3, 1, 4, 1, 5, 9] [ 0 , (0 + 3) , ((0 + 3) + 1) , (((0 + 3) + 1) + 4) , ((((0 + 3) + 1) + 4) + 1) , (((((0 + 3) + 1) + 4) + 1) + 5) , ((((((0 + 3) + 1) + 4) + 1) + 5) + 9) ]

վΊͯ )BTLFMMͰͷྦྷੵ࿨ uuu TDBOMΛΈͯΈΔ let ds = [3, 1, 4,
1, 5, 9] :: [Int] s = scanl' (+) 0 ds -- [0, 3, 4, 8, 9, 14, 23 scanl' :: (b -> a -> b) -> b -> [a] -> [b] • ࠶ؼతʹ݁߹Λద༻͢Δɺͱ͍͏ྦྷੵܭࢉ ৞ΈࠐΈ Λந৅Խͨ͠ͷ͕ TDBOM • TDBOMͷΠϯλϑΣʔεʹ͸݁߹ԋࢉ͕ύϥϝʔλͱͯ͠දΕ͍ͯΔ – ͳΒྦྷੵ࿨ – NBYͳΒྦྷੵ NBY – NJOͳΒྦྷੵ NJO – YPSͳΒྦྷੵ YPS

ࣸ૾ͱ݁߹ ू໿ uuu NBQSFEVDF GPME • ؔ਺ܕϓϩάϥϛϯάͰ͸ʮࣸ૾ͱ݁߹ ू໿ ʯͷϝϯλϧϞσϧͰ໰୊Λղ͘ •
ࣸ૾ͱ݁߹ ू໿ NBQSFEVDF GPME • ͳͥ NBQSFEVDF͔ – )BTLFMMͷෆมσʔλߏ଄͸୅਺తσʔλܕʹΑΔ࠶ؼσʔλߏ଄ – ࠶ؼσʔλߏ଄ͷૢ࡞ʹ͸ NBQSFEVDF – -*41ͷ௚ײ͔Βʜ ͋ͱͰ

ΞϧΰϦζϜΛந৅Խ͢Δ uuu ೋ෼୳ࡧΛߴ֊ؔ਺Ͱந৅Խ͢Δ

୯ௐੑ͕͋ΔͷͰɺڥքΛఆΊΔ͜ͱ͕Ͱ͖Δ Ҏ্ uuu
ճ Ҏ্ uuuճ Ҏ্ uuu ճ Ҏ্ uuuճ Ҏ্ uuu ճ Ҏ্ uuu ճ ͜͜·Ͱ৚݅Λຬͨ͢ɺҎ߱͸ຬͨ͞ͳ͍ YҎ্ͷཁૉ͕ YճҎ্දΕΔ͔

ೋ෼୳ࡧͰղ͚·͢ɻͰ΋ɺίϯςετதʹೋ෼୳ࡧΛॻ͘ͱόάΒ͕ͤͪ main :: IO () main = do _ <-
getInt as <- getInts let binSearch (ok, ng) | abs (ng - ok) == 1 = ok | otherwise = do let m = (ok + ng) `div` 2 count = length $ filter (>= m) as if count >= m then binSearch (m, ng) else binSearch (ok, m) print $ binSearch (0, 10 ^ 18)

ຖճॻ͔ͳ͍͍ͯ͘Α͏ɺந৅Խ͠·͢ ˠߴ֊ؔ਺ G͕දΕΔ -- | 左が true / 右が false
で境界を引く bisect2 :: (Integral a) => (a, a) -> (a -> Bool) -> (a, a) bisect2 (ok, ng) f | abs (ng - ok) == 1 = (ok, ng) | f m = bisect2 (m, ng) f | otherwise = bisect2 (ok, m) f where m = (ok + ng) `div` 2 let (ok, _) = bisect2 (0, 10 ^ 18) (¥x -> countBy (>= x) as >= x) print ok

৚݅ؔ਺ G͸ࣸ૾ͱΈͳͤΔ • ೋ෼୳ࡧ͸ʮڥքΛҾ͘৚݅ʯΛؔ਺ GͰ౉͢Α͏ந৅ԽͰ͖Δ • (a -> Bool) Λʮ஋
੔਺ ͔Β ৚݅Λຬ͔ͨ͢Ͳ͏͔΁ͷࣸ૾ʯͱଊ͑Δ͜ͱ͕Ͱ͖Δ • ΞϧΰϦζϜΛந৅Խͨ͠Βͦ͜ʹࣗવͱࣸ૾ G͕දΕͨ bisect2 :: (Integral a) => (a, a) -> (a -> Bool) -> (a, a)

#'4 ෯༏ઌ୳ࡧ Λந৅Խ͢Δ ؔ਺ GΛʮ͋Δঢ়ଶ͔Β࣍ͷঢ়ଶ΁ͷঢ়ଶભҠʯͱଊ͑Δ

https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_an

1 2 4 3 5
6

άϥϑΛʮྡ઀Ϧετʯʹߏ଄Խͯ͠ #'4 ෯༏ઌ୳ࡧ ͢Δ main = do [n, m] <-
getInts uvs <- replicateM m getTuple -- 1 => [(2, 1), (4, 1)] という構造の「隣接リスト」にする let g = accumArray @Array (flip (:)) [] (1, n) $ concatMap (¥(u, v) -> [(u, (v, 1)), (v, (u, 1))]) uvs -- 幅優先探索する dist = bfs g [(1, 0)] for_ [1 .. n] $ ¥s -> print $ dist ! s

ࢀߟ ઌͷ #'4 ͷ࣮૷ bfs :: (Ix v, IArray a
[(v, e)], Num e, Eq e) => a v [(v, e)] -> [(v, e)] -> Array v e bfs g v0s = runSTArray $ do dist <- newArray (bounds g) (-1) for_ v0s $ ¥(v0, d0) -> do writeArray dist v0 d0 aux (Seq.fromList [v0 | (v0, _) <- v0s]) dist return dist where aux Empty _ = return () aux (v :<| queue) dist = do acc <- readArray dist v us <- filterM ( ¥(u, _) -> (fmap (== -1) . readArray dist) u ) (g ! v) queue' <- foldForM queue us $ ¥q (u, w) -> do writeArray dist u $! acc + w return $ q |> u aux queue' dist ༨ஊ ࢲ͸͜Ε͙Β͍ʹͳΔͱίϯςετ தʹ͸ॻ͖ͨ͘ͳ͍ͷͰϥΠϒϥϦԽ͠· ͕͢ɺ$ ΍1ZUIPOͰ΍ͬͯΔਓ͸ຖ ճ#'4ΛιϥͰهड़ͯͨ͠Γ͠·͢

ʮάϥϑͷྡ઀ϦετʯͷͨΊͷ࣮૷ʹͳͬͯ͠·͍ͬͯΔ let dist = bfs g [(1, 0)] • #'4͸άϥϑͷྡ઀ϦετͷͨΊ͚ͩͷ୳ࡧΞϧΰϦζϜͰ͸ͳ͍
• ྡ઀Ϧετͷߏ଄ʹґଘ͍ͯ͠ΔՕॴΛύϥϝʔλԽ͠ɺந৅౓Λ্͛Α͏

ந৅౓Λ্͛Δ uuu άϥϑͷભҠΛ֎෦͔Β஫ೖͰ͖ΔΑ͏ʹ͢Δ let dist = bfs (g !) (+)
(-1) (bounds g) [(1, 0)] • (g !) uuuʮ௖఺W͔ΒḷΕΔ௖఺͸ ʯͱ͍͏ࣸ૾ G – ʮ௖఺ ͔Β͸ɺ௖఺ ̎ ͱ௖఺ ΁ɺͦΕͧΕॏΈ ͰભҠͰ͖ΔʯΛهड़͢Δؔ਺ – f v = g ! v • ڑ཭ͷ݁߹ԋࢉ (+)

ೋ࣍ݩάϦουͷ୳ࡧ໰୊Λղ͍ͯΈΔ uuu ಉ࣮͡૷Ͱղ͚Δ͔ https://atcoder.jp/contests/abc308/tasks/abc308_d

#'4ͷ࣮૷Λม͑Δ͜ͱͳ͘ɺؔ਺ GΛهड़͢Δ͚ͩͰ໰୊͕ղ͚Δ main = do [h, w] <- getInts grid
<- getCharGrid ((1, 1), (h, w)) let dist = bfs f (+) (-1) (bounds grid) [((1, 1), 0)] where f v = [ (u, 1) | d <- [(1, 0), (0, 1), (-1, 0), (0, -1)], let u = v + d, inRange (bounds grid) u, case (grid ! v, grid ! u) of ('s', 'n') -> True ('n', 'u') -> True ('u', 'k') -> True ('k', 'e') -> True ('e', 's') -> True _ -> False ] printYn $ dist ! (h, w) /= -1 ʮϚε WˠW͔Β౸ୡͰ͖ΔϚε VͷϦετʯ ͱ͍͏ࣸ૾ άϦουͷ্Լࠨӈʹ৚݅Λຬͨ͢ભҠઌ͕͋ΔͳΒ ͦΕΛྻڍ

https://atcoder.jp/contests/abc235/tasks/abc235_d Ұݟ͢ΔͱάϥϑͰ΋άϦου΋ͳ͍໰୊ɻछྨͷૢ࡞Λ܁Γฦͯ͠ /ʹͰ͖Δ

B /ͷ৔߹ 1 3 9 27 81 72 243 18

main = do [a, n] <- getInts let bounds =
(1, 10 ^ 6 + 1 :: Int) let dist = bfs f (+) (-1) bounds [(1, 0 :: Int)] where f x | x >= 10 && x `mod` 10 /= 0 = [(x', 1) | x' <- [rotate x, a * x], inRange bounds x'] | otherwise = [(a * x, 1) | inRange bounds (a * x)] rotate y = let ys = toDigits 10 y in fromDigits 10 (last ys : init ys) print $ dist ! n ΍͸Γؔ਺ GΛهड़͢Δ͜ͱͰ໰୊͕ղ͚Δ

վΊͯ #'4ʹ౉͍ͯ͠Δؔ਺ GͷҙຯΛߟ͑ͯΈΔ let dist = bfs f (+) (-1)
bounds [(1, 0 :: Int)] • f Λهड़͢Δ͚ͩͰ໰୊͕ղ͚Δ͕ɺf ͸Կऀ? • (v -> [(v, e)]) • (ঢ়ଶ -> [(࣍ͷঢ়ଶ, ભҠίετ)]) ͱ͍͏ঢ়ଶભҠͷࣸ૾ ঢ়ଶ͔ΒભҠީิ΁ͷࣸ૾ ͱߟ͑Δ͜ͱ͕Ͱ͖Δ

ࣸ૾ Gʹ͍ͭͯߟ͑Δ͏ͪɺ#'4ͷϝϯλϧϞσϧ͕Ξοϓσʔτ͞ΕΔ • #'4͸άϥϑΛ୳ࡧ͢ΔΞϧΰϦζϜ • #'4͸άϦουΛ୳ࡧ͢ΔΞϧΰϦζϜ uuu άϦου΋άϥϑͷҰछ • #'4͸ঢ়ଶΛ୳ࡧ͢ΔΞϧΰϦζϜ
uuu ঢ়ଶભҠΛάϥϑભҠͱߟ͍͑ͯͬͨΓ͖ͨΓ

༨ஊ )BTLFMM Ҏ֎Ͱ΋͜Μͳ෩ʹ #'4Λந৅ԽͰ͖Δ • Θ͔Βͳ͍͚Ͳɺ؆୯Ͱ͸ͳͦ͞͏ • ભҠΛʮঢ়ଶભҠͷؔ਺ʯͱ͢Δ͜ͱ͸Ͱ͖Δ • ঢ়ଶۭؒͷߏ଄
࣍ݩ ΛύϥϝʔλԽ͢Δ͜ͱͱɺύϑΥʔϚϯεΛཱ྆͢Δͷ͕೉͍͔͠ ΋ – )BTLFMMͷ "SSBZ͸࣍ݩΛύϥϝʔλԽͰ͖Δ

ಈతܭը๏Λ )BTLFMMͰΠϛϡʔλϒϧʹղ͘ ঢ়ଶۭؒͷ৞ΈࠐΈɺͦͯ͠୅਺తߏ଄͕ݟ͑Δ

φοϓβοΫ໰୊ͷΑ͋͘ΔϞσϧ uuu ೋ࣍ݩͷάϦου ೋ࣍ݩ഑ྻ Ͱߟ͑Δ

for (int j = 0; j <= W; ++j) dp[0][j]
= 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= W; ++j) { if (j >= w[i]) dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]); else dp[i+1][j] = dp[i][j]; } } cout << dp[N][W] << endl; ໋ྩతͳ࣮૷ uuu Մมͳೋ࣍ݩ഑ྻΛ༻ҙͯ͠ॻ͖׵͑Δ

%1Λ͜ͷϞσϧͰߟ͑ͨͱ͖ͷ՝୊ • ೋ࣍ݩͰ͋Ε͹಄ͰΠϝʔδͰ͖Δ͕ɺࡾ࣍ݩʹͳΔͱ΍΍͍͜͠ɻ࢛࣍ݩҎ্͸Πϝʔδ͕೉͍͠

%1ͷܭࢉͷಛੑ • ෦෼໰୊ॏෳੑͱ෦෼ߏ଄࠷దੑ • ࡶʹ͍͏ͱ – Ұͭલͷঢ়ଶ͚͔ͩΒ࣍ͷঢ়ଶ͕ܭࢉͰ͖Δ ܭࢉաఔͰ࠷ॳͷํͷঢ়ଶ͸͍Βͳ͍ – ͦΕΛ܁Γฦͤ͹࠷దղ͕ٻ·Δ

͜ͷߦ ঢ়ଶ Λܭࢉ͢Δͷ ʹ͸ɺҰͭલͷߦ Ұͭલͷ ঢ়ଶ ͚ͩΘ͔Ε͹͍͍

ʮೋ࣍ݩ഑ྻΛॻ͖׵͑ΔʯͰ͸ͳ͘ʮঢ়ଶۭ͕ؒ࣍ͷঢ়ଶʹભҠ͢Δʯͱߟ͑Δ ঢ়ଶۭؒ ભҠ ભҠ ભҠ

Ұͭલͷঢ়ଶΛ࣍ͷঢ়ଶʹભҠͤ͞ΔɻͦΕΛ࠶ؼతʹ uuu GPME͡ΌΜ main = do [n, wx] <- getInts
items <- replicateM n getTuple -- 初期状態の状態空間 let dp0 = accumArray @UArray max minBound (0, wx) [(0, 0 :: Int)] -- 状態空間を、再帰的に状態遷移させる let dp' = foldl' f dp0 items where f dp (wi, vi) = accum max dp [(w + wi, acc + vi) | (w, acc) <- assocs dp, inRange (bounds dp) (w + wi)] print $ maximum (elems dp) Մม഑ྻΛߋ৽͢Δͱ͍͏໋ ྩతͳ࣮૷Ͱ͸ͳ͘ɺෆมͳ ஋Λ৞ΈࠐΜͰ͍͘ɺͱ͍͏ )BTLFMMΒ͍࣮͠૷ʹ

໰୊ʹݻ༗ͷ෦෼ΛύϥϝʔλԽ͠ɺGPMEʹΑΔ %1ܭࢉΛந৅Խ͢Δ -- 畳み込みDP -- ex) accumArrayDP @UArray f max
minBound (0, wx) [(0, 0)] wvs accumArrayDP :: ( IArray a e, Ix v, Eq e, Show e, Show v, Show (a v e), Foldable t ) => ((v, e) -> x -> [(v, e')]) -> -- 状態遷移関数 f v / x をみて v の次の遷移可能性を返す (e -> e' -> e) -> -- 緩和の二項演算 e -> -- 初期値 (0, minBound, maxBound, False など) (v, v) -> -- 状態空間の下界、上界 [(v, e')] -> -- 開始時点の状態 t x -> -- 入力 (時間遷移) a v e -- Array or UArray accumArrayDP f combine initial (l, u) v0s xs = let dp = accumArray combine initial (l, u) v0s in foldl' transition dp xs where transition dp x = accumArray combine initial (l, u) $ concatMap (filter (inRange (bounds dp) . fst) . (`f` x)) (assocs dp)

φοϓβοΫ໰୊͸͜͏ղ͚Δ main = do [n, wx] <- getInts items <-
replicateM n getTuple let dp = accumArrayDP @UArray f max 0 (0, wx) [(0, 0)] items where f (w, acc) (wi, vi) = [(w, acc), (w + wi, acc + vi)] print $ maximum (elems dp)

݁߹ͷ࢓ํͱঢ়ଶભҠͷؔ਺ ͋ͱॳظঢ়ଶ Λએݴ͢Ε͹ɺ%1͕ղ͚Δ main = do [n, wx] <- getInts
items <- replicateM n getTuple let dp = accumArrayDP @UArray f max 0 (0, wx) [(0, 0)] items where f (w, acc) (wi, vi) = [(w, acc), (w + wi, acc + vi)] print $ maximum (elems dp)

%1΋ɺந৅Խͨ͠Β݁߹ͱࣸ૾͕ύϥϝʔλԽ͞Εͨ • ࿩ͷྲྀΕతʹೋ࣍ݩ഑ྻ ˠঢ়ଶۭؒͷ৞ΈࠐΈɺͱ͍͏Ϟσϧͷస׵Λઌʹߟ͕͑ͨ • ࣮ࡍʹ͸ɺ%1ͷந৅ԽΛࢼΈͨΒ GPMEͷ࣮૷ʹͳΓɺޙ෇͚ͰҙຯΛߟ͑ͨΒʮঢ়ଶۭؒ ͷ৞ΈࠐΈʯͱ͍͏Ϟσϧʹؾ͕͍ͭͨ • ʮ%1
΋ NBQ SFEVDF GPME.BQ ͡Όͳ͍͔ ʜʯ – ࣸ૾ uuu ঢ়ଶͷભҠ – ݁߹ uuu ෳ਺ܦ࿏͔Βಉ͡ঢ়ଶʹྲྀೖͨ͠ͱ͖ɺ஋ΛҰͭʹू໿ ˞ͨͩ͠ɺ͜ͷϞσϧͰղ͚Δͷ͸φοϓβοΫ%1ɻ֝௓ͼ%1͸͜ͷϞσϧͰ͸ղ͚ͳ͍

ΠϯλϑΣʔεΛோΊΔͱ୅਺తߏ଄΋ݟ͑ͯདྷΔ uuu %1͸൒؀తߏ଄Λ࣋ͭ let dp = accumArrayDP @UArray f (+)
0 (0, n) [(0, 0)] items f ((v, e) -> x -> [(v, e')]) ঢ়ଶ (v, e) ʹೖྗ x Λ࡞༻ͤ͞ෳ਺ͷભҠઌ (v, e') Λੜ੒͢Δ (࡞༻ తͳ৐๏) (+) (e -> e' -> e) ಉ͡ঢ়ଶʹෳ਺ભҠ͕ू·Δͱ͖ɺ·ͱΊΔ (Ճ๏) 0 e ॳظ஋ (Ճ๏ͷ୯Ґݩ) • %1͸ɺ͋Δঢ়ଶ্ۭؒʹ͓͚ΔϞϊΠυʢࣸ૾ʣ࡞༻ͱɺ൒܈తͳू໿Λ૊Έ߹Θͤͨܭࢉ • GPME.BQ͸.POPJEΛ࢖͏͕ɺͦΕΛΑΓҰൠԽͯ͠4FNJSJOHʹ֦ுͨ͠΋ͷ͕%1Ͱ͋ΔͱΈͳͤ Δ

ந৅ͷߏ଄ ΠϯλϑΣʔε ͕ྑ͘ࣅ͍ͯΔ • #'4΋ %1΋ɺந৅తʹ͸ঢ়ଶۭؒʹ஋Λ഑ΓɾूΊΔૢ࡞ͷ্ʹߏங͞ΕͨϞσϧ • #'4΋൒؀తߏ଄ ·ͨ͸ͦͷ֦ு Λ࣋ͭ
·ͩͪΌΜͱߟ͑ΒΕ͍ͯ·ͤΜ let dp = accumArrayDP @UArray f (+) 0 (0, n) [(0, 0)] items let dist = bfs f (+) (-1) (0, n) [(1, 0)]

f f f f f f (+), max, min, …
NBQ SFEVDF

ͳͥΞϧΰϦζϜΛந৅Խ͢ΔͱɺNBQSFEVDF GPME ΍୅਺తߏ଄͕ ؔ਺ܕϓϩάϥϛϯάɺ)BTLFMM͕ͦΕΛଅ͢

͠Ό͘ͱΓ๏ • (+) (-) 0 ··· ݁߹ɺٯݩɺ୯Ґݩ → Մ׵ϞϊΠυ •
ʮՄ׵ϞϊΠυ্ͷ෦෼۠ؒͷྦྷੵ஋ʯʹରͯ͠ʮ৚݅ f Λຬͨ͢࠷େ۠ؒΛ୳ࡧ͢Δʯ – f ··· ϞϊΠυͷ৞ΈࠐΈʹରͯ͠൑ఆΛ෇͚ͨʮ৚݅෇͖ࣸ૾ʯ let secs = shakutori f (+) (-) 0 as

͜Ε͸ۮવͳͷ͔ • )BTLFMMͰΞϧΰϦζϜΛந৅Խ͢Δͱɺ݁߹ ೋ߲ ԋࢉɺࣸ૾ ͋ͱॳظ ঢ়ଶ ͕ύϥϝʔλԽ͞ΕͯΠϯλϑΣʔεʹදΕΔ • NBQSFEVDF
• ͦͯ͠ΠϯλϑΣʔε͕ʮ୅਺తߏ଄ΈʯΛଳͼΔ

༨ஊ (PPHMFͷ .BQ3FEVDF ͸.BQͱ3FEVDFͷ૊Έ߹ΘͤͰ ଟ͘ͷ໰୊Λղ͘͜ͱ͕Ͱ͖Δ͜ͱʹج͍ͮͨฒྻ෼ࢄܭࢉγεςϜ

)BTLFMM͸࠶ؼతσʔλߏ଄Λσʔλߏ଄ͷجຊͱ͍ͯ͠Δ data List a = Nil | Cons a (List
a) • )BTLFMMͷσʔλߏ଄ uuu ୅਺తσʔλܕʹΑΔ࠶ؼతσʔλߏ଄ • ࠶ؼతσʔλߏ଄ʹదͨ͠࠷খͷૢ࡞͕ NBQͱ SFEVDF GPME – NBQ͸ a -> b Λ֤ཁૉʹద༻͠ɺߏ଄Λอͬͨ··ม׵ ࠶ؼߏ଄ʹର͢Δؔ਺ద༻ͷ࠷খ୯Ґ – SFEVDF GPME ͸ͦͷߏ଄Λյ͠ͳ͕ΒҰͭͷ஋ʹ৞ΈࠐΉ ߏ଄ΛͨͨΉ࠶ؼతύλʔϯͷ࠷খ୯Ґ

ʮࣸ૾ͱ৞ΈࠐΈʯ͸Ͳ͔͜Βདྷͨͷ͔ • -JTQ ʙ ͕Ϧετʹର͢Δ NBQSFEVDFͰɺଟ͘ͷ໰୊Λهड़Ͱ͖Δ͜ͱΛܦݧ తʹൃݟͨ͠ • ؔ਺ܕݴޠͷൃలʹΑΓɺNBQSFEVDF GPME
͸ϦετʹݶΒͳ͍࠶ؼతσʔλߏ଄ʹద ͨ͠ૢ࡞Ͱ͋ΔͱҰൠԽ͞Εͨ • )BTLFMM ʙ ͸ͦΕΒΛཧ࿦͚ͮͯ࠶ߏ੒͠ɺܕΫϥε֊૚ͱͱ΋ʹऔΓࠐΜͩ • 'VODUPS 'PMEBCMF "QQMJDBUJWF .POBE 5SBWFSTBCMF • NBQSFEVDF GPME ͸ )BTLFMMͷʮ࠶ؼʯͱʮߏ଄ԽʯΛ؏֩͘ɺݴޠઃܭͷத৺ʹ͋Δ

https://wiki.haskell.org/wikiupload/8/85/TMR-Issue13.pdf

)BTLFMMͷෆมͳσʔλߏ଄͸ NBQSFEVDF GPME Ͱૢ࡞͢Δ • Ϧετɺ4FUɺ.BQɺ"SSBZ ͳͲͷෆมσʔλߏ଄͸͍ͣΕ΋ 'PMEBCMFɻ·ͨ 'VODUPSͰ ͋ͬͨΓɺͦ͏Ͱͳͯ͘΋
NBQΛ͍࣋ͬͯΔ • ͦΕΒΛجૅʹΞϧΰϦζϜΛ࣮૷͠ɺ۩ମΛύϥϝʔλԽ͍ͯ͘͠ͱࣗવͱ NBQ΍ GPME ΁ͷҾ਺͕ύϥϝʔλͱͯ͠දΕΔ ͜Ε͕ΞϧΰϦζϜͷந৅ʹG΍ ͷΑ͏ͳؔ਺͕͍ͭ΋දΕΔཧ༝ ӬଓσʔλϓϩάϥϛϯάΛࢤ޲ͨ͠৔߹ͷඞવ ˞ඞͣ͠΋͜ͷߏ଄ʹԊΘͳ͍ΞϧΰϦζϜ΍σʔλߏ଄΋ɺ΋ͪΖΜ͋Γ·͢

ͳͥͦΕ͕ɺ୅਺తߏ଄ͱ݁ͼͭ͘ͷ͔ • લड़ͷ௨Γ ࠶ؼతσʔλߏ଄͸ࣸ૾ͱ݁߹ʹࣗવʹؐݩͰ͖Δ • ঢ়ଶͷʮ఻ൖʯͱʮू໿ʯ͸୅਺తੑ࣭Λඞཁͱ͢Δ – ʮ఻ൖʯ֤ঢ়ଶΛ৽͍͠ঢ়ଶʹࣸ͢ ˠࣸ૾ –
ʮू໿ʯෳ਺ͷ݁ՌΛҰͭʹ·ͱΊΔ ˠ݁߹ – ͜Ε͕݁߹తͰͳ͚Ε͹࠶ؼɾޮ཰Խ͕೉͍͠ ˠ୅਺తߏ଄ͷཁ੥ ΞϧΰϦζϜΛந৅Խ͢Δͱࣸ૾ͱ݁߹͕ܭࢉͷຊ࣭తͳߏ੒ཁૉͱͯ͠ݱΕΔ ঢ়ଶۭؒΛू߹ͱΈͳ͢ͱɺ୅਺తߏ଄ʢ'VODUPS .POPJE 4FNJSJOHʣʹରԠ͢Δ )BTLFMMͷܕͱߴ֊ؔ਺͸ɺͦͷߏ଄ΛࣗવʹΠϯλϑΣʔεͱͯ͠࿐ग़ͤ͞Δ ந৅Խ͸ʮܭࢉͷ୅਺ʯΛՄࢹԽ͢ΔաఔͰ΋͋Δ

)BTLFMMͷந৅ͷɺڝٕϓϩάϥϛϯάʹ͓͚ΔҖྗ • ΞϧΰϦζϜͷந৅ʹग़͖ͯͨࣸ૾΍݁߹͸ʮάϥϑͷભҠʯʮঢ়ଶભҠͷࣸ૾ʯͳͲҙຯ ͚ͮ͢Δ͜ͱ͕Ͱ͖Δ – ͨͩͷύϥϝʔλͰ͸ͳ͘ɺղऍΛՃ͑Δ͜ͱ͕Ͱ͖Δ – ͦͯͦ͠ΕΛ୅਺తߏ଄ͷ໨ͰΈͯɺ਺ֶతੑ࣭Λҙࣝ͢Δ͜ͱ΋Ͱ͖Δ • ڝٕϓϩάϥϛϯάͷ໰୊͕ɺͦͷҙຯʹैͬͯߟ࡯͢Δ͜ͱͰղ͚Δ
– ෦෼໰୊Λղ͚ͩ͘Ͱɺશମ͕ղ͚Δ – ͜ͷࢥߟͷϑϨʔϜϫʔΫ͸ಛʹ %1΍άϥϑ୳ࡧ໰୊ͳͲʹ͓͍ͯڧྗͳ෢ثʹͳΔ

໋ྩܕͰΞϧΰϦζϜΛॻ͘ͱ͖ uuuʮͲ͏ಈ͔͔͢ʯ • ؔ৺͸ʮखଓ͖ʯ΍ʮঢ়ଶͷมԽʯʹ޲͘ – ഑ྻΛߋ৽͠ɺม਺Λมߋ͠ͳ͕ΒʮͲ͏΍ͬͯಈ͔͔͢ʯΛߟ͑Δ • Ұ࣌తͳதؒঢ়ଶ ୹໋ͳม਺ Λ࢖ͬͯʮ࠷ऴঢ়ଶʹͲ͏΋͍͔ͬͯ͘ʯʹूத͢Δ
• ΞϧΰϦζϜ͸Ұ࿈ͷ໋ྩͱͯ͠هड़͞ΕΔϨγϐ 🧠 ࢥߟ͸ʮ࣮ߦͷॱংʯʹԊͬͯਐΉɻಈ࡞ΛͳͧΔ͜ͱͰҙຯΛ೺Ѳ͢Δɻ ϓϩηεࢤ޲ɺྲྀΕʹॏ͖Λஔ͘ࢥߟ

for (int j = 0; j <= W; ++j) dp[0][j]
= 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= W; ++j) { if (j >= w[i]) dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]); else dp[i+1][j] = dp[i][j]; } } cout << dp[N][W] << endl;

ؔ਺ܕͰΞϧΰϦζϜΛॻ͘ͱ͖ uuuʮԿΛҙຯ͍ͯ͠Δ͔ʯ • ؔ৺͸ʮߏ଄ʯ΍ʮҙຯʯʹ޲͘ – ˠ͜ͷ NBQ͸ԿΛ͍ࣸͯ͠Δ ͜ͷ GPME͸ͲΜͳԋࢉΛू໿͍ͯ͠Δ •
ܭࢉ͸ෆมͳσʔλߏ଄ʹର͢Δࣸ૾ͱ৞ΈࠐΈͱͯ͠ߏ੒͞ΕΔ • ΞϧΰϦζϜ͸ࣸ૾ͱ݁߹ͷ૊Έ͋Θͤͱͯ͠هड़͞ΕΔࣜ 🧠ࢥߟ͸ʮߏ଄ͱҙຯʯʹԊͬͯਐΉɻࣜͷߏ੒ΛோΊͯશମ૾Λଊ͑Δɻߏ଄ࢤ޲ɺؔ܎ʹॏ͖Λஔ͘ࢥߟɻ ܭࢉΛྲྀΕͱͯ͠௥͏ͷͰ͸ͳ͘ɺҙຯͷ͋Δߏ੒ NBQ GPME ؔ਺߹੒ ͱͯ͠ଊ͑Δɻ Ұ࿈ͷૢ࡞ΛʮԿΛ͔ͨ͠ʯͰ͸ͳ͘ɺʮͲͷΑ͏ͳҙຯͷ͋Δࣸ૾΍݁߹Λఆ͍ٛͯ͠Δ͔ʯͱݟΔ

let dp = accumArrayDP @UArray f max 0 (0, wx)
[(0, 0)] items where f (w, acc) (wi, vi) = [(w, acc), (w + wi, acc + vi)] print $ maximum (elems dp)

ந৅Խָ͕͍͠ͷ͸Θ͔͚ͬͨͲɺڝϓϩΛ )BTLFMMͰ΍ΔϝϦοτ͸ • ͋Γ·͢ΑͰ΋ͦΜͳ͜ͱͲ͏Ͱ΋͍͍͡Όͳ͍Ͱ͔͢ɻϩϚϯͰ͢ – ϝϦοτϝϦοτ͏ΔͤʔΜͩΑ – )BTLFMMͰղ͚ͳ͍໰୊ʹग़ձͬͨ͜ͱ͸ͳ͍ – ʮ)BTLFMMʹΑΔந৅͕ิॿྠʹͳΔʯ͜Ε͚ͩͰ΋े෼ͳϝϦοτ
• ΑΓ۩ମతͳϝϦοτ͸ྫ͑͹uuu – )BTLFMMͷ࠶ؼσʔλܕ Ӭଓσʔλߏ଄ ˠ Ӭଓσʔλߏ଄Λલఏʹͨ͠໰୊ͷ෼ղ – ʮӬଓσʔλϓϩάϥϛϯάͱڝٕϓϩάϥϛϯά ʙ )BTLFMMͰ͕Μ͹Δڝϓϩʯ • IUUQT[FOOEFWOBPZB@JUPBSUJDMFTBCEDBBBC

)BTLFMM͛͢ʔͳͱࢥ͏͜ͱ • ࠓ೔࿩ͯ͠ΔΑ͏ͳ͜ͱΛ෼͔ͬͯͯ )BTLFMMΛ࢖ͬͯདྷͨΘ͚Ͱ͸ͳ͍ • )BTLFMMΛ࢖͍ͬͯͨΒࣗવͱࠓ೔࿩ͨ͠Α͏ͳந৅Խͷ࣮૷ʹͳͬͨ • ͦͷந৅ԽͷҙຯΛߟ͍͑ͯΔ͏ͪʹࠓ೔࿩ͨ͠Α͏ͳߟ࡯ʹࢸͬͨ • )BTLFMMΛ΍ͬͯΔͱ͜͏͍͏ܦݧΛԿ౓΋͢Δ
– ·ΔͰϓϩάϥϛϯάݴޠͱ͍͏ಓ۩͕ɺΑΓྑ͍ந৅ͱීว΁ͷಓےΛࢦࣔͯ͘͠͠Ε͍ͯΔΑ͏ͳײ͡

࿩ͨ͜͠ͱ • )BTLFMM ͰڝٕϓϩάϥϛϯάʹࢀՃ͍ͯ͠ΔɻΞϧΰϦζϜΛந৅Խ͢Δͱɺͦͷ࣮૷͕ ࣅͨΑ͏ͳΠϯλϑΣʔεʹͳΔ͜ͱΛܦݧͨ͠ – ߴ֊ؔ਺ͱͯࣸ͠૾ Gͱ݁߹ͷೋ߲ԋࢉ͕ύϥϝʔλͱͯ͠Α͘දΕΔ • ͦΕ͸ۮવͳͷ͔ɺ͍΍ɺۮવͰ͸ͳ͍
– )BTLFMMͷࠜఈʹ͋Δ࠶ؼσʔλߏ଄ɺͦΕʹ࠷దͳૢ࡞Ͱ͋Δࣸ૾ͱ৞ΈࠐΈ NBQSFEVDF • ࣸ૾ͱ৞ΈࠐΈʹΑΔؔ਺ͷΠϯλϑΣʔε͔ΒΞϧΰϦζϜͷ୅਺తߏ଄͕ݟ͑Δ • ؔ਺ܕϓϩάϥϛϯάɺ)BTLFMM͸ΞϧΰϦζϜΛΑΓந৅౓ߴ͘ଊ͑ΔࢥߟΛิॿͯ͘͠ ΕΔ

͓·͚

NJTD • ෆมͳσʔλߏ଄ͱ NBQSFEVDFͰશ෦͍͚Δͷ – ͍͍͑ɻύϑΥʔϚϯεͷ؍఺͔Β .VUBCMF"SSBZ͕ඞཁͳ৔໘͸͋Γ·͢ • 6OJPO'JOEɺηάϝϯτ໦ɺ஗ԆධՁηάϝϯτ໦ͳͲͷ࣮૷ –
.VUBCMF"SSBZͷૢ࡞΋Ϟφυͷݟ஍͔ΒݟΕ͹ NBQSFEVDFతͳ΋ͷͱͯ͠ଊ͑Δ͜ͱ͸Ͱ ͖Δ͕ɺͦΕΛѻ͏ਓؒͷϝϯλϧϞσϧͱͯ͠͸໋ྩܕతͳૢ࡞ – .VUBCMF"SSBZ͸ඇ࠶ؼతͳݻఆαΠζͷઢܗߏ଄Ͱ͋Γɺ୅਺తσʔλܕͰએݴ͞ΕΔ࠶ؼత σʔλߏ଄ͱ͸ҟͳΔ΋ͷ • ೖग़ྗ΍ཚ਺ಉ༷ͷɺ֎ք 3FBM8PSME ͷӨڹԼʹ͋Δ෭࡞༻తͳଘࡏ ֎෦ࢿݯ ϝϞϦ ͱͷڮ౉͠૷ஔ • .POPJEͱ͔ 4FNJHSPVQͱ͔ͷܕ࢖࣮ͬͯ૷͠ͳ͍ͷ – ࢲ͸࢖ͬͯ·ͤΜ͕ɺ࢖ͬͯ៉ྷͳந৅Λ࣮૷͍ͯ͠Δ "U$PEFSͷઌഐํ΋͍·͢ – ࢲ͸׳Εͱهड़ͷָ͞Λ༏ઌ͍ͯ͠·͢

ܕγεςϜ͸ϓϩάϥϛϯάݴޠͷૢ࡞ମܥ΍දݱྗͦͷ΋ͷΛܗ࡞Δϝλߏ଄

Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング

Haskell でアルゴリズムを抽象化する / 関数型言語で競技プログラミング

More Decks by Naoya Ito

Other Decks in Programming

Featured

Transcript