LoginSignup
2
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(じょお)

ABC402 A～F をHaskellで

Posted at

A - CBC

問題 ABC402A

シグネチャを決める。

import Data.Char

abc402a :: String -- S
        -> String -- 答え
abc402a = filter isUpper

B - Restaurant Queue

問題 ABC402B

シグネチャを決める。

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

オンラインで応対する必要はない。
タイプ1のクエリで届いた番号を、タイプ2のクエリの個数だけ返せばよい。

結果

abc402b _q qis = take cnt [x | 1:x:_ <- qis]
  where
    cnt = length [() | 2:_ <- qis]

C - Dislike Foods

問題 ABC402C

シグネチャを決める。

abc402c :: Int     -- N
        -> Int     -- M
        -> [[Int]] -- Ki, Aij
        -> [Int]   -- Bi
        -> [Int]   -- 答え

食材 $B_i$ が克服されるのは日付 $i$ である。
食材番号から克服日を求める逆引き表 $R$ を用意しておく。$R[B_i] = i$

それぞれの料理は、使う食材の克服日の最も遅い日がその料理の解禁日となる。
それは $R$ を引いた結果の最大値で求められる。
この計算は「$K_i$の総和は$3 \times 10^5$ 以下」の回数で抑えられる。

料理が解禁される日それぞれに、一つの料理が解禁されるとカウントした数を
初日から累積すれば、問題の要求を満たすことができる。

結果

import Data.Array.Unboxed

abc402c :: Int -> Int -> [[Int]] -> [Int] -> [Int]
abc402c n _m kas bs = scanl1 (+) $ elems cnt
  where
-- 食材Biが克服される日
    r :: UArray Int Int
    r = array (1,n) $ zip bs [1 ..]
-- 料理 i の食材が克服される日の最大値が、その解禁日
    ka = [maximum [r ! a | a <- as] | _:as <- kas]
-- 各日付で解禁される料理の個数
    cnt :: UArray Int Int
    cnt = accumArray (+) 0 (1,n) [(d,1) | d <- ka]

D - Line Crossing

問題 ABC402D

シグネチャを決める。

abc402d :: Int     -- N
        -> Int     -- M
        -> [[Int]] -- Ai, Bi
        -> Int     -- 答え

点の番号は1始まりでなく0始まりで考える。

例えば6角形のとき、1-2, 0-3, 4-5 は平行になっている。
これらを同一視する指標は、この数字を眺めていても見えてこない。
これらの線と垂直になる線の向きは、1.5(1と2の中点)-4.5(4と5の中点) を結ぶ線である。
これは $((A_i + B_i) / 2) \bmod (6/2)$ とわかる。

同様に、例えば5角形のとき、1-4, 2-3 は平行になっている。
これらと垂直になる線の向きは、0-2.5 を結ぶ線で、やはり $((A_i + B_i) / 2) \bmod (5/2)$ で得られる。

結局、2で割るのは不要で、$(A_i + B_i) \bmod N$ の値で分類すればよいとわかる。
平行になるものどうしは交差せず、平行でない異なるグループの線どうしは全て交わるので、その数を数える。

結果

それぞれに分類された線の本数 cnt[i] に対して、それより分類番号が小さい線の合計本数 cnt[0] + ... + cnt[i-1] を scanl (+) 0 で作っている。

import Data.Array

abc402d :: Int -> Int -> [[Int]] -> Int
abc402d n _m abs = sum $ zipWith (*) (elems cnt) (scanl (+) 0 $ elems cnt)
  where
    cnt = accumArray (+) 0 (0, pred n) [ (mod (a + b - 2) n, 1) | a:b:_ <- abs]

E - Payment Required

問題 ABC402E

シグネチャを決める。

abc402e :: Int     -- N
        -> Int     -- X
        -> [[Int]] -- Si, Ci, Pi
        -> Double  -- 答え

手持ちの残額 ($X$～0) または支払い総額 (0～$X$) をマスの番号とするスゴロクのDP（集めるDP）をする。
しかし、一つの問題は一度しか得点を得られないので、状態のもう一つの軸として、
AC済みの問題番号集合のビット表現 (0～$2^N-1$) または未正解の問題番号集合 ($2^N-1$～0) を考える。
DPの値は、それぞれの状態を出発点として、そこから最善を尽くしたときのスコアの期待値とする。

