LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@gotoki_no_joe(じょお)

ABC413をHaskellで

Posted at

A - Content Too Large

問題 ABC413A

シグネチャを決める。

abc413a :: Int   -- N
        -> Int   -- M
        -> [Int] -- Ai
        -> Bool  -- 答え
abc413a _n m as = m >= sum as

B - cat 2

問題 ABC413B

シグネチャを決める。

abc413b :: Int      -- N
        -> [String] -- Si
        -> Int      -- 答え

実際に全ての組み合わせを作り、Set に放り込めばよい。

結果

import Data.List
import qualified Data.Set as S

abc413b :: Int -> [String] -> Int
abc413b _n ss = S.size $ S.union s1 s2
  where
    s1 = S.fromList [a ++ b | a:bs <- tails ss, b <- bs]
    s2 = S.fromList [b ++ a | a:bs <- tails ss, b <- bs]

C - Large Queue

問題 ABC413C

シグネチャを決める。

abc413c :: Int     -- Q
        -> [[Int]] -- query_i
        -> [Int]   -- 答え

普通にする

Data.Sequence を使って、タイプ1クエリについては右から追加し、タイプ2クエリについては左から取り出せばよい。
ただし、$c \leq 10^9$ と大きいので、言葉どおりに replicate でやると困ったことになる。
$(c,x)$ の対のキューとして保持し、タイプ2クエリに対しては必要な個数だけ切り出す。

import Data.List
import qualified Data.Sequence as Q
import Data.Maybe

abc413c :: Int -> [[Int]] -> [Int]
abc413c _q qis = catMaybes $ snd $ mapAccumL step Q.empty qis
  where
    step q (1:c:x:_) = (q Q.|> (c, x), Nothing)
    step q (2:k:_) = loop k 0 q

    loop k v ((c,x) Q.:<| q) =
      case compare k c of
        GT -> loop (k - c) (v + c * x) q
        EQ -> (q, Just $ v + c * x)
        LT -> ((c - k, x) Q.:<| q, Just $ v + k * x)

もっとズルいやり方

タイプ2クエリのときデータが不足することはないと保証されているので、クエリの流れてくる順に処理する必要もなく、タイプ1クエリで到着するデータ全てのリストを完全に構築してから、タイプ2クエリのそれぞれの結果を求めても同じ事になる。
このアプローチなら Data.Sequence も Data.Maybe も使わずにできてしまう。

import Data.List

abc413c :: Int -> [[Int]] -> [Int]
abc413c _q qis = snd $ mapAccumL step cxs0 ks
  where
    cxs0 = [(c,x) | 1:c:x:_ <- qis]
    ks = [k | 2:k:_ <- qis]
    step cxs k = loop k 0 cxs

    loop k v ((c,x):cxs) =
      case compare k c of
        GT -> loop (k - c) (v + c * x) cxs
        EQ -> let !res = v + c * x in (cxs, res)
        LT -> let !res = v + k * x in ((c - k, x):cxs, res)

D - Make Geometric Sequence

問題 ABC413D

シグネチャを決める。テストケース一つ分の計算をする。

abc413d :: Int    -- N
        -> [Int]  -- Ai
        -> Bool   -- 答え

公比 $r < -1$ のとき、符号が激しく入れ替わる。そのような場合も含めて、絶対値の昇順にソートすれば、隣接する要素どうしの比が一定であることで判定できる。
これは $r = 1$ の場合も統一して扱える。
絶対値の昇順にすることで、$-1 < r < 1$ の場合は現れない。

唯一取りこぼしているのが $r = -1$ の場合で、この場合は$-a$と$a$が交互に出現する。これは専門で判定するコードを用意する。

結果

import Data.List
import Data.Function
import Data.Ratio

abc413d :: Int -> [Int] -> Bool
abc413d n as@(a1:_) = cond1 || cond2
  where
-- 一般の場合
    cond1 = same $ between (%) $ sortBy (compare `on` abs) as
-- r = -1 の場合
    cp = count a1 as
    cm = count (- a1) as
    cond2 = cp + cm == n && abs (cp - cm) <= 1

same (x:xs) = all (x ==) xs

between f xs = zipWith f xs $ tail xs

count v xs = length $ filter (v ==) xs

これこの問題の話で、$r=-1$の場合が全てのテストケースに入っているものだから、それにひっかかっている提出は全滅判定で、どの程度正しいのかさっぱりわからんかった、ってことなんですよ。

E - Reverse 2^i

問題 ABC413E

