ABC283 A～E をHaskellで

A - Power

問題 ABC283A

Haskellにはなぜかべき乗がいっぱいある。

(^)  :: (Num a       , Integral b) => a -> b -> a  -- bは非負整数のみ
(^^) :: (Fractional a, Integral b) => a -> b -> a  -- 小数の整数乗、負の数も許す
(**) :: Floating a                 => a -> a -> a

結果

main = getLine >>= print . (\[a,b] -> a ^ b) . map read . words

B - First Query Problem

問題 ABC283B

配列を順次書き換えよということなので、IOArray でする。

結果

import Data.Array.IO
import Control.Monad

main = do
  n <- readLn
  as <- map read . words <$> getLine
  arr <- newListArray (1,n) as :: IO (IOArray Int Int)
  q <- readLn
  replicateM_ q $ do
    qi <- map read . words <$> getLine
    case qi of
      [1,k,x] -> writeArray arr k x
      [2,k]   -> readArray arr k >>= print

C - Cash Register

問題 ABC283C

入力は最大100001文字になるので、ByteString で読み込むべきかとも思うが、文字のリストのパターンマッチで数えるくらいで済ませたいので String で読む。

結果

シグネチャを決める間もない。

abc283c :: String -> Int
abc283c = loop 0
 
loop cnt ""           = cnt
loop cnt ('0':'0':ds) = loop (succ cnt) ds
loop cnt       (_:ds) = loop (succ cnt) ds

D - Scope

問題 ABC283D

シグネチャを決める。やはり文字列をちまちま調べるので String で。

abc283d :: String  -- S
        -> Bool    -- 答え

「良い文字列」とはつまり、括弧の対応がとれているものということで、
閉じ括弧で位置 $j$ がどうこうとは、位置 $i$ の閉じ括弧に対応する開き括弧の位置ということ、
が言いたいのだろうと好意的に解釈する。

つまり、

• 英文字が来るたびに、その文字が初出であればセーフ、2回めならばアウトとする
• 開き括弧で、その次点で出現済みの文字の状況をセーブする（入れ子あり）
• 閉じ括弧で、直前にセーブした状況をロードして、対応する開き括弧以降の変更をリセットする

26個もあるフラグを管理するので IOArray Char Bool で管理する…必要はなく、ビットに文字を割り当てれば32ビット整数でも間に合う。（mutable arrayでは状況のセーブも大変である。）

結果

import Data.Bits
import Data.Char

abc283d :: String -> Bool
abc283d s = loop s (complement zeroBits) []

loop :: String -> Int -> [Int] -> Bool -- bの型を固定する必要がある
loop ""       _ _      = True
loop ('(':cs) b bs     = loop cs b (b:bs)
loop (')':cs) _ (b:bs) = loop cs b bs
loop ( c :cs) b bs     = testBit b i && loop cs (clearBit b i) bs
  where
    i = ord c - ord 'a'

問題文の言い回しについて

$S_i$ が ) ならば、$i$ 未満の整数 $j$ であって、$S$ の $j$ 番目から $i$ 番目までの文字からなる文字列が良い文字列となる最大の整数 $j$ を取る。

「良い文字列」の定義では「まず英小文字をすべて削除する」ので、abc(def) の末尾 $i=8$ に対して $j=4$ （つまり (def)）以外に、$j=3$（c(def))、$j=2$（bc(def))、$j=1$（abc(def)) も「良い文字列」である。

が、「となる最大の整数 $j$」とあるので、これらの中で最大の $j=4$ を選べということのようだ。

ところが、問題文にも

英小文字、(、) からなる文字列のうち

とあるように、「$S$ の $j$ 番目から $i$ 番目までの文字からなる文字列」という言い方は、「appleはaからzの文字からなる文字列」というのと同じで、全てを使えとも並び順を変えるなとも言っていない。とすると、空文字列は常に良い文字列なので、常に $j=i$ が選べてしまう。

普通に「$S$ の $j$ 番目より後ろの文字を取り除き、$i$ 番目より前の文字を取り除いて得られる部分文字列」と表現するべきところだったように思う。

E - Don't Isolate Elements

問題 ABC283E

シグネチャを決める。

