ABC257 A～E をHaskellで

A - A to Z String 2

問題 ABC257A

シグネチャを決める。

abc257a :: Int   -- N
        -> Int   -- X
        -> Char  -- 答え

$N$ 文字ごとに次の文字に移るので、0始まりの位置を $N$ で割った答えが文字を決める。

結果

abc257a n x = ['a'..'z'] !! (div (pred x) n)

B - 1D Pawn

問題 ABC257B

シグネチャを決める。

abc257b :: Int     -- N
        -> Int     -- K
        -> Int     -- Q
        -> [Int]   -- Ai
        -> [Int]   -- Li
        -> [Int]   -- 答え

ルールを読むと、コマの追い越しは起きないので、$i$ 番目のコマの位置 $P[i]$ を配列で管理すれば十分である。初期値はそれぞれ $A_i$ となる。
$P[L_i] + 1 = P[L_i + 1]$ が移動できない条件。
一番右に到達できるのは $A_K$ だけだが、$P[K+1] = N+1$ という番兵を置いておけば、1つめの条件に関する処理が不要になる。

結果

import Data.Array

abc257b n k q as ls = init $ elems pq
  where
    p0 = listArray (1, succ k) $ as ++ [n+1]
    pq = foldl step p0 ls

step p l
  | succ pl == p ! succ l = p            -- 詰まっていて進めない
  | otherwise             = p // [(l, succ pl)]   -- 一歩進む
  where
    pl = p ! l

一点更新は Data.IntMap の方が速いので、速度を重視してそちらを使う手もある。

C - Robot Takahashi

問題 ABC257C

シグネチャを決める。

abc257c :: Int     -- N
        -> String  -- S
        -> [Int]   -- Wi
        -> Int     -- 答え

大人が $A$ 人とする。子供は $N-A$ 人となる。
$X$ を十分小さな値 $X_0 \leq \min W_i$ に設定したとき、つまり全員を大人と判定するとき、$f(X_0) = A$ となる。
$X$ を大きくしていって、大人の体重をひとつ超えると、大人と判定するべき一人を子供と誤って判定するようになるので、 $f$ の値は $1$ 減少する。
逆に、子供の体重をひとつ超えると、今まで誤って大人と判定していた一人を子供と正しく判定するようになるので、$f$ の値は $1$ 増加する。
つまり、この増減を累積すれば、それぞれの $X$ での $f(X)$ の値がわかるので、その最大値をとればよい。

結果

import qualified Data.IntMap as IM

abc257c :: Int -> String -> [Int] -> Int
abc257c n s ws = maximum $ scanl (+) f0 $ elems deltas
  where
    f0 = length $ filter ('1' ==) s
    deltas = fromListWith (+)
      [(w, if c == '1' then -1 else 1) | (c,w) <- zip s ws]

実際には $N$ が大きいので入力の読み込みには Data.ByteString を用いるべきで、すると $S$ も ByteString になるので少し変わる。

D - Jumping Takahashi 2

問題 ABC257D

シグネチャを決める。

abc257d :: Int               -- N
        -> [(Int,Int,Int)]   -- xi,yi,Pi
        -> Int               -- 答え

ジャンプ台を頂点とし、それぞれのジャンプ台から他のジャンプ台へ飛べるかどうかは、$S$ の値によって辺の有無が変わる有向グラフと見なせる。そして、いずれかの頂点から他の全ての頂点へ到達可能なグラフを作る最小限の $S$ が求めたい値。

辺が使えるようになる $S$ の大きさの順にソートして、グラフに順に追加していき、全ての頂点に到達可能な頂点が見つかった時点の辺が必要とする $S$ の値がそれ、という方針で進める。

個々の頂点 $1 \leq n \leq N$ について、「その頂点から到達可能な頂点の集合」$O[n]$ と、逆に「その頂点へ到達可能な頂点の集合」$I[n]$ の両方を考える。最初は全て自分自身のみからなる。
ここに辺 $(u,v)$ を追加すると：

• $u$に到達できる全ての頂点は、$v$ から到達できる全ての頂点へも到達できるようになる
• $v$ から到達できる全ての頂点へは、$u$ に到達できる全ての頂点から到達できるようになる

前者が $O$ を拡大し、そのとき $I$ を利用する。後者は $I$ を拡大するときに $O$ を使う。
$O$ に全体集合が現れることが終了条件である。

$v$から到達できる頂点の中に $u$ へ到達できる頂点があって循環が起きて、一度の操作だけでは到達可能な頂点を全て挙げることができないのではないか？と心配になるが、もしそうなったら、（その時点での）最短経路として辺 $(u,v)$ を複数回通るような経路を必要とする頂点の対があるということで、そんなことはないので問題はない。

結果

