ABC403振り返り

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）に参加したので振り返り。

コンテスト成績証

A - Odd Position Sum

リストの要素を1つ飛ばしで集計すれば良い。

main :: IO ()
main = do
    n <- val ucInt
    as <- list1 ucInt

    let s = f as
            where f [] = 0
                  f [a] = a
                  f (a:_:bs) = a + f bs

    print s

B - Four Hidden

\(T\) の先頭から \(U\) と照合し、照合中の \(T\) の文字が \(U\) と同じ文字または ? なら照合OKとする。 照合NGなら、 \(T\) の次の文字から再度照合する。

解説では、 ? がちょうど4つであることから、 'a' から 'z' までの4重ループする方法も解説されていたけど、 そっちは思いつかなかった。。。

main :: IO ()
main = do
    ts <- list1 ucChar
    us <- list1 ucChar

    let result = f ts us
            where f :: [Char] -> [Char] -> [Bool]
                  f as bs
                      | length as < length bs = []
                      | otherwise = and (zipWith (\a b -> a == '?' || a == b) as bs) : f (tail as) bs

    putStrLn $ if or result then "Yes" else "No"

C - 403 Forbidden

クエリ \(1\) とクエリ \(2\) で付与される閲覧権限を、ユーザ毎に IntSet で管理する方針。 全ページに閲覧権限が付与される（クエリ \(2\) ）場合は、 \(1 \le Y \le M\) でない値（ \(0\) など）で表現することにする。

main :: IO ()
main = do
    (n,k,q) <- int3
    queries <- list2 q ucInt

    auth <- newArray @IOArray (1,n) IS.empty

    for_ queries $ \query -> do

        case query of
            [1,x,y] -> modifyArray auth x (IS.insert y)
            [2,x] -> modifyArray auth x (IS.insert 0)
            [3,x,y] -> do
                s <- readArray auth x
                putStrLn $ if IS.member 0 s || IS.member y s then "Yes" else "No"

D - Forbidden Difference

コンテスト中1時間以上取り組んで、時間内には解けず・・・

\(D > 0\) の場合

以下の入力を例とする。

\(\lvert A_i - A_j \rvert = 3\) となるとき、 \(A_i,A_j\) は、 \((0,2),(7,9),(8,10,12),(15,17),(26,28,30)\) のいずれかの組にともに属する。 また、要素を削除するとき、同じ値の要素はすべて \(A\) から削除する必要がある（例えば、 28は \(A\) に2個存在するが、 \(\lvert B_i - B_j \rvert \ne 0\) を満たすためには2個とも削除する必要がある）。 したがって、上記の組毎に、「どの要素の値を削除すれば、削除する要素数が最小になるか」を考えれば良く、最終的な答えは削除した要素数の組毎の和である。

一般に、ある要素の値 \(x\) に対して、 \(x \pm jD \ (j = 1,2, \dotsc)\) であって、 \(j\) が連続している要素の値の組を探し、組毎に削除する \(A\) の要素数が最小となるよう、削除する要素の値を決めれば良い。

（コンテスト中はここまで考察できた。その後の考察はコンテスト後。）

ここで、 \(x + jD \equiv x \pmod D\) であることから、実装上は要素の値 \(x \ (0 \le x \le D)\) に対して \(x + jD \ (j = 1,2,\dotsc)\) を求め、 \(j\) が連続していない箇所で組を区切れば良い。

次に、組毎に削除する要素の値を決める方法を考える。 制約として、ある要素の値 \(x\) を削除しないならば、 \(x+D\) 及び \(x-D\) の要素の値は削除する必要がある。 逆に、 \(x\) を削除する場合、 \(x+D\) 、 \(x-D\) は削除しても削除しなくても良い。 そのため、単純に要素の値を1つ飛ばしで削除すれば良い、というわけではなく、削除する要素の値の選び方には様々なパターンがありうる。

そこで、動的計画法を用いて、削除すべき \(A\) の要素数の最小値を求めることにする。 ある組 \(G\) に注目したとき、 \({dp}_0(k), \ {dp}_1(k)\) を \(k\) 番目の要素の値までに取り除いた \(A\) の要素数の最小値と定義する （添字 \(0,1\) はそれぞれ、 \(k\) 番目の要素の値を削除しない・するに対応する）。

緩和式は以下の通り。ここで \(c\) は、 \(k\) 番目の要素の値の、 \(A\) における要素数を表す。

\(G\) の要素数を \(m\) とすれば、求めるものは \(\min({dp}_0(m),\ {dp}_1(m))\) である。この値を、すべての組に対して求めて合計する。

\(D=0\) の場合

