ABC261 A～E をHaskellで

A - Intersection

問題 ABC261A

シグネチャを決める。

abc261a :: [Int]  -- L1,R1,L2,R2
        ->  Int   -- 答え

重なりがあると仮定して、重なっている区間の左端は $\max(L_1,L_2)$、右端は $\min(R_1,R_2)$ である。右端から左端を引けば区間の長さになるはずだが、それが負になったら実際には重なりがなかったということになるので、その場合は0に切り上げる。

結果

abc261a [l1,r1,l2,r2] = max 0 $ min r1 r2 - max l1 l2

B - Tournament Result

問題 ABC261B

シグネチャを決める。星取表のひとマスは1文字で表現されているので、String こと [Char] のリストで渡すことにする。

abc261b :: Int       -- N
        -> [String]  -- Aijの行ごとのリスト
        -> Bool      -- 矛盾がないときTrue

表を転置したものと突き合わせて、全ての箇所に矛盾がなければよい。

結果

import Data.List

abc261b :: Int -> [String] -> Bool
abc261b n ass = and $ zipWith (==) ias tas
  where
    ias = map inv $ concat ass
    tas = concat $ transpose ass

inv 'W' = 'L'
inv 'L' = 'W'
inv  c  =  c

C - NewFolder(1)

問題 ABC261C

シグネチャを決める。

abc261c :: Int        -- N
        -> [String]   -- Si
        -> [String]   -- 行ごとの出力内容

前から順に見ていき、それぞれの名前について、何回出現済みかを数えておく表を維持する。この表は、文字列に対して文字列を対応付けるので、 Data.Map を使って実現する。
状態を持ちまわす繰り返しは

mapAccumL :: (state -> x -> (state, y)) -> state -> [x] -> (state, [y])

で実現する。stateが状態、xが入力列の要素、yが出力列の要素の型である。

結果

import qualified Data.Map as M

abc261c :: Int -> [String] -> [String]
abc261c n = snd . mapAccumL step M.empty
  where
    step m si =
      case M.lookup si m of
        Nothing -> (M.insert (si, 1)      m, si)
        Just k  -> (M.insert (si, succ k) m, si ++ '(' : show k ++ ")")

D - Flipping and Bonus

問題 ABC261D

シグネチャを決める。

abc261d :: Int -> Int     -- N, M
        -> [Int]          -- Xi
        -> [(Int,Int)]    -- Ci, Yi のペアのリスト cys
        -> Int            -- 答え

全ての場合$2^{5000}$を試すのは無理なので、動的プログラミングを用いる。
$a$ 回めのトスにより連続 $b$ 回の表が出たとき（$b = 0$ は裏が出たことを表す）に得られる最大スコアの配列$s_a[0 \leq b \leq a]$ を追跡する。
$s_0 = [0]$ である。
$s_{a-1}$ と $X_a$ から $s_a$ が求められる。
裏が出たときの最高スコアは、直前までの最高スコアとなるので $s_a[0] = \max s_{a-1}$ となる。
表が出たときのスコアは、連続表回数が1増えるのと、連続ボーナスの両方を足し合わせたものとなる。連続ボーナスが「第 $C_i$ 項の値は $Y_i$ 、該当がない場合0」という数列 $\{B_i\}$ で表されていれば、$s_a[b > 0] = s_{a-1}[b-1] + X_a + B_i$ となる。
よって、$s_{a-1}, X_a$ から $s_a$ を求める関数は次のように実装できる。数列 $\{B_i\}$ はリスト bs にあるものとする。

step ss xa = maximum ss : zipWith (+) bs (map (xa +) ss)

bsは Data.Array.accumArray で構築できる。
問題の答えは $s_N$ の最大値である。

結果

import Data.Array

abc261d :: Int -> Int -> [Int] -> [(Int,Int)] -> Int
abc261d n m xs cys = maximum ssn
  where
    bs = elems $ accumArray (+) 0 (1,n) cys
    ssn = foldl step [0] xs
    step ss xa = maximum ss : zipWith (+) bs (map (xa +) ss)

蛇足

命令型の場合、配列を破壊的に更新できるのはよいが、前に要素を追加するのは苦手なので、添え字を逆向きに使って徐々に後ろに伸ばしていくようなコードにするといい感じにできそう。

$ts_0 = [ss_0[0]]$
$ts_1 = [ss_1[1], ss_1[0]]$
$\vdots$
$ts_n = [ss_n[n], \dots, ss_n[0]]$

つまり、初めに確保した長さ $N+1$ の配列 $ts$ の、添え字 $a$ に $ss_a[0]$ が入り、それより手前に逆向きに続きが入っていると考え、

• $ts[a+1] \leftarrow \max_{0 \leq i \leq a} ts[i] $
• $ts[0 \leq i \leq a] \leftarrow ts[i] + X_a + B_{a-i+1}$

という更新をかけることで $a$ を進め、$a = N$ まで終わったところで $ts$ の最大値を答えとする。

E - Many Operations

