ABC 340, exgcd

競技プログラミング

ABC 340

ABC 340 に参加しました。

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} &= \begin{vmatrix} \mathbb{U} \mathbb{V} \mathbb{E} \end{vmatrix}^{t} \\ &= \begin{vmatrix} u_{1} & u_{2} & u_{3}\\ v_{1} & v_{2} & v_{3}\\ \mathbb{e}_{x} & \mathbb{e}_{y} & \mathbb{e}_{z} \end{vmatrix} \\ & \{3 行目に関する余因子展開\} \\ &= \mathbb{e}_{x} \begin{vmatrix} u_{2} & u_{3} \\ v_{2} & v_{3} \end{vmatrix} + \mathbb{e}_{y} \begin{vmatrix} u_{3} & u_{1} \\ v_{3} & v_{1} \end{vmatrix} + \mathbb{e}_{z} \begin{vmatrix} u_{1} & u_{2} \\ v_{1} & v_{2} \end{vmatrix} \\ &= \mathbb{e_x} (u_2 v_3 - u_3 v_2) + \mathbb{e_y} (u_3 v_1 - u_1 v_3) + \mathbb{e_z} (u_1 v_2 - u_2 v_1) \\ & \{2 次元ベクトルの場合 (u_3 = v_3 = 0)\} \\ &= \mathbb{e_z} (u_1 v_2 - u_2 v_1) \end{aligned} \\ \]

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

\[ \begin{aligned} \mathbb{A} &:= \begin{bmatrix} A\\B\\0 \end{bmatrix}, \mathbb{X} := \begin{bmatrix} x\\y\\0 \end{bmatrix} \\ \frac {|\mathbb{A} \times \mathbb{X}|} {2} &= 1 \iff |Ay - Bx| = 2 \iff Ay - Bx = \pm2 \end{aligned} \\ \]

この等式を満たす整数値 \(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 は頻出ですね。