ABC 340, exgcd

Feb 11, 2024

競技プログラミング

ABC 340

ABC 340 に参加しました。

A 問題

数列 $a, a + d, .., b$ を生成します。リストの range syntax を使ったり、 iterate を使うとシンプルに書けるようです:

[a, a + d .. b]
takeWhile (<= b) $ iterate (+ d) a

僕は unfoldr を使ってしまいました。

B 問題

クエリ処理の問題です。 Haskeller にとっては複数の厄介事が絡み合うため、茶 diff 相当かもしれません。

クエリ処理の方針

スタックを使います。いずれのクエリでも文字列 A の後ろ側に関心があるためです。

クエリ 1: A の末尾に値 x を追加する
クエリ 2: A の後ろから k 番目の値を求め、標準出力に出す

Haskell においてはリストがスタックとして使えます。

解答の出力

クエリ 2 においては、求めた値を標準出力に出す必要があります。クエリ 2 が来る度に都度 print してしまうのが簡単です。ただしクエリ処理の関数には IO モナドが必要です。

都度 print する解答

main :: IO ()
main = do
  !q <- ints1
  !qs <- U.replicateM q ints2

  let f :: [Int] -> (Int, Int) -> IO [Int]
      f !acc (1, !x) = return (x : acc)
      f !acc (2, !k) = do
        print $ acc !! pred k
        return acc
      f _ _ = error "unreachable"

  U.foldM'_ f [] qs

より Haskell らしい解答としては、クエリ処理を純粋関数とします。戻り値を答えの一覧とし、最後に print します。 unfoldr などが適切な関数だと思います。

unfoldr による解答

main :: IO ()
main = do
  !q <- ints1
  !qs0 <- U.replicateM q ints2

  let !res = U.unfoldr f ([], qs0)
        where
          f (!acc, !qs) = case U.uncons qs of
            Nothing -> Nothing
            Just ((1, !x), qs') -> f (x : acc, qs')
            Just ((2, !k), qs') -> Just (acc !! pred k, (acc, qs'))
            _ -> error "unreachable"

  U.forM_ res print

答えの一覧をリストに溜めながら foldl' して、最後に reverse するのも OK です。計算量のオーダーは $O(N)$ のまま変わりません。競技プログラミングにおいては reverse は実質無料です。

C 問題

$n$ を何度も半分へ割っていきます。 $n \le 10^{17}$ より大きな $n$ が与えられる場合に注意します。解説にある通り、計算結果のキャッシュを持つ (メモ化する) と考察を放棄できます。

ここではメモ化に IntMap を使用します。素直に書くとこうなりました:

solve :: Int -> IM.IntMap Int -> (Int, IM.IntMap Int)
solve !x !im0 = case IM.lookup x im0 of
  Just !cost -> (cost, im0)
  Nothing -> (cost', IM.insert x cost' im')
    where
      !x1 = x `div` 2
      !x2 = x - x1
      (!cost', !im') =
        let (!cost1, !im1) = solve x1 im0
            (!cost2, !im2) = solve x2 im1
         in (x + cost1 + cost2, im2)

State モナドを使うとこうなりました:

solve :: Int -> IM.IntMap Int -> (Int, IM.IntMap Int)
solve !x !im0 = case IM.lookup x im0 of
  Just !cost -> (cost, im0)
  Nothing -> (cost', IM.insert x cost' im')
    where
      !x1 = x `div` 2
      !x2 = x - x1
-      (!cost', !im') =
-        let (!cost1, !im1) = solve x1 im0
-            (!cost2, !im2) = solve x2 im1
-         in (x + cost1 + cost2, im2)
+      (!cost', !im') = (`runState` im0) $ do
+        !cost1 <- state $ solve x1
+        !cost2 <- state $ solve x2
+        return $ x + cost1 + cost2

もっとシュッとした解答の人も多くてさすがです。それがしの提出はスパゲッティゆえに……

D 問題

D 問題は Dijkstra 法 (辺に重みがある場合の BFS) をやるだけのようです。

E 問題

遅延セグメント木を使うと区間 add ができます。緑 diff とは……

遅延セグメント木のはずがないと、メタ読みで F, G に行ってしまいました。メタを外してくるのは面白いですね。

F 問題

解けませんでした。平行四辺形の面積は外積の長さですから、三角形の面積はその半分です。式を整理すると、拡張ユークリッドの互除法で解けるそうです。

外積は行列式を使って表現できます。手計算の際には、行列をループさせると余因子の符号を考えなくて済みます。

$\begin{aligned} \mathbb{U} \times \mathbb{V} &=$

今回の計算においては $\mathbb{U} = \mathbb{A}, \mathbb{V} = \mathbb{X}$ を代入します。三角形の面積が 1 に等しい条件は、以下の等式が成り立つことです。

$\begin{aligned} \mathbb{A} &:=$

この等式を満たす整数値 $x, y$ は拡張ユークリッドの互助法によって求まります。実装は @4tsuzuru さんの exgcd 関数を拝借しています。

TODO: $x, y$ の変域の考察

拡張ユークリッドの互除法

exgcd が活躍する具体例は、算数でよくあるバケツで水を組む問題です。容量 $A$ のバケツと容量 $B$ のバケツを使って、お風呂にちょうど $L$ リットルの水を汲みます。

互いに疎な整数 $A, B$ に対して $n_A A + n_B B = 1$ を満たす整数 $n_A, n_B$ の組が存在します。 exgcd によって $n_A, n_B$ を求めると、両辺を $L$ 倍して任意の $L \mathrm[L]$ の水を汲むことができます。

類題は ABC 186 - E でした。フレンズさん回で exgcd は頻出ですね。