ABC 385

ABC 385 に参加しました。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
提出 AC AC AC AC - WA
予想 diff 10 300 200 1,000 ? 1,600
実際 diff 14 77 446 1,171 1,406 1,905

A 問題

3 つの整数を 2 つまたは 3 つのグループに分けたとき、それぞれのグループの整数の和がすべて等しくできるか判定せよ。こんな感じでどうでしょう。

solve :: StateT BS.ByteString IO ()
solve = do
  !xs <- intsU'
  printYn $ U.any (\x -> 2 * x == U.sum xs || 3 * x == U.sum xs) xs

追記: 嘘解法の指摘を頂きました。うわあああああ

A 問題，
2 3 4
とかで変なことが起こりませんか？

— とーらす🌸📦🌕✨🌂🎧 (@torus711) December 21, 2024

B 問題

グリッド上を指示通り動くとき、訪問できる家の数を求めよ。 \(X, Y\) という名前で y, x 座標の値が与えられて、こういう問題はいつも疑問です。

dir :: Char -> (Int, Int)
dir 'U' = (-1, 0)
dir 'D' = (1, 0)
dir 'L' = (0, -1)
dir 'R' = (0, 1)
dir _ = error "unreachable"

solve :: StateT BS.ByteString IO ()
solve = do
  (!h, !w, pred -> !y0, pred -> !x0) <- ints4' -- 1
  !gr <- getGrid' h w
  moves <- U.map dir . U.fromList . BS.unpack <$> line'
  let points = U.scanl' step (y0, x0) moves -- 2
        where
          step yx@(!y, !x) dir
            | gr @! yx' == '#' = yx
            | otherwise = yx'
            where
              !yx' = add2 yx dir
  let res = U.length . U.filter ((== '@') . (gr @!)) . U.uniq $ U.modify VAI.sort points -- 3
  let (!resY, !resX) = U.last points
  printBSB (resY + 1, resX + 1, res)

C 問題

整数列を任意の K 個飛ばしで見たとき、等しい値の列の長さの最大値を求めよ。すべての点から \(1, 2, 3, .. N - 1\) 個飛ばしを全探索するとします。 調和級数 の和 \(\sum\limits_{i \in [1, n] \cap \mathbb{Z}} \frac {1} {i}\) は \(\log n\) 程度の大きさであり、愚直に探索すれば \(O(N \log N)\) で解けます。実際は枝刈りでほぼ \(O(N)\) だと思います。

追記: 計算量の考察が間違ってそうです…… orz

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !xs <- intsU'

  -- 位置 `i` から `d` 個飛ばしで等しい値の列の長さを求める
  let step :: Int -> Int -> Int
      step i0 d = inner $ i0 + d
        where
          x0 = xs G.! i0
          inner i
            | i >= n || xs G.! i /= x0 = 1
            | otherwise = 1 + inner (i + d)

  let Max res =
        Max 1 -- 1
          <> U.foldMap' -- 2
            (\i0 -> U.foldMap (Max . step i0) (U.generate (n - 1) (+ 1)))
            (U.generate n id)
  printBSB res

D 問題

B 問題の sparse 版です。苦戦しました。なお B 問題とは異なり、 \(X, Y\) という名前で本当に x, y 座標の値が与えられる上に、 Y 軸の向きが反転しています。

以下の方法で解きました。

E 問題

Advent Calendar が終わってから考えます。

F 問題

同上です。