シグネチャを決める。テストケース一つ分の計算をする。

abc413c :: Int   -- N
        -> [Int] -- Pi
        -> [Int] -- 答え

「操作」は、$a$ が2進数で AAAAA のとき、（0始まりの）位置 AAAAA00..00 (後半は$b$個の0の連続）から位置 AAAAA11..11 までを反転させる。AAAAA の下位に 0 があってもよい。
これは、順列 $P_i$ を高さ $N$ の完全二分木の葉に並べたとき、いずれかのノードの傘下にある要素をまるごと反転させることに対応していて、逆にいうと、そのような範囲をまたぐ CC00100～CC10011 のような区間で反転ということは起きない、と言っている。

完全二分木の任意の頂点で反転させて辞書順最小を目指す、という問題に読み替えると、

  • 葉は $P_i$ のみからなる列そのものしか選択肢がない
  • 中間頂点は、左部分木の列を最小にしたものと、右部分木の列を最小にしたものとで、小さい方を前に、そうでない方を後ろに付ける
    （ここで、$P_i$ は順列なので要素の重複はなく、先頭要素を見るだけで辞書順の比較が可能なのがミソ。そうでないと長さ分の比較時間がかかる。〉

というボトムアップな再帰計算で答えが得られるとわかる。

結果

列の連結を $O(N)$ でするために ShowS と同じ技を使っている。

import Data.List
import qualified Data.Vector.Unboxed as UV

abc413e :: Int -> [Int] -> [Int]
abc413e n ps = res []
  where
    pV = UV.fromListN n ps
    (_, res) = recur (2 ^ n) 0
    recur :: Int -- 注目している区間の長さ
          -> Int -- 注目している区間の先頭位置
          -> ( Int              -- 先頭要素（比較用）
             , [Int] -> [Int])  -- 最小化した列（を与えられた列の前に繋ぐ関数）
    recur 1 a = (x, (x :))
      where
        x = pV UV.! a
    recur len a
      | x < y     = (x, v . w)
      | otherwise = (y, w . v)
      where
        len2 = div len 2
        (x, v) = recur len2 a
        (y, w) = recur len2 (a + len2)

F - No Passage

問題 ABC413F

シグネチャを決める。横着する。

abc413f :: [Int]   -- H,W,K
        -> [[Int]] -- Ri,Ci
        -> Int     -- 答え

TLEから抜け出せずに、フレンズさんのヒントを見た。

アライグマ「F問題は、青木君の邪魔がないときはBFSで解けるのだ。
青木君の邪魔があるときは、BFSで2回目に来たときに距離の更新とキューへの追加をすればいいのだ！」

1～4の整数がどうとかうるさいが、要は、マス目の範囲内で4近傍上下左右に移動する、
ただし1方向だけ禁止にする青木君がいるとき、ゴールに行くまでの距離をそれぞれのマスについて数えよ、
ということ。

例1を見ると、2方がゴールであるマスは、どちらか一方を止められたとしても、もう一方に行けるので距離1となっている。
同様に、周囲の距離が短い方から2つ確定しているとき、小さい方は止められるので大きい方が答になる。
幅優先探索を使えば、距離は短い順に決定できるので、後からより短いものが現れる恐れがない。

ということで、

  • 幅優先探索で探索
  • マスの距離が確定するたびに、その周囲4マスを調査候補に投入
  • 最初の訪問では、一度訪問したという印だけ付けて終わり
  • 2度めの訪問で、そのときの距離でマスの答えを確定させる。周囲4マスが次の候補になる

とすればよい。

TLEから抜け出せなかった理由は、幅優先探索なら2度目の訪問で確定、に気づかず、
全ての訪問において周囲の距離を調べ、2つ以上の距離が確定していたら確定、
という無駄のあるロジックだったせいのようだ。

結果

キューは Data.Sequence で座標と距離の対を管理するのではなく、
今回処理する座標リストと次回のリストの2本と、現在の距離、の組み合わせにするスタイル。
また、それぞれのマスの確定した距離を配列に記録して最後に総和を取るのではなく、
マスが確定するたびに、それを合計していくスタイル。

import Control.Monad.ST
import Data.Array.ST
import Data.Word

abc413f :: [Int] -> [[Int]] -> Int
abc413f [h,w,_k] rcs = runST $
  do
    fld <- newArray bnds 0 :: ST s (STUArray s (Int,Int) Word8)
    forM_ ijs0 (\rc -> writeArray fld rc 2)
    loop fld 1 (concatMap neighbors ijs0) [] 0
  where
    bnds = ((1,1),(h,w))
    ijs0 = [(r,c) | r:c:_ <- rcs]
    neighbors (i,j) = filter (inRange bnds) [(pred i,j),(succ i,j),(i,pred j),(i,succ j)]

    loop :: STUArray s (Int,Int) Word8 -> Int -> [(Int,Int)] -> [(Int,Int)] -> Int -> ST s Int
    loop _fld _d [] [] acc = return acc
    loop fld d [] kls acc = loop fld (succ d) kls [] acc
    loop fld d (ij:ijs) kls acc = do
      x <- readArray fld ij
      case x of
        0 -> writeArray fld ij 1 >> loop fld d ijs kls acc
        1 -> writeArray fld ij 2 >> (loop fld d ijs (neighbors ij ++ kls) $! acc + d)
        _ -> loop fld d ijs kls acc

ちなみに、同じアプローチで、初回訪問済み頂点集合と確定済み頂点集合をIntSetで保持するimmutable版は惜しくもTLEx4で終わった。

G - Big Banned Grid

問題 ABC413G

シグネチャを決める。横着する。シグネチャがF問題ととても似ている。

abc413g :: [Int]   -- H,W,K
        -> [[Int]] -- Ri,Ci
        -> Bool    -- 答え

こちらは $H,W \leq 2\times 10^5$ と広大なので、マス目の配列を幅優先探索する訳にはいかない。
一方、$K \leq 2 \times 10^5$ と手勢が足らず、大抵はどこかから通れそう。

つまり、((1,1),(h,w)) という広大なフィールドのうち、
上辺 (1,*) または右辺 (*,W) から
下辺 (H,*) または左辺 (*,1) まで、斜めも含む8近傍で繋ぐ経路があれば、
それが障害となって高橋君はゴールできず、さもなくばどこからか通れるはず。
この方法なら、障害の個数 $K$ に対して $O(K \log K)$ くらいで判断できるだろう。

例外がちょっとあって、
例3にあるとおり、$H=W=1$ でスタートとゴールが同じときは、必ず成功する。
例にはないが、$H=1$ または $W=1$ のときは、障害物が一つあるだけでアウトになる。

結果

障害物は座標の集合で直接扱った。

import qualified Data.Set as S

abc413g :: [Int] -> [[Int]] -> Bool
abc413g [1,1,_] _ = True
abc413g [h,w,k] _ | h == 1 || w == 1 = k == 0
abc413g [h,w,_k] rcs = loop r0 ijs0
  where
    ijs0 = [(r,c) | r:c:_ <- rcs, r == 1 || c == w]
    r0 = S.fromList [(r,c) | r:c:_ <- rcs, r /= 1 && c /= w]
    loop _ [] = True -- 尽きたら失敗
    loop r1 ((i,j):ijs)
      | any (\(k,l) -> k == h || l == 1) kls = False -- 到達した
      | otherwise = loop r2 (kls ++ ijs)
      where
        kls = [kl | k <- [pred i .. succ i], l <- [pred j .. succ j], let kl = (k,l), S.member kl r1]
        r2 = foldl' (flip S.delete) r1 kls

別解とか

  • 公式解説 by MMNMM
    • グラフを作ると(1,1) から (H,W) への最大流の流量が 1 以上であることと同値
    • これは、最大流最小カット定理から、重み 0 のカットが存在しないことと同値
    • 双対グラフの最短経路問題に帰着
    • 幅優先探索や深さ優先探索、Union Find などを用いることで解くことができます

何でそう色々な話に飛ぶの。

  • 公式解説の補足 by Iroha_3856
    • 公式解説の補足をします。 本質は同じ
    • {左の壁 または 下の壁} から {右の壁 または 上の壁} へと障害物マスを八近傍で辿っていけるのと、(1,1) から (H,W) へと行く経路は存在するのは同値

つまり自分の解法と同じアプローチなのね。

  • ユーザ解説 by PCTprobability
    • 障害物がないマスを、O(H+K) 個の矩形領域に分解
    • 各列に対して連続している障害物がないマスの区間を極大に取る
    • 後はグラフを実際に構築して (1,1) を含む矩形領域から (H,W) を含む矩形領域に到達可能かを見ればよい

これはフレンズさんの説明の

アライグマ「G問題はABC361Gとだいたい同じなのだ！
通れるマスを横長の長方形に分割すればいいのだ！」

これと同じアプローチのことかな？

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?