ABC017をHaskellで

• A : 整数演算
• B : 有限オートマトン
• C : 累積和による積分で関数復元
• D : DP+尺取り法、（別解：累積和、セグメント木）

A - プロコン

問題 ABC017A

シグネチャを決める。少し無精する。

abc017a :: [(Int,Int)] -- si,ei
        -> Int         -- 答え

記述そのままだと $\displaystyle \sum_{i=1}^3 \left ( s_i \times \frac{e_i}{10} \right )$ を計算することになる。
公式の解説は、整数と浮動小数点数の間の型変換をほどほどに行うC言語を前提に、この式のとおりに計算し、しかし浮動小数点数の計算誤差を切り捨て丸めで真値に補正するため

小さな数(0.1とか)を足してから切り捨てると安全です。

いやそれはどうかと思うですよ。

$s_1,s_2,s_3$は10の倍数であることが保証されていることを使って、
$\displaystyle s_i \times e_i \div 10 = \frac{s_i}{10} \times e_i$
と式変形してやれば、余りを出すことなく$s_i$を10で割ることができる。

さらに、（古い感覚だと）割り算は時間のかかる計算なので、3つの課題それぞれについて割る代わりに、最後に一度だけ割るようにできる。
結局、
$\displaystyle \sum_{i=1}^3 \left ( s_i \times \frac{e_i}{10} \right ) = \frac{1}{10} \times \sum_{i=1}^3 s_ie_i$
細かいことを言うと、$\sum$の計算で桁あふれが起きると台無しなので、そうでないことを確認する必要がある。

結果

abc017a = flip div 10 $ sum $ map (uncurry (*))

B - choku語

問題 ABC017B

シグネチャを決める。

abc017b :: String -- X
        -> Bool   -- 答え

パターンマッチを用いて、文字を消費していくオートマトンを書くことで実現できる。

結果

abc017b "" = True
abc017b ('c':'h':x) = abc017b x
abc017b ('o':x) = abc017b x
abc017b ('k':x) = abc017b x
abc017b ('u':x) = abc017b x
abc017b _ = False

C - ハイスコア

問題 ABC017C

シグネチャを決める。$l_i,r_i,s_i$ については横着する。

abc017c :: Int     -- N
        -> Int     -- M
        -> [[Int]] -- li,ri,si
        -> Int     -- 答え
abc017c n m lrss = ...

Mが16ぐらいまでなら、集合のビット表現を用いて、宝石の取得状況に対して最大のスコアをDPするというアプローチでも行けるだろう。
ただ、遺跡に対して得られる宝石はバラバラでなく区間なので、これは無駄に贅沢。

遺跡を一つ攻略すると、ある区間の宝石が入手される。
全ての宝石をコンプしてはいけない、という制約があるので、つまり、どれか一つでもいいから取得しないような攻略のパターンを発見する必要がある。

取得しない宝石を番号Xのものと固定したとする。
宝石Xを取らないようにするには、宝石Xが手に入ってしまう遺跡全ての攻略をあきらめる必要がある。宝石Xが手に入らない遺跡は全て攻略してよい。このときのスコアは、全ての遺跡のスコアの合計 $S = \sum s_i$ から、諦める遺跡のスコアの合計を引いた値になる。

Xを1からMまで振ってスコアを求めて最小値を得る、ではないやり方をしないといけない。

宝石の番号を横軸、遺跡の番号を縦軸にとった表を考える。
この表の行$i$の列$l_i$から$r_i$に$s_i$を書き込む。
この表を列について足し合わせた値が、その列の宝石をあきらめたときに得られなくなるスコアになる。

このスコアのグラフは、$x < l_i$ で 0、$l_i \leq x \leq r_i$ で $s_i$、$r_i < x$ で 0というステップ関数のグラフを足し合わせた形になる。
これは、ステップ関数の微分、つまり $x = l_i$ で $s_i$、$x = r_i$ で $- s_i$、それ以外で0という導関数を全て足し合わせ、それを累積和で積分することで復元できる。

結果

積分の初期値をスコアの総和、ステップ関数を凹な形にすることで、直接スコアを求める。

import qualified Data.IntMap

