ABC338 A～F をHaskellで

A - Capitalized?

問題 ABC338A

Regular Expressionがあればそれで一発？

シグネチャを決める。

import Data.Char

abc338a :: String -- S
        -> Bool   -- 答え
abc338a (c:cs) =isUpper c && all isLower cs

B - Frequency

問題 ABC338B

シグネチャを決める。

abc338b :: String -- S
        -> Char   -- 答え

結果

配列で数える。
最頻の文字が複数ある場合に対応するため、最大個数を求めるステップと、その個数だけある文字を取り出す段階を分ける。

import Data.Array

abc338b :: String -> Char
abc338b cs = head [c | (c,k) <- assocs cnt, k == x]
  where
    cnt = accumArray (+) 0 ('a','z') [(c, 1) | c <- cs]
    x = maximum $ elems cnt

個数を左、文字を右にした対の最大値を取り出すと、最頻の文字の中でアルファベット順で最も遅いものが選ばれてしまうので、個数をマイナスにして最小値を取り出すと唯一に決まる。

import Data.Array
import Data.Tuple

abc338b :: String -> Char
abc338b cs = snd . minimum . map swap . assocs $
             accumArray (+) 0 ('a','z') [(c, -1) | c <- cs]

C - Leftover Recipes

問題 ABC338C

シグネチャを決める。

abc338c :: Int  -- N
        -> [Int] -- Qi
        -> [Int] -- Ai
        -> [Int] -- Bi
        -> Int   -- 答え

とりあえず料理Bを無視して料理Aだけ作るとしたとき、作れる個数は $Q_i / A_i$ の最小値。
Aを作る個数を0からこの上限まで試して、残りの材料で作れる料理Bの個数も同様に導く。
合計の最大値をとる。

結果

abc338c _n qs as bs = maximum [s + tfun s | s <- [0..smax]]
  where
    smax   = minimum [div q a | (q,a) <- zip qs as, a > 0]
    tfun s = minimum [div (q - a * s) b | (q,a,b) <- zip3 qs as bs, b > 0]

別解

$s = 0,1,\dots$について $Q_i - s A_i$ を求める代わりに、$Q_i$から$A_i$を引くことを繰り返す。$s$の最大値は引けなくなったときがそれなので自然に判る。

abc338c :: Int -> [Int] -> [Int] -> [Int] -> Int
abc338c _n qs as bs =
    maximum $
    zipWith (+) [0..] $       -- Aを作る個数を加える
    map bfun $                -- Bの作れる個数
    takeWhile (all (0 <=)) $  -- どれかがマイナスになったら終了
    iterate afun qs           -- QiからAiを引くことを繰り返す
  where
    afun xs = zipWith (-) xs as -- Aをもう一つ作る
    bfun rs = minimum [div r b | (b,r) <- zip bs rs, b /= 0] -- Bの作れる個数

takeWhile～iterateはunfoldrでかっこよくなるけど、そこまで凝らなくてもね。

    qs : unfoldr step qs -- QiからAiを引くことを、引けなくなるまで繰り返す
  where
    step qs
      | all (0 <=) qs1 = Just $ (qs1, qs1)
      | otherwise = Nothing
      where
        qs1 = zipWith (-) qs as

D - Island Tour

問題 ABC338D

シグネチャを決める。

abc338d :: Int  -- N
        -> Int  -- M
        -> [Int] -- Xi
        -> Int   -- 答え

島は数珠つなぎになっているので、元々はどちら向きにでも回ることができる。島の番号が増える向きを「順回り」、逆を「逆回り」と呼ぶことにする。
橋をどれか一つ落とすと、どちらか片方でしか行けなくなる。（逆に言うと、どちらかの回りが必ず妨害される。）
島$A$と$B$ ($A < B$)の間を移動するとき、順回りで渡る橋は$F = B - A$本、逆回りでは$R = N - F$本。
順回りで使う橋のどれかを落としたとき、逆回りの行程が必要になる。順回りで使う橋とは、橋$A$から$B-1$のこと。
逆に、それ以外の橋を落としたときは、順回りの行程が必要になる。全ての橋について、どちらかの行程が必ず必要である。
全ての行程について、その橋を落としたときに必要になる行程を足し込むことで、ツアー全体の行程が得られる。その最小値が求める値。