問題 ABC261E

シグネチャを決める。

abc261e :: Int -> Int     -- N, C
        -> [(Int,Int)]    -- Ti, Ai のペアのリスト tas
        -> [Int]          -- 結果のリスト

毎回素朴に計算するのでは間に合わないので、操作列と等価な計算を $O(1)$ で実現する工夫が必要になる。

抽象度の無駄に高い解法

実行する演算は and, or, xor ですべてビット演算なので、ビット毎に考えればよい。
演算と $A_i$ のビットの0/1により、操作 $i$ が引数 $X$ のビットを結局どうする計算になるのかをまとめると次のようになる。

演算＼Ai	0	1
and	const 0	id
or	id	const 1
xor	id	not

結局4種類の演算になった。この演算を2つ合成した結果がどうなるかも計算できる。
$X$ に演算1を適用してから演算2を適用する。

演算1＼演算2	id	const 0	const 1	not
id	id	const 0	const 1	not
const 0	const 0	const 0	const 1	const 1
const 1	const 1	const 0	const 1	const 0
not	not	const 0	const 1	id

よって、この4種類の演算を代数的データ型で表し、

• $T_i, A_i$ を関数列に展開する計算（上の対応表）
• 0/1 に適用した結果を求める適用関数
• 関数合成した結果を求める合成関数（上の合成表）
• $X$ をビット列に展開する計算、整数に戻す計算

を組み合わせることで実装できる。

結果

import Data.List

data BitFun = Fid | Fc0 | Fc1 | Fnt deriving Enum

-- 適用
apply Fid b = b
apply Fc0 _ = 0
apply Fc1 _ = 1
apply Fnt b = 1 - b

-- ビット列に広げる
i2bs n = take 30 $ f n
  where
    f x = let (q,r) = divMod x 2 in r : f q

-- 整数に戻す
bs2i bs = sum $ zipWith (*) bs $ iterate (2 *)

-- TiとAiのビットに対応する関数を選び出す
ta2f t a = [[], [Fc0, Fid], [Fid, Fc1], [Fid, Fnt]] !! t !! a

-- 合成
composite f g = table !! fromEnum f !! fromEnum g
  where
    table =
      [ [Fid, Fc0, Fc1, Fnt]
      , [Fc0, Fc0, Fc1, Fc1]
      , [Fc1, Fc0, Fc1, Fc0]
      , [Fnt, Fc0, Fc1, Fid]] 

abc261e :: Int -> Int -> [(Int,Int)] -> [Int]
abc261e n c tas = snd $ mapAccumL step (fs0, x0) tas
  where
    fs0 = iterate 30 Fid
    x0 = i2bs c
    step (fs, x) (ti, ai) = ((fs1, x1), bs2i x1)
      where
        fs1 = zipWith composite fs $ map (ta2f ti) (i2bs ai)
        x1 = zipWith apply fs1 x

ふと我に返った解法

二値関数は入力値に対する出力値の表で表現できるので、代数的データ型（というか列挙型）と同じ情報量で普通に表現できる。

fid = [0, 1] -- id
fc0 = [0, 0] -- const 0
fc1 = [1, 1] -- const 1
fnt = [1, 0] -- not

apply = (!!) -- 適用

composite f g = map (apply g) f -- 合成

操作列と同等な合成された関数の表現である表とは、つまり入力の0/1に対して出力がどうなるかの表である。これをビット単位に30個並べて追跡する代わりに、30ビット分の入力0または1についてどうなるかの2値 $O_i, I_i$ だけを追跡し、今回の引数 $X_i$ に対しては、$X_i$のビットが1の桁については $I_i$ を、ビットが0の桁については $O_i$ を取り出して合わせることで結果を計算できる。$f$ を $T_i$ から対応するビット単位の二項演算 and, or, xor を返す関数として、

初期値：
$O_0 = 0$ : $00 \dots 00{(2)}$ に対する操作0個の適用結果
$I_0 = 11 \dots 11_{(2)}$ : 30桁の $11 \dots 11_{(2)}$ に対する操作0個の適用結果
$X_0 = C$ : $X$ の初期値
漸化式：
$O_i = f(T_i)(O_{i-1}, A_i)$
$I_i = f(T_i)(I_{i-1}, A_i)$
$X_i = (I_i \; \textrm{and} \; X_{i-1}) \; \textrm{or} \; (O_i \; \textrm{and} \; (\textrm{not} \; X_{i-1}))$

結果

import Data.Bits
import Data.List

abc261e :: Int -> Int -> [(Int,Int)] -> [Int]
abc261e n c = snd . mapAccumL step (o0, i0, c)
  where
    o0 = 0
    i0 = 2^30 - 1
    fs = [(.&.), (.|.), xor]
    step (o, i, x) (ti, ai) = ((o1, i1, x1), x1)
      where
        f = fs !! pred ti
        o1 = f o ai
        i1 = f i ai
        x1 = (i1 .&. x) .|. (o1 .&. complement x)