お金は残額 $r$ 、問題は未正解を1とする集合 $b$ で扱うことにして、状態のスコア期待値 $ex[b,r]$ は、

  • Nとおりの問題 $S_i, C_i, P_i$ のうち、まだ支払いが可能 $C_i \leq r$ かつ未回答 $i \not\in b$ のものについて、
  • 正解した場合スコアは $S_i$ 増えて、その先は $ex[b \cup \{i\}, r - C_i]$ である
  • 不正解の場合スコアは変化せず、その先は $ex[b, r - C_i]$ である
  • 前者になる確率 $P_i / 100$ 後者になる確率 $(100 - P_i)/100$ を掛けて足すと期待値
  • …が最大値になる問題（の値）を選ぶ。一つも解答できないとき0

となる。

結果

import Data.Bits
import Data.Array

abc402e :: Int -> Int -> [[Int]] -> Double
abc402e n x scps = ex ! (white, x)
  where
    iscps = zip [0 ..] scps
    white = bit n - 1
    bnds = ((0,0), (white, x))
    ex = listArray bnds $ map f $ range bnds
    f :: (Int,Int) -> Double
    f (b, r) = maximum $ 0 :
        [ ((ac + fromIntegral s) * pp + wa * (100 - pp)) / 100
        | (i, s:c:p:_) <- iscps, testBit b i, c <= r  -- 選べる問題の中で
        , let ac = ex ! (clearBit b i, r - c)         -- 正解した後の期待値
        , let wa = ex ! (b, r - c)                    -- 不正解の後の期待値
        , let pp = fromIntegral p ]

F - Path to Integer

問題 ABC402F

シグネチャを決める。

abc402f :: Int     -- N
        -> Int     -- M
        -> [[Int]] -- Aij
        -> Int     -- 答え

考える

単純に、マス $(1,1)$ から出発してマス $(i,j)$ に至った段階で作れる数の剰余を全て追跡することを考える。
それらを $R[i,j]$ に保存するとして
$R[1,1] = \{A_{1,1} \bmod M \}$
$R[i,j] = \{(10r + A_{i,j}) \bmod M \ |\ r \in R[i-1,j] \cup R[i,j-1]\}$
というDPを行い、$R[N,N]$ の最大の要素が答えになる。
しかしこの方法では、$\Big |R[N,N] \Big | \leq {}_{2N}C_N$ となり、$N \leq 20$ は大きすぎる。

半分全探索

指数関数的に場合の数が増えるということは、
サイズを抑えておけば思ったより爆発せずに済むということでもある。
「半分全探索」という技法で、マス $(1,1)$ から右、下に進む計算と
$(N,N)$ から左、上に進む計算を行い、$(1,N),\dots,(N,1)$の対角線位置のマスで
両側の結果を突き合わせると、
$(1,1)$ から $(i, N-i+1)$ への場合の数は ${}_N C_i$、$(N,N)$ からも同じで、
それらの組み合わせだけを調べればよい。

DPのステップ

素朴な方法では $10r + A_{i,j} \bmod M$ と一桁ずつくり上がりをさせれば済んだが、半分全探索ではそうはできない。
マスの数字が最終結果の何桁目になるかはその位置から確定する。
左下マスからのマンハッタン距離を$k$としたとき $10^k$ の重みになる。
マスの数字と合わせて $d_{i,j} \times 10^{2N-2-i-j} \bmod M$ が結果へ足し込まれる値になる。

突き合わせ

対角線マス $(i,N-i-1)$ での突き合わせは、$(1,1)$ からの値の集合を $U_i$ $(N,N)$ からの値の集合を $D_i$ として、$\max \{ (u + A_{i,N-i+1} + d) \bmod M \ | \ u \in U_i, d \in D_i\}$ を求めること。
中央部では $| U_{10} |, |D_{10}| \leq {}_{20}C_{10} = 184,756 \risingdotseq 2\times10^5$ とおりずつの組み合わせになるので、単純に総当たりすると間に合わない。

$U_i' = \{ (u + A_{i,N-i+1}) \bmod M \ |\ u \in U_i \}$ とおく。
また $\forall d \in D_i ; d < M$ とする。

