ABC268 A～E をHaskellで

A - Five Integers

問題 ABC268A

シグネチャを決める。

abc268a :: [Int]  -- A,B,C,D,E
        -> Int    -- 答え

Data.List.nub で重複をなくせばよい。
入力を Int にする必要すら実はない。

結果

import Data.List

abc268a :: [String] -> Int
abc268a = length . nub

B - Prefix?

問題 ABC268B

シグネチャを決める。

abc268b :: String  -- S
        -> String  -- T
        -> Bool    -- 答え

Data.List.isPrefixOf というそのものずばりの標準ライブラリ関数がある。

結果

import Data.List

abc268b :: String -> String -> Bool
abc268b = isPrefixOf

$T$ の先頭から $S$ の長さだけ取り出した文字列が $S$ と等しいならば接頭辞、と自分で計算してもいい。

abc268b s t = s == take (length s) t

C - Chinese Restaurant

問題 ABC268C

「料理 $p_i$」が、重複のない料理の背番号のことなのか、重複のある料理の種類のことなのか、問題文からは判断できない。例は全て重複がないが、それは判断材料にはならない。
以下、重複がないものとして進める。

シグネチャを決める。

abc268c :: Int   -- N
        -> [Int] -- pi
        -> Int   -- 答え

回転を $r$（$0 \leq r < N$）回行った結果、それぞれの料理が喜ばせる人数を足し合わせ、 $r$ に関して最大値を探せばよい。
最初に人 $i$ の前にある料理 $p_i$ は、人 $p_i$ の正面に来るとその人を喜ばせる。回転が1足らないか1多くても問題ない。そのために回転させる回数はそれぞれ、$\bmod N$ で $p_i - i,$ $p_i - i + 1,$ $p_i - i - 1$ である。

結果

import Data.Array

abc268c :: Int -> [Int] -> Int
abc268c n ps =
  maximum $ elems $
  accumArray (+) 0 (0, pred n)
  [(mod e n, 1) | d <- zipWith (-) ps [0..], e <- [pred d .. succ d]]

$p_i$ に重複が許される場合、人 $i$ の正面と両隣に料理 $i$ が並んでも喜ぶのは人 $i$ ただひとりだが、上のプログラムはこのとき人 $i$ が3人分喜んでいるという答えを返す。
（そういう問題の場合はどうやって解けばよいのだろうか…）

D - Unique Username

問題 ABC268D

シグネチャを決める。

abc268d :: Int       -- N
        -> Int       -- M
        -> [String]  -- Si
        -> [String]  -- Ti
        -> String    -- 答え

$N \leq 8$ なので、$S_i$ の並べ替えのやり方はたかだか $_8P_8 = 40320$ とおり。
文字列で埋まる部分の長さ $L = \sum |S_i|$ として、下線の入れ方は、$3 \leq |X| \leq 16$ から $L$ を引いた値を$N-1$個に分割するやり方の場合の数で
$$\sum_{u = 3-L}^{16-L} {}_u C _{N-2}$$
これも大した数ではないので、総当たりで試しても時間は間に合うと予想する。

結果

import Data.List
import qualified Data.Set as S

abc268d n m ss ts
  | null xs   = "-1"
  | otherwise = head xs
  where
    tset = S.fromList ts
    slen = sum $ map length ss
    usmax = 16 - slen               -- 下線文字個数の上限
    usmin = max (3 - slen) (pred n) -- 下線文字個数の下限
    xs = [ x
         | ss1 <- permutations ss         -- Siの順列
         , k <- [usmin .. usmax]          -- 下線文字個数
         , ks <- combinations (pred n) k  -- N-1か所それぞれの下線文字数
         , let x = build ks ss1           -- Xの候補
         , S.notMember x tset             -- Tiに現れない
         ]

combinations 0 x = [[] | x == 0]
combinations 1 x = [[x]]
combinations n x = [a : bs | a <- [1 .. x-n+1], bs <- combinations (pred n) (x - a)]

-- ssの間に順にk文字の'_'を挟んでXを作る
build ks ss = concat [replicate k '_' ++ s | (k,s) <- zip (0:ks) ss]

$S_i$ の順列は Data.List.permutations で列挙できる。
下線文字の配分を combinations で列挙している。数 $x$ を1以上で $n$ 個に分割するやり方は、

• $n=1$のとき $[x]$ だけ、
• $n>1$のとき、$1 \leq a \leq x - n + 1$ について、まず $a$ をとって、残りは $x - a$ を $n-1$ 個に分割する全てのやり方

となる。ただし $n=0$ のとき、$x=0$ なら $[\,]$ だけ、$x > 0$ ならひとつもなし、となる。（$N = 1$ のとき現れる）

（実際には自分は、同じアイデアをより高速な ByteString でACさせた。この String 版でもACすることを確認した。）

蛇足

入力がもっと巨大な場合は、

1. $T_i$ を下線文字で区切り、$S_i$の番号と間の下線文字の文字数に正規化する。（正規化できない、生成できないものはこの段階で捨てる。）$S_i$ の番号列をキーに、下線文字の文字数列の集合を値とした Map を作る。
2. キーとして使われていない順列があればそれの最も単純な列を返す
3. さもなくば、下線文字の文字数列の可能な組み合わせで使われていないものがあればそれを使う

という前向きなアプローチになるのだろうか。

E - Chinese Restaurant (Three-Star Version)

問題 ABC268E

問題Cの発展問題なので、やはり問題文に同じ疑問点を抱えている。
C同様、$p_i$ は背番号だとして話を進める。

シグネチャも問題Cと同じ。

abc268e :: Int   -- Int
        -> [Int] -- pi
        -> Int   -- 答え

人 $i$ の不満度は、自分と料理 $i$ との位置のずれの大きさ、ただし、右回りと左回りで近い方。
目の前にあるとき不満度は最小で 0、反対側にあるとき不満度は最大で $\lfloor N/2 \rfloor$ となる。
回転量に対する不満度のグラフは、$d = (p_i - i) \bmod N$ が $N/2$ 以下、つまり正回転で0に近づく場合は次のようなグラフをなす。

逆回転で0に近づく場合は形が変わる。

このようなグラフをなす関数を、全ての料理について足し合わせて、不満度合計の最小値を求めるには、積分としての累積和を用いる。

結果

import Data.Array

abc268c :: Int -> [Int] -> Int
abc268c n ps = minimum fs
  where
    ds = [mod (p - i) n | (p,i) <- zip ps [0..]]
    f0 = sum [if d * 2 < n then d else n - d | d <- ds]  -- 不満度切片
    fs = scanl (+) f0 $                                  -- 不満度
         scanl1 (+) $ elems $                            -- 不満度傾き(速度)
         accumArray (+) 0 (0, pred n) $                  -- 不満度傾きの変化量(加速度)
         [t | d <- ds, t <- ts n d]

-- n,dなグラフの傾きの変化量
ts n d
  | d * 2 < n = (0, -1) : (d, 2) :
                if even n then [(d + n2, -2)] else
                if d + n2 + 1 == n then [(d + n2, -1)] else
                [(d + n2, -1), (d + n2 + 1, -1)]
  | otherwise = (0,  1) : (d, 2) :
                if even n then [(d - n2, -2)] else [(d - n2 - 1, -1),(d - n2, -1)]
  where
    n2 = div n 2

$N$ が奇数の場合、グラフの上に凸になっている箇所が一点にならず、2回同じ値をとることに注意が必要。
さらに細かいが、後半 d + n2 + 1 が $N$ をオーバーランしているとき、0に戻して足しこむ必要はないことにも注意。