ABC 378 / 東京観光、 Emacs

ABC 378

ABC 378 に参加しました。レーティング微減です。

Table 1: Diff 予想
問題	A 問題	B 問題	C 問題	D 問題	E 問題	F 問題
提出	AC	AC	AC	AC	TLE	AC
Diff 予想	10	20	400	800	1,500	1,100
Diff 実際	22	118	191	587	1,406	1,436

A 問題

同じ色のボールを 2 つずつ捨てていくとき、捨てられるペアの数を求めよ。色ごとにボールの数を数えて 2 で割った和が答えです。

import Data.List;main=interact$show.sum.map((`div`2).length).group.sort.map(read @Int).words

B 問題

ゴミが定期的に収集されるとき、最寄りのゴミ収集日を求めよ。愚直に分岐するのが簡単だと思います。

let !d' = d `mod` q
(d +) $ case compare d' r of
  EQ -> 0
  GT -> r + q - d'
  LT -> r - d'

C 問題

数列を走査するとき、それぞれの \(A_i\) と同じ値が出現した最寄りの位置を求めよ。 Map を持って数列を走査します。

mapAccumL 案件ですが、 vector には無いので State モナドを使いました:

let !res = (`evalState` IM.empty) $ U.imapM (\i x -> state (step i x)) xs
      where
        -- step :: i -> x -> state -> (x', state)
        step (succ -> i) x im = case IM.lookup x im of
          Just i' -> (i', im')
          Nothing -> (-1, im')
          where
            !im' = IM.insert x i im

上のコードの提出は、 mapAccumL よりも 100 ms 程度遅かったです。 mapM + State は遅い！　cojna さんの mapAccum を借りると mapAccumL と同速程度に速くなります。

D 問題

グリッド上で長さ K の単純道 (頂点の重複が無いパス) の数を求めよ。愚直解が通ります。大雑把に見積もると \(O(HW \cdot N!)\) は TLE しますが、もう少し正確に考えると \(O(HW \cdot 4 \cdot 3^{K-1})\) になります (公式解説) 。

この DFS は大まかに次の形で実装できます:

!dist <- UM.replicate (h * w) undef
(\f -> fix f (0 :: Int) source) $ \loop d1 v1 -> do
  GM.write dist v1 d1    -- 訪問済みにする
  -- 隣接頂点を調べる、など (省略)
  GM.write dist v1 undef -- 未訪問にする

計算量の見積もりを間違えました。順位表を見るとペナルティの数が少なかったため、メタ読みで愚直解が通ると分かりました。