このとき、最大値の候補は

  • $U_i'$ の各要素 $u$ に対して、和が $M$ 未満となる最大の $d \in D_i$ の値
  • $(\max U_i' + \max D_i) \bmod M$ これは、和が$M$を越えるとき最大で $M-2$

で、後者は二分探索的なやり方をする代わりに、尺取法で計算できる。
尺取法にしても計算量は事前のソートが支配的なのでオーダーは同じ。

結果

sco がDPの配列。要素は IntSet
左上と右下のマスはそれぞれのDPを計算し、
対角線のマスは突き合わせの計算をする。

import qualified Data.IntSet as IS

abc402f :: Int -> Int -> [[Int]] -> Int
abc402f n m ass = maximum [IS.findMax $ sco ! (i, succ n - i) | i <- [1 .. n]]
  where
    reg x = mod x m
    mul x y = reg $ x * y
    add x y = reg $ x + y
    base :: UArray Int Int -- 桁の重み 10^k
    base = listArray (0, 2 * pred n) $ iterate (reg . (10 *)) 1
    bnds = ((1,1),(n,n))
    arr :: UArray (Int,Int) Int -- A_ij
    arr = listArray bnds $ concat ass
    sco :: Array (Int,Int) IS.IntSet
    sco = listArray bnds $ map f $ range bnds
    f ij@(1, 1) = IS.singleton $ mul (arr ! ij) (base ! (2 * pred n))
    f ij@(i, j)
      | i == n, j == n = IS.singleton $ arr ! ij -- base = 1
      | otherwise =
        case compare (i + j) (succ n) of
          LT -> fsub [(pred i,j),(i, pred j)] v -- 左上マス
          GT -> fsub [(succ i,j),(i, succ j)] v -- 右下マス
          EQ -> IS.singleton $ maximum $ c0 : cs -- 対角線マス
      where
        v = mul (arr ! ij) (base ! (n + n - i - j))
        us = fsub [(pred i,j),(i, pred j)] v
        ds = fsub [(succ i,j),(i, succ j)] 0
        c0 = add (IS.findMax us) (IS.findMax ds)
        cs = gsub (IS.toDescList us) (IS.toAscList ds)
-- DPステップ
    fsub pqs v = IS.unions [IS.map (add v) (sco ! pq) | pq <- pqs, inRange bnds pq]
-- 突き合わせの尺取法
    gsub [] _ds = []
    gsub (u:us) ds
      | null ds1 = gsub us ds
      | otherwise = u + last ds1 : gsub us (last ds1 : ds2)
      where
        (ds1, ds2) = span (m - u >) ds

G - Sum of Prod of Mod of Linear

問題 ABC402G

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

abc402g :: [Int]  -- N,M,A,B1,B2
        -> Int    -- 答え

なんもわからん。
フレンズさんいわく

大変なのだ……

公式解説からさらにユーザ解説で、ごく短いPythonコードが示されているので、表面的に移植だけ。

abc402g :: [Int] -> Int
abc402g [n,m,a,b1,b2]
  | b1 > b2 = abc402g [n,m,a,b2,b1]
  | otherwise = sum
    [ div (a * a * pred n * n * (n + pred n)) 6
    , div (a * (b1 + b2) * n * pred n) 2
    , b1 * b2 * n
    , negate $ m * (a * h1 + b2 * f1)
    , negate $ m * (a * h2 + b1 * f2)
    , div (m * m * (g1 + f1 + g2 - f2)) 2]
  where
    (f1, g1, h1) = floorSum n m a b1
    (f2, g2, h2) = floorSum n m a b2

floorSum :: Int -> Int -> Int -> Int -> (Int,Int,Int)
floorSum _ 0 _ _ = (0, 0, 0)
floorSum n m a b = (f + a1 * nn + b1 * n, g, h + div (nn * (a1 * (n + pred n) + 3 * b1)) 3)
  where
    (a1,a2) = divMod a m
    (b1,b2) = divMod b m
    y = div (a2 * n + b2) m
    (ff, gg, hh) = floorSum y a2 m (pred m + a2 - b2)
    nn = div (n * pred n) 2
    f = n * y - ff
    h = nn * y + div (ff - gg) 2
    g = sum [ n * y * y - ff - 2 * hh
            , div (n * (n + pred n) * pred n * a1 * a1) 6
            , 2 * nn * a1 * b1
            , b1 * b1 * n
            , 2 * a1 * h
            , 2 * b1 * f ]
2
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
2
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?