abc283e :: Int      -- H
        -> Int      -- W
        -> [[Int]]  -- Aij
        -> Int      -- 答え

$1 - 1 = 0, 1 - 0 = 1$ ということで、操作 $1 - A_{i,j}$ は0と1を入れ替える。操作されていない行を「表」された行を「裏」と呼ぶことにする。

ある行に孤立した要素があるかどうかは、その上の行と下の行の両方がないと判断できない。（1行めと$H$行めは、0行めと$H+1$行めに、0でも1でもない値が並んだ行があるとして考えればよい。）

上から順に見てDPしていくことを考える。
$i-1$行めと$i$行めの過去2行について、表と裏の状態が考えられる。
この4パターンそれぞれについて、1行めから$i-1$行めまでに孤立した要素なしにできるか、またそのときの操作の最小回数を追跡する。孤立した要素が出現してしまう場合は、操作回数が$H+1$（$H$を超える値）で表すことにする。
次に$i+1$行めについて、やはり表と裏の両方について、$i$行めに孤立が起きないようにできるかどうかを調べる。8通りの場合を調べ、孤立が起きないとき、$i+1$行めを裏返すなら操作回数が1増える、孤立が起きるときは操作回数は$H+1$になる、とする。
これらの操作回数の最小値を、$i$行めと$i+1$行めの表裏の4パターンそれぞれについて集計する。これを上から下まで行う。
4パターンの操作回数の最小値が答えとなる。

結果

反復で更新する状態は次の内容を持っている：

( [Int] -- 長さ4で、表/表, 表/裏, 裏/表, 裏/裏 の場合の最小操作手順
, [Int] -- i-1行めの内容
, [Int] -- i-1行めを裏返した内容
, [Int] -- i行めの内容
, [Int] -- i行めを裏返した内容
)

abc283e :: Int -> Int -> [[Int]] -> Int
abc283e h w (as:ass)
  | ans > h   = -1
  | otherwise = ans
  where
    h1 = succ h
    lOUT = replicate w 2
    cnt0 = [0,1,h1,h1]
    statn = foldl' step (cnt0, lOUT, lOUT, as, map rev as) ass
    (cnt,_,_,_,_) = step statn lOUT -- 仮想のH+1行め
    ans = minimum cnt
    step ([cnt0, cnt1, cnt2, cnt3], l0, l0r, l1, l1r) l2 =
      ( [min cnnn cRnn, min cnnR cRnR, min cnRn cRRn, min cnRR cRRR]
      , l1, l1r, l2, l2r)
      where
        l2r = map rev l2
        cnnn = if check l0  l1  l2  then cnt0     else h1
        cnnR = if check l0  l1  l2r then cnt0 + 1 else h1
        cnRn = if check l0  l1r l2  then cnt1     else h1
        cnRR = if check l0  l1r l2r then cnt1 + 1 else h1
        cRnn = if check l0r l1  l2  then cnt2     else h1
        cRnR = if check l0r l1  l2r then cnt2 + 1 else h1
        cRRn = if check l0r l1r l2  then cnt3     else h1
        cRRR = if check l0r l1r l2r then cnt3 + 1 else h1

-- 行l1が孤立した要素を持たないときTrue
check l0 l1 l2 = and $ zipWith (||) (zipWith (||) bN bS) (zipWith (||) bE bW)
  where
    bN = zipWith (==) l0 l1
    bS = zipWith (==) l1 l2
    bE = zipWith (==) l1 (tail l1) ++ [False]
    bW = zipWith (==) l1 (2:l1)

-- 操作
rev a = 1 - a

stepがあまりにもコードクローンなのでまとめて次のようにできたが、見通しよくなったかというと微妙。

    step (cnt, l0, l0r, l1, l1r) l2 =
        (zipWith min as bs, l1, l1r, l2, l2r)
      where
        l2r = map rev l2
        (as,bs) = splitAt 4
          [ if check l0 l1 l2 then cnti + one else h2
          | (cnti, (l0, l1)) <- zip cnt [(l0, l1) | l0 <- [l0,l0r], l1 <- [l1, l1r]]
          , (l2, one) <- [(l2, 0), (l2r, 1)]
          ]