abc017c :: Int -> Int -> [[Int]] -> Int
abc017c n m lrss = maximum $ scanl1 (+) $ IM.elems m
  where
    s = sum [s | _:_:s:_ <- lrss]
    m = IM.fromListWith (+) $
        (1, s) : -- 積分の初期値
        [p | l:r:s:_ <- lrss, p <- [(l,- s)] ++ [(succ r,s) | r < m]]

[(succ r,s) | r < m] は、範囲外である$M+1$の値（$S$になる）を累積和が吐き出さないようにしている。

D - サプリメント

問題 ABC017D

シグネチャを決める。

abc017d :: Int   -- N
        -> Int   -- M
        -> [Int] -- fi
        -> Int   -- 答え

自分の解法

概要

ある日にサプリ番号$i$から飲み始めたとき、次の同じ味のサプリメントは番号$j$であるとすると、$j$の手前までしか飲めない。さらに、$i+1$から$j-1$の間の全てのサプリについても同様なので、それらの値の最小値の手前まで、が飲んでいい最も遠い位置となる。そこまでなら、どこで止めてもよい。

「次に$i$から飲み始めるやり方の場合の数」を配列に入れる。1については1通りである。
上の$i$についての場合の数を、$i+1$から$j-1$までに配って足し合わせる。
$N+1$を飲み始めるやり方の場合の数が、要求されている答えである。

このままだと配るDPなので、集めるDPにすることを考える。
1からスタートして$N+1$に至る経路の数と、$N+1$からスタートして、逆回しに1に至る経路の数は同じ。つまり、$N+1$の場合の数を1とし、$i$は$i+1$から$j-1$までの和とする。

詳細

まず、それぞれのサプリについて、次に同じ味のサプリが何番なのか（存在しない場合は$N+1$）という番号を探す。これを配列$next[1～N]$に入れる。個々に線形探索すると$O(N^2)$かかってしまう。

味ごとに、最後に見た位置を記憶する書き換え可能配列$seen[1～M]$を持って、先頭から、位置$i$に色$f_i$を見たとき、$next[seen[f_i]] = i$, $seen[f_i] \leftarrow i$ と更新する。最後に全てのまだ未定義な$next[j]$ は全て$N+1$に設定する（もしくはこれを初期値とする）という命令的な手順がわかりやすい。これは$O(N)$でできる。

immutableにやるには、味ごとに出現した位置の昇順のリスト（ただし全てに$N+1$を含む）を作り、その隣り合う対$(i,j)$について$next[i]=j$とする。おそらくソートが支配的で$O(N \log N)$かかる。

next = array (1,n) [(i,j) | is <- elems posArr, i:j:_ <- tails $ sort is]
posArr = accumArray (flip (:)) [n+1] (1,n) $ zip fs [1..]

配列$next$に基づいて、番号$i$から飲み始めて、いずれかの重複が起きる最小の番号を持つ配列$span$は、$\displaystyle \min_{i \leq j < next[i]} next[j]$ と求められる。

span = listArray (1,n)
       [ minimum [next ! j | j <- [i .. pred $ next ! i]]
       | i <- [1..n]]

$N+1$に至る経路の個数を数えるDP配列$count$は、初期値$count[N+1] = 1$とし、$i$に対しては、$i$番目だけを飲んで次は$i+1$から～$span[i]$ の手前までを飲んで次は$span[i]$から、の範囲全ての場合の数の和になるので、$\displaystyle count[i] = \sum_{j=i+1}^{span[i]} count[j]$ と定義できる。

count = listArray (1,n+1) $ map countf [1..n] ++ [1]
countf i = reg $ sum [count ! j | j <- [succ i .. span ! i]]

reg x = mod x 1000000007

abc017d n m fs = count ! 1

落とし穴

上の実装は30点までしか得られない。
明瞭な定義に基づいて素朴に実装したとき、実は時間のかかる計算を2つ見落としている。

sum

countf の中で、countの区間 [succ i .. span ! i] に対して sum を行っているが、これでは全ての区間について、区間の全ての要素に対して足し算をすることになり、 $O(N^2)$ になる。
このような計算を高速化するには、累積和を用いる。ただし、countは後ろから値が定まっていく配列なので、前からの累積和をとってしまうと、依存が循環してしまう。なので累積和も後ろから取るようにする必要がある。

countAcc = listArray (1,n+1) $ scanr (\x y -> reg $ x + y) 0 $ elems count