解説を読むまで気づかなかったが、 \(D=0\) の場合、 \(\lvert A_i - A_j \rvert = 0\) となる。これは言い換えると、 \(A\) 内に同じ値の要素が存在している、ということである。 このことから、 \(B\) では値が重複する要素が存在しないことがわかる。 そのため、削除する \(A\) の要素数は、 \(A\) の要素数から \(A\) のユニークな要素の数を引けば良い。

実装

上記を踏まえ、実装は以下の通り。

solve :: Int -> [Int] -> Int
solve d as
    | d == 0 = length as - length (freqI as)
    | otherwise =
          let cs = hist (0,10^6) as
              ds = concatMap (filter ((/=1) . length) . (\i -> (chain (\x y -> x + d == y) . filter ((/=0) . (cs!))) [i,i+d..10^6])) [0..d-1]

              results = flip map ds $ \grp ->
                  let m = length grp
                      dpt = runSTUArray $ do
                          dp <- newArray ((0,0),(m,1)) maxBound
                          writeArray dp (0,0) 0
                          writeArray dp (0,1) 0
                          for_ (zip [1..m] grp) $ \(i,x) -> do
                              r0 <- readArray dp (i-1,0)
                              r1 <- readArray dp (i-1,1)
                              writeArray dp (i,0) r1
                              writeArray dp (i,1) (cs!x + min r0 r1)
                          return dp

                  in min (dpt ! (m,0)) (dpt ! (m,1))

          in sum results

hist :: (Int, Int) -> [Int] -> UArray Int Int
hist bnds = accumArray @UArray (+) 0 bnds . map (,1)

chain :: (a -> a -> Bool) -> [a] -> [[a]]
chain _ [] = []
chain _ [a] = [[a]]
chain f (a:b:as)
    | a `f` b   = let (k:ks) = chain f (b:as)
                  in (a:k) : ks
    | otherwise = [a] : chain f (b:as)

cs で、要素の値に対応する \(A\) の要素数を Array に格納している。 ds では組を生成し、要素の値に対応する \(A\) の要素数を求めている。

1. chain 関数について

   当初、グルーピングには groupBy を使用していたが、意図した通りの組にならないことがわかった。 これは、 groupBy がグルーピングするとき、リストの隣り合う要素を比較するのではなく、リストの先頭要素と残りの要素を比較する、という動作をするためである。 そのため、隣り合う要素を比較してグルーピングする chain 関数を作成した。 以下のように動作する。

   λ> groupBy (\x y -> x + 2 == y) [1,3,5,7,9]
   [[1,3],[5,7],[9]]
   λ> chain (\x y -> x + 2 == y) [1,3,5,7,9]
   [[1,3,5,7,9]]

振り返り・感想

今回は割と集中できて（コンテストの間、妻に子の世話をお願いした。大変感謝）、C問題まで割と調子良く、20分くらいでさっくり解けた。 そのため、幸い（？）にもレートはちょっとだけ上がった。 とはいえ、D問題が解けなかったのには変わりなく、不完全燃焼。。。

D問題は、 \(D\) 飛ばしで要素の値をグルーピングするところまでは手を動かしながらたどり着けたが、そこから先、削除する要素の値を選ぶのに動的計画法を使うところまでいけなかった。。。 最初、要素の値を組から1つ飛ばしで選べば良い、と考えてしまっており、ドツボにハマってしまった。 ただ他にも、D問題の初回提出時点で以下のようにいくつか考慮漏れがあり、動的計画法を実装できていたとしても難しかったかもしれない。

• 制約に書いてあるのに \(A_i = 0\) を考慮していなかった（そのため、 UArray の範囲外参照でREとなったが、ジャッジ環境でしかREが出ず、原因がなかなかつかめなかった）
• 最初に提出した時点で、 \(j\) が連続していないときの考慮ができていなかった（ chain 関数によるグルーピングが必要なことを認識していなかった）
• 前述の通り、 \(D=0\) のケースを考慮できていなかった

特にREについては、制約通りに実装できているかチェックすれば防げた問題なので、制約を満たしているかも確認しよう。 上限は計算量の兼ね合いで自然と考えていると思うが、下限についてはおろそかになりがち。 今回のように、配列のインデックスに使うような値はちゃんと制約通りの範囲を確保しているか確認しよう。

考察で、「問題をいくつかの小問題に分割できないか」と考えるのは常套手段のようだ。 今回だと、要素の値を適切にグルーピングして、グループそれぞれについて動的計画法を適用する、といったように。 「小問題への分割」は競技プログラミングに限らず色々な場面で有効な考え方だと思われるので、意識して使いこなせるようにしたい。