頂点集合は素直に Data.IntSet を、$O,I$ は一点更新の速度を求めて Data.IntMap を用いて、immutableに実装した。

import qualified Data.IntSet as IS
import qualified Data.IntMap as IM
import Data.List

abc257d :: Int -> [(Int,Int,Int)] -> Int
abc257d n xyps = loop os0 is0 edges
  where
    os0 = IM.fromAscList [(i, IS.singleton i i) | i <- [1..n]]
    is0 = os0
    ixyps = zip [1..] xyps
    edges = sort
      [ p
      | (u,(x,y,p)):jzwqs <- tails ixyps
      , (v,(z,w,q)) <- jzwqs
      , let dist = abs (x - z) + abs (y - w)
      , p <- [(divrup dist p, (u,v)), (divrup dist q, (v,u))]
      ]
    loop os is ((s, (u,v)):edges)
      | reached   = s
      | otherwise = loop os1 is1 edges
      where
        ov = os IM.! v
        iu = is IM.! u
        osAdd = [(i, IS.union ov (os IM.! i)) | i <- IS.elems iu]
        reached = any ((n ==) . IS.size . snd) osAdd
        os1 = IM.union (IM.fromAscList osAdd) os -- 上書き更新のために向きが重要
        isAdd = [(j, IS.union iu (is IM.! j)) | j <- IS.elems ov]
        is1 = IM.union (IM.fromAscList isAdd) is

-- @gotoki_no_joe
divrup x y = negate $ div (negate x) y -- 切り上げ除算

この解法は公式にある3つめのkyopro_friends氏による解説と同じ方針のようだ。DPは特に意識しなかったが。
到達可能性について前引きと逆引きの$O,I$を使う代わりに、到達可能フラグの二次元の表を使っているのだろうか。

C++などの高速な言語であれば比較的余裕を持って(1秒未満で)ACすることができます。

ということだが、Haskellでも657msでできた。
1回のステップで全ての頂点間の到達可能フラグを舐めるので $O(N^2)$ （ここの解法では IntSet.union が $O(N+M)$ なので同じ）、完全グラフなので辺は $N^2$ あるため、全体では $O(N^4)$ かかる。

1,2つめの公式解説は、$S$ を何らかの値に固定してグラフを決めたとき、ワーシャルフロイド法、または開始頂点総当たりでの再帰的探索により条件を満たすかを判定できる、これを $S$ に関して二分探索する、という方針を説明している。これだと $O(N^3 \log S)$ となる。
tatyam氏による解説のやり方ではなんと $O(N^2)$ で済むらしい。
cirno3153氏による解説は「強連結成分分解」を使って、$O(N^2 \log S)$ で解いている。

E - Addition and Multiplication 2

問題 ABC257E

シグネチャを決める。

abc257e :: Int     -- N
        -> [Int]   -- Ci
        -> String  -- 答え

答えは64ビット整数にすら収まらないので、Int で返すわけにはいかない。
逆にこれがヒントで、桁ごとに上位から文字列として答えを返すべきで、数値としての計算はしないと言っている。

数字のカードがそれぞれ値段をつけて売られていて、枚数制限はないが所持金の限度がある、その中で最大の10進表記の数を作れ、と言っている。
数を大きくするには、なるべく上の桁で大きな数字を使うべきだが、それよりもともかく桁数を稼ぐべきである。"9" よりも "11" の方が大きい。

なのでまずは最も安い（ものの中で最大の）数字を買えるだけ買って並べる。問題の例1だと、"5" が一番安く2枚買えるので "55" が作れる。しかし手元にはお釣りが1円ある。この残額で、"5"の代わりになるべく大きい数字カードを買えるだけ買い、上の桁に入れる。例1では "9" が3円なので最初の "5" の代わりに "9" が1枚だけ買えるのでそうして、結局 "95" となる。

結果

abc257e n cs = loop q r
  where
    (cmin, iminN) = minimum $ zip cs [-1,-2..] -- 最安数字の値段とその数字のマイナス
    imin = negate iminN                        -- 最安数字
    (q, r) = divMod n cmin                     -- 桁数と残額
    cis = reverse $ drop imin $                -- 他の数字を買うために必要な差額
      [(c - cmin, d) | (c,d) <- zip cs digits] -- iminより大きいもの限定、数字の大きい順
    loop cnt rest =                            -- cnt:出力する残り桁数、rest:残額
      case filter ((rest >=) . fst) cis of
        [] -> replicate cnt (digits !! imin)   -- 買えるものが無ければ残りは imin を並べる
        (c,d):_ -> d : loop (pred cnt) (rest - c) -- 最良の数字を1文字買う

digits = ['1'..'9']

手書きの再帰 loop をなるべく減らしたいのだけど、つい使ってしまう。