countf i = reg $ countAcc ! (succ i) - countAcc ! (succ $ span ! i)

これで$O(N)$になった。

minimum

span の定義で、next の区間 [i .. pred $ next ! i] に対して minimum を行っている。これも全ての区間について、区間の全ての要素の比較を行うことになり、$O(N^2)$かかる。
これを高速化するには、セグメント木が利用できる。値の更新は必要ないので少々大がかりすぎる道具なきらいはある。

次のようなAPIで、immutableなセグメント木が定義されているとする。

-- セグメント木を作る
-- 引数：データ列(添え字は0始まり), モノイド演算, 単位元
makeSegTree :: [a] -> (a->a->a) -> a -> SegmentTree a

-- 第a要素から第b要素の手前までを演算した結果を求める
querySegTree :: SegmentTree a -> Int -> Int -> a

するとspanは次のように定義できる。

nextT = makeSegTree (0 : elems next) min maxBound

span = listArray (1,n)
       [ querySegTree nextT i ni
       | (i,ni) <- zip [1..] (elems next)]

これで$O(N \log N)$になった。

結果

AC, 220ms, 58MB ：ただし next はmutable arrayを用いた手法で求めている。

解説の解法

公式の解説には、尺取り法を用いて$O(N+M)$で解くことができる、とある。
が、言葉遣いが少々独特で、部分点解法の時点で何を言っているのか微妙に意味が取りづらい…（多分人のことは言えない）

$i$番目まで消費するやり方の場合の数を持つ配列$count[0～N]$を構築する。
初期値は$count[0]=1$、問題の答えは$count[N]$となる。
$count[i]$は、それより手前のどこか$k$番目から、$i$番目までを一度に消費するやり方と、それ以降$i$未満の位置から同様に、の全ての和になるので、$count[i] = \sum_{k\leq j<i} count[j]$ となる。

この$k$は（$k$番目は消費済みなので）$k+1$から$i$までが味の重複のない最大の区間である。
さらに考えると、ある$i$に対する$k$と、別の$i'$に対する$k'$は、$i < i'$ ならば $k \leq k'$ が必ずいえる。
つまり、$i$を増やしたとき$k$が減ることはない。
そこで、$k$から$i$の区間を、尺取り法で追跡することを考える。
右を伸ばそうとしたとき、その味が区間に既に存在する味ならば、それを追い出せるまで左を縮める。
存在しない場合は、右を伸ばすことができる。このとき、区間の$count[]$の総和が新たなマスの値になる。
尺取り虫の状態として、区間に存在する味の集合と、区間の$count[]$の総和を管理して、右が$N$に到達したとき仕事が完了する。

味集合を IntSet、$count$ の内容はそのまま遅延配列に置く形で実装した。
前者はmutableなフラグ配列で表現すれば$O(1)$アクセスになるが、一応Data.IntSetのmember,insert,deleteも定数時間（要素数$n$、計算機のビット幅$W$として$O(\min(n,W))$）で動く。

abc017d :: Int -> Int -> [Int] -> Int
abc017d n m fs = count ! n
  where
    count = listArray (0,n) $ 1 : loop 0 1 1 IS.empty fs fs
    loop :: Int  -- k : 左端の位置
         -> Int  -- i : 右端、次に値を決めるcount[i]の位置
         -> Int  -- s : kからi-1までのcount[]の総和
         -> IS.IntSet -- is : k+1からiまでにある味の集合
         -> [Int]  -- fks : kの味、以降のリスト
         -> [Int]  -- fis : iの味、以降のリスト
         -> [Int]  -- 答え count[1]～count[N] の値を順に
    loop k i s is fks fis
-- 右の味が尽きたなら、全てを計算し終えた
      | null fis = []
-- 右の味が既にあるなら、左を縮める
      | IS.member fi is = loop (succ k) i (reg $ s - count ! k) (IS.delete fk is) (tail fks) fis
-- まだないなら、取り込んで伸びる
      | otherwise = s : loop k (succ i) (reg $ s + s) (IS.insert fi is) fks (tail fis)
      where
        fi = head fis -- 次に加入する味
        fk = head fks -- 次に離脱する味

結果

AC, 140ms, 37MB
尺取り虫 loop の型シグネチャ（のコメント）を省略したら正味10行程度で書けてしまうとはびっくり。