しかしこれを素朴にやると、要素$N$個の配列に$M$回の足し込みを行うため$O(NM)$で間に合わない。

足し込むべき行程は、橋$A$から橋$B-1$が$N - F$で、それ以外、つまり1から$A-1$までと$B$から$N$までは$F$で一定値である。1から順に見て変化するのは1,X,Yのとき。
これは累積和による積分の出番。

結果

import Data.Array

abc338d :: Int -> Int -> [Int] -> Int
abc338d n _m xs = minimum $ scanl1 (+) $ elems da  -- 累積して最小値をとる
  where
    da = accumArray (+) 0 (1,n)
      [ p
      | (x0, x1) <- zip xs (tail xs)         -- Xi, Xi+1
      | let (a, b) = (min x0 x1, max x0 x1)  -- A < B にする
      , let f = b - a                        -- F
      , let r = n - f                        -- R
      , p <- [ (1, f)                        -- 1～にFを足す
             , (a, r - f)                    -- A～にRを足すように差分をインパルス
             , (b, f - r)                    -- B～にFを足すように差分をインパルス
             ]
      ]

別解

ユーザ解説 by AngrySadEightは、思いがけない切り口からの解法だった。

橋$N$を落としたときの総行程は、上で言う順方向の距離の総和として計算できる。

その他の橋を落とすことを一般化して考える代わりに、橋$N$が落ちたまま、島の方を一つ手前にずらす。つまりそれぞれ1減らす、ただし$0$は$N$に戻す。
すると、1だった島が$N$になることにより、この島発着の行程が全て、その時点の順方向から逆方向に切り替えることになる。
より詳しく見ると、最初の番号で$X$と$Y$を結ぶ行程$(X < Y)$があったとして、ずらすことで$X$が1から$N$に変わるとき、この行程は初めて、逆方向に切り替えられる。
さらにずれて今度は$Y$が1から$N$に変わるとき、逆方向だった行程が順方向に戻される。
一回転させることで、全ての行程が2度切り替えを受ける。

元の島$X$が1から$N$に変わるときに起きる行程の変化量を調べておき、初期状態の順方向の総和を初期値として累積和をとると、それぞれのステップでの行程の距離が得られるので、その差以上値をとればよい。

abc338d :: Int -> Int -> [Int] -> Int
abc338d n m xs = minimum $ scanl1 (+) $ elems diffs
  where
    diffs = accumArray (+) 0 (0,n)
      [ p
      | (x0, x1) <- zip xs (tail xs)     -- Xi, Xi+1 の間の行程
      , let d = abs $ x - y              -- 行程の長さ
      , let d1 = n - d - d               -- 1度めの切り替えでの増分
      , p <- [ (0, d)          -- 初期状態での総行程はdの総和
             , (min x y, d1)   -- 1度めの切り替え
             , (max x y, -d1)  -- 2度めの切り替えで元に戻る
             ]
      ]

ひとつめの解法とこの別解とで、根底の考え方は違うのに、結果として出てきたコードはどちらも累積和を用いた、似たような計算をするのは興味深い。

E - Chords

問題 ABC338E

シグネチャを決める。

abc338e :: Int     -- N
        -> [[Int]] -- Ai, Bi
        -> Bool    -- 答え

フレンズさんのtweetの絵が判りやすい。どこで切っても同じで、開いて一本にしたときに線が重ならないとは、（全て異なる文字による）括弧の対応がとれていることと同じなので、スタックで判定できる。

このとき、切る位置はもちろん自然にNと1の間にすると、AとBの小さい方が先に出現し、大きい方が後に出現する位置だと判るので、先に出現する方が開き、後が閉じ括弧となり、「今K番の括弧は開き中かどうか」を、スタックの中を探したり、別に表を持ったりする必要すらない。

結果

import Data.Array

abc338e :: Int -> [[Int]] -> Bool
abc338e n abs = loop [] $ elems circle
  where
    circle = array (1, n + n)
             [ p
             | (i, a:b:_) <- zip [1..] abs
             , p <- [ (min a b,  i)     -- 開き括弧
                    , (max a b, -i)]]   -- 閉じ括弧
    loop _ [] = False                                -- 最後まで交差はなかった
    loop    js  (i:is) | i > 0      = loop (i:js) is -- 開き括弧はpush
    loop (j:js) (i:is) | i + j == 0 = loop     js is -- スタックトップと一致する閉じ括弧はpop
                       | otherwise  = True           -- 違うなら、交差した。

公式解説のコードは、開きか閉じかを示す0/1と番号のタプルで真面目にやっていた。
符号を流用するこれの方がズボラだ…

F - Negative Traveling Salesman

問題 ABC338F

シグネチャを決める。$U_i,V_i,W_i$は手抜きする。

abc338f :: Int       -- N
        -> Int       -- M
        -> [[Int]]   -- Ui, Vi, Wi
        -> Maybe Int -- 答え 経路がないとき Nothing

考える

さっぱりわからなかったのでアライさんのヒントを見る。

F問題は巡回セールスマンなのだ！　最初にワーシャルフロイドで全点間最短経路問題を求めておけばあとは普通にbitDPやるだけなのだ！

「普通に」でどうしていいかまだ判らなかったので公式解説を見た。

つまり、「意図的に目的地として設定して移動した先の頂点の集合だけを考える。次の目的地まで行く経路に、初めて通る頂点があるかもしれないが、それは無視してよい。
なぜなら、その頂点も意識して通った方が低コストなら、そのように選んだ順路もどこかで意図的に探索されるから。」

なるほど。最小コストをDPして、その添え字は次のようにする。

• 意図的に到達済みの頂点集合 $S$ 、$N \leq 20$なのでビット表現で扱う
• 訪問を終えて最後に至った頂点 $i$
  （頂点が頂点集合に含まれないような状況については、コスト無限大とする）

すると、$cost[S][i]$は、

• $i \not\in S$ のときは $\infty$
• 到達済み頂点が1つ $|S| = 1$ のときは当然0
• 複数のときは、$S$の$i$意外に到達済みの全ての場合に対して、何らかの終点$j$から$i$に向かったときのコストの最小値 $\displaystyle \min_{j \in S, j \neq i} \left ( cost[S \setminus \{i\}][j] + dist[j][i] \right )$

とすることで集めるDPで計算できる。
bitDPでは、部分集合を表す整数はより小さな値になるので、添え字の小さい方から順に値を確定できるのが面白い。

ワーシャルフロイド法は骨の髄まで命令型配列なのでSTモナドで計算し、結果をrunSTArrayでimmutable配列として取り出し、Arrayを使った暗黙の集めるDPで書いてみた。
が、どうあがいてもTLEする。

結局、ワーシャルフロイド法の結果をSTArrayのまま持ち、コストのDPもSTモナドで命令的に回してやったら2616ms, 175MBでACできた。
上のArray実装のときの集める関数 costf が原型を保って流用できてはいるが、本体の計算を関数型でできなかったのはくやしい。

G - evall

問題 ABC338G

シグネチャを決める。

import qualified Data.ByteString.Char8 as BS

abc338g :: BS.ByteString  -- S
        -> Int            -- 答え

皆目見当も付かない。

すごいHなの人のtweet の「すごい綺麗」さを理解するためには何とかするしかない。
（といっても、公式解説のコード例もユーザ解説のコード例も、問題の難解さに見合わないコンパクトさで言葉が出てこない。

降参。