ABC 417

Aug 3, 2025

ABC 417

ABC 417 に参加しました。

A 問題

文字列 SS の先頭 AA 文字、末尾 BB 文字を削除せよ。 dropEnd 関数を知っていると楽できますね。

solve :: StateT BS.ByteString IO ()
solve = do
  (!n, !a, !b) <- ints3'
  !s <- line'
  printBSB . BS.dropEnd b $ BS.drop a s

B 問題

数列 AA から数列 BB の要素を 1 つずつ削除せよ。 (\\\\) 一発で解ける模様です:

solve :: StateT BS.ByteString IO ()
solve = do
  (!n, !m) <- ints2'
  !xs <- U.toList <$> intsU'
  !ys <- U.toList <$> intsU'
  printBSB . unwordsBSB . U.fromList $ xs \\ ys

C 問題

数列 AA に対し条件 j−i=Ai+Ajj - i = A_i + A_j を満たす i,ji, j の数を求めよ。

本番で考えた方法

下の図で i=1i = 1 かつ A1=1A_1 = 1 のとき、 j>1j > 1 に対しては Aj=−1,0,1,..A_j = -1, 0, 1, .. である場合に条件を満たします:

   o----o----o----o----o
 A_1  A_2  A_3  A_4  A_5
       -1    0    1    2

ここで頻度列 ([..][..]) を持って、読み出し位置のオフセット (∣|) をズラして行くと、 jj に対して条件を満たす ii の数が O(1)O(1) で求められます:

[-    1    -    -    -]
          |0    1    2   j = 1
     |0    1    2    3   j = 2
|0    1    2    3    4   j = 3

という形で頑張りました。伝わらないかも……

シンプルな解放

Ai+i=j−AjA_i + i = j - A_j の形に変数分離 (f(i)=g(j)f(i) = g(j)) すると、各項の値が独立するため簡単になります。 j∈[0,N)j \in [0, N) の範囲で走査して O(N)O(N) で解けます。頭がいいですね:

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

  let lhs, rhs :: Int -> Int -> Int
      lhs i xi = i + xi
      rhs j xj = j - xj

  let !res = runST $ do
        freq <- UM.replicate (1 + n + 2 * 10 ^ 5) (0 :: Int)
        U.ifoldM'
          ( \acc j xj -> do
              dn <- fromMaybe 0 <$> (GM.readMaybe freq $! rhs j xj)
              GM.modify freq (+ 1) $! lhs j xj
              pure $! acc + dn
          )
          (0 :: Int)
          xs

  printBSB res

D 問題

NN 個の関数を連結するとき、様々な入力に対する出力を求めよ。それぞれの関数 fif_i は 1≤ai,bi,pi≤5001 \le a_i, b_i, p_i \le 500 の範囲で以下の通り定義する:

fi(t):={t+ai(t≤pi)max⁡(0,t−bi)(t>pi)f_i(t) := \begin{cases} t + a_i & (t \le p_i) \\ \max (0, t - b_i) & (t \gt p_i) \end{cases}

t>500t \gt 500 の間は、常に t−bit - b_i が選択されることが分かります。各点の入出力を t∈[0,500]t \in [0, 500] の範囲で持つことにすると、 t>500t \gt 500 の範囲は二分探索で計算できそうです。

各点で t∈[0,500]t \in [0, 500] の範囲で入出力表を持つことにして、最後の関数から順に (入力 → 最終出力) を計算していくと解けます。

E 問題

単純無向連結グラフにおいて、 XX から YY への辞書順最小パスを O(N2log⁡N)O(N^2 \log N) で求め、経路復元せよ。

Dijkstra 法において、コストを ByteString 型の経路にすると WA になりました。 Text 型の経路にすると AC しました。 ByteString の比較はバイト列の比較ですから、文字コードが 255 を超えると正しく判定できなくなるようです。

Misc