ABC 417
ABC 417 に参加しました。
A 問題
文字列 \(S\) の先頭 \(A\) 文字、末尾 \(B\) 文字を削除せよ。 dropEnd 関数を知っていると楽できますね。
solve :: StateT BS.ByteString IO ()
solve = do
(!n, !a, !b) <- ints3'
!s <- line'
printBSB . BS.dropEnd b $ BS.drop a s
B 問題
数列 \(A\) から数列 \(B\) の要素を 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 問題
数列 \(A\) に対し条件 \(j - i = A_i + A_j\) を満たす \(i, j\) の数を求めよ。
本番で考えた方法
下の図で \(i = 1\) かつ \(A_1 = 1\) のとき、 \(j > 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
ここで頻度列 (\([..]\)) を持って、読み出し位置のオフセット (\(|\)) をズラして行くと、 \(j\) に対して条件を満たす \(i\) の数が \(O(1)\) で求められます:
[- 1 - - -]
|0 1 2 j = 1
|0 1 2 3 j = 2
|0 1 2 3 4 j = 3
という形で頑張りました。伝わらないかも……
シンプルな解放
\(A_i + i = j - A_j\) の形に変数分離 (\(f(i) = g(j)\)) すると、各項の値が独立するため簡単になります。 \(j \in [0, 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 問題
\(N\) 個の関数を連結するとき、様々な入力に対する出力を求めよ。それぞれの関数 \(f_i\) は \(1 \le a_i, b_i, p_i \le 500\) の範囲で以下の通り定義する:
\[
f_i(t) := \begin{cases}
t + a_i & (t \le p_i) \\
\max (0, t - b_i) & (t \gt p_i)
\end{cases}
\]
\(t \gt 500\) の間は、常に \(t - b_i\) が選択されることが分かります。各点の入出力を \(t \in [0, 500]\) の範囲で持つことにすると、 \(t \gt 500\) の範囲は二分探索で計算できそうです。
各点で \(t \in [0, 500]\) の範囲で入出力表を持つことにして、最後の関数から順に (入力 → 最終出力) を計算していくと解けます。
E 問題
単純無向連結グラフにおいて、 \(X\) から \(Y\) への辞書順最小パスを \(O(N^2 \log N)\) で求め、経路復元せよ。
Dijkstra 法において、コストを ByteString 型の経路にすると WA になりました。 Text 型の経路にすると AC しました。 ByteString の比較はバイト列の比較ですから、文字コードが 255 を超えると正しく判定できなくなるようです。