ABC278 A～F をHaskellで

A - Shift

問題 ABC278A

シグネチャを決める。$A_i$ は数である必要がない。

abc278a :: Int       -- N
        -> Int       -- K
        -> [String]  -- Ai
        -> [String]  -- 答え

基本的に、$A_i$ の前から $K$ 要素を除き、後ろに $K$ 要素の "0" を追加すればよいが、
$N < K$ のときに（削除しすぎ、）追加しすぎる。

結果

abc278a n k as = take n $ drop k as ++ repeat "0"

B - Misjudge the Time

問題 ABC278B

シグネチャを決める。

abc278b :: Int        -- H
        -> Int        -- M
        -> (Int,Int)  -- 答え (時,分)

24時制で AB時CD分が、AC時BD分も時刻としてありうる数字の配置であるとは、

• BはAが0,1のとき全ての数字が現れる。Aが2のときは3以下の数字が現れうる。
• Cは常に5以下の数字である。

より、BとCが入れ替わっても時刻として違和感を起こさない条件は、

• Bが5以下である
• Cは、Aが2のとき3以下、Aが1以下のときは条件なし

の両方が満たされることである。
このような条件を満たす時刻を、1分ずつ進めながら見つける。

結果

abc278b h m = until prop tick (h,m)

tick (23, 59) = (0, 0)
tick (h , 59) = (succ h, 0)
tick (h ,  m) = (h, succ m)

prop (h, m) = b <= 5 && (a /= 2 || c <= 3)
  where
    (a,b) = divMod h 10
    (c,d) = divMod m 10

質問に「0X時X0分のように、BとCが等しい場合も見間違えやすいに含むか？」とあった。そんなこと全く考えなかったが、確かに言われてみると、それは見間違えても時刻は変わらない。

C - FF

問題 ABC278C

シグネチャを決める。（本番での実装はクエリごとに計算する形にしたが、ここでは一括して計算する形にする。）

abc278c :: Int      -- N
        -> Int      -- Q
        -> [[Int]]  -- Ti,Ai,Bi
        -> [Bool]   -- 答え

フォロー状況を、整数のペアの集合で表現する。
「ユーザーXがユーザーYをフォローしている」を要素 (X,Y) で持つ。

結果

import qualified Data.Set as S
import Data.Maybe

abc278c :: Int -> Int -> [[Int]] -> [Bool]
abc278c n q tabs = catMaybes $ snd $ mapAccumL step S.empty tabs

step s [1,a,b] = (S.insert (a,b) s, Nothing)
step s [2,a,b] = (S.delete (a,b) s, Nothing)
step s [3,a,b] = (s, Just $ S.member (a,b) s && S.member (b,a) s)

D - All Assign Point Add

問題 ABC278D

シグネチャを決める。
続けてクエリ問題。

abc278d :: Int      -- N
        -> [Int]    -- Ai
        -> Int      -- Q
        -> [[Int]]  -- query_q
        -> [Int]    -- 答え

$A$ の初期値が与えられているのに、1で行うことは「$A$ の全ての要素に $x_q$ を加える。」ではなくて「$A$ の全ての要素を $x_q$ にする。」である点がいつもと違う。

$N \leq 2 \times 10^5$ 要素の配列を $Q \leq 2 \times 10^5$ 回クエリ「$1 \; x_q$」でリフレッシュさせられてはかなわないので、クエリ2で値を与えられた要素だけ IntMap で保持し、それ以外は直近のクエリ1で与えられたデフォルト値とする。

結果

import qualified Data.IntMap as IM
import Data.Maybe

abc278d :: Int -> [Int] -> Int -> [[Int]] -> [Int]
abc278d n as q qs = catMaybes $ snd $ mapAccumL step (im0, 0) qs
  where
    im0 = IM.fromList $ zip [1..] as

step (im, def) query =
  case query of
    [1,x]   -> ((IM.empty , x  ), Nothing)
    [2,i,x] -> ((imadd i x, def), Nothing)
    [3,i]   -> ((im       , def), Just $ a i)
  where
    imadd i x = IM.insert i (a i + x) im
    a i = IM.findWithDefault def i im

defの初期値はundefinedでも問題ないはず。

E - Grid Filling

問題 ABC278E

シグネチャを決める。

abc278e :: Int      -- H
        -> Int      -- W
        -> Int      -- N
        -> Int      -- h
        -> Int      -- w
        -> [[Int]]  -- Aij
        -> [[Int]]  -- 答え

全ての塗りつぶしに対して定義通りに数えると $O(H^2W^2)$ で大変なので、計算量を節約したい。そこで塗りつぶしされていない部分に、どの数字が何回出現しているのかを、大きさ$N$の配列で数えて把握する。この配列の0でない要素の個数が、それぞれに対して問題が要求している数になる。

塗りつぶし範囲が(1,1)から(h,w)の場合については、素直に数える。
このカウント結果があるとき、塗りつぶし範囲を右または下に1マスずらした場合のカウント結果は、塗りつぶし範囲から復帰する部分のマスについてカウントを増やし、新たに塗りつぶされる部分のマスについてカウントを減らすだけで構築できる。

最初の塗りつぶしについて数えたものから、下に範囲をずらしたものを行数分だけ作る。
これらをスタート地点として、塗りつぶし範囲を右にずらしたものを列数分だけ作る。
という２次元の走査で全ての結果を効率的に得られる。

結果

import Data.Array.Unboxed

abc278e :: Int -> Int -> Int -> Int -> Int -> [[Int]] -> [[Int]]
abc278e hh ww n h w ass = map countXYs $ zip [1..] countX1s
  where
    aa :: UArray (Int,Int) Int
    aa = listArray ((1,1),(hh,ww)) $ concat ass
-- 素直に数える
    count11 :: UArray Int Int
    count11 = accumArray (+) 0 (1,n)
      [(a, 1) | (i,as) <- zip [1..] ass, (j,a) <- zip [1..] as, h < i || w < j]
-- 下にずらしたカウント
    countX1s = scanl stepV count11 [1..hh-h]
    stepV cnt h0 = accum (+) cnt $
      [(aa ! (h0  , j),  1) | j <- [1..w]] ++
      [(aa ! (h0+h, j), -1) | j <- [1..w]]
-- 右にずらしたカウント
    countXYs (h0, countX1) = map countNZ $ scanl (stepH h0) countX1 [1..ww-w]
    stepH h0 cnt w0 = accum (+) cnt $
      [(aa ! (h0 + i, w0  ),  1) | i <- [0..pred h]] ++
      [(aa ! (h0 + i, w0+w), -1) | i <- [0..pred h]]
-- 0でない要素の個数を数える
    countNZ = length . filter (0 <) . elems

やることは判っているのだけど、配列をごちゃごちゃするのが面倒で飛ばしてしまった。
それでタイムアップするのだから情けない。

F - Shiritori

問題 ABC278F

シグネチャを決める。

abc278f :: Int       -- N
        -> [String]  -- Si
        -> Bool      -- 答え True なら "First", False なら "Second"

ある語から開始して、行き詰まるまでしりとりを続ける様子は木構造をなす。
「ある語を読んだ」ことで「まだ読まれていない語の集合」と「次に読むべき語の先頭の文字」という状況が定まった状態をノードの識別子とする。
この状況から、次に遷移できるノード（読める語）が決定できる。

• 次に読める語がない状態なら相手は手詰まりなので勝ち。
• 次に読める語の状態に一つでも勝ち（これは相手が、という意味になる）なら、相手はそれを選択するはずなので負け。
• そうでないときとは、全ての相手の選択肢が全て相手の負け確定になっているので、勝ち。

$N \leq 16$ と大したことないので、「使用済みの語」をビット集合で表現し、「次の先頭の文字」に対して、読める語の番号とその末尾の文字の対をMapで持つことで、これを全探索する。
どこかの語から始めることで先攻が勝ちにできるなら "First" さもなくば "Second" が答えとなる。

結果

次の状態を読んだ結果を rs とすると、上の分析は以下の場合分けになる。

  | null rs   = True
  | or rs     = False
  | otherwise = True

これは = not $ or rs と等しい。

import qualified Data.Map as M
import Data.Bits

abc278f :: Int -> [String] -> Bool
abc278f n ss = or [check (bit i) (last s) | (i, s) <- zip [0..] ss]
  where
    g = M.fromListWith (++) [(head s, [(i, last s)] | (i, s) <- zip [0..] ss]

    check bs c = not $ or
      [ check (setBit bs j) d
      | (j, d) <- M.findWithDefault [] c g
      , not $ testBit bs j]

わずか $N \leq 16$ にもかかわらずTLEする。
check 関数の呼び出しは重複するので、これをメモ化して計算量を抑える必要がある。

メモ化

import qualified Data.Map as M
import Data.Bits
import Data.Array

abc278f :: Int -> [String] -> Bool
abc278f n ss = or [checkA ! (bit i, last s) | (i, s) <- zip [0..] ss]
  where
    g = M.fromListWith (++) [(head s, [(i, last s)] | (i, s) <- zip [0..] ss]

    checkA = array ((1,'a'),(2^n-1,'z'))
      [((bs, c), checkF bs c) | bs <- [1..2^n-1], c <- ['a'..'z']]

    checkF bs c = not $ or
      [ checkA ! (setBit bs j, d)
      | (j, d) <- M.findWithDefault [] c g
      , not $ testBit bs j]

愚痴：メモ化が必要なのはTLEしてすぐ気づいたのだが、そこで混入したしょうもないバグに気づくのに20分もかかってしまった。

Data.Array.array は要素が足りていなくてもその場では文句を言わず、
定義が与えられなかった要素にアクセスがあったところで初めて

a.out: (Array.!): undefined array element

と実行時エラーを起こす。
よく見るとこれは添え字の範囲外へのアクセスをしたときのエラー

a.out: Error in array index

とは異なるので、エラーメッセージはちゃんと読みましょう。

または、array や listArray で配列要素を生成するときには、自分で添え字を生成せずに、　Data.Ix.range に任せると失敗がない。

bounds = ((1,'a'),(2^n-1,'z'))
checkA = listArray bounds $ map checkF $ range bounds

checkF (bs, c) = ...

checkF 関数の引数を非カリー化して配列の添え字と合わせている。