ABC 432
ABC 432 に参加しました。 D 問題で ac-library-hs を使用しました。
A 問題
数列を並び替え、最も大きな値を作成せよ。数列を降順ソートした後、連結して出力します:
solve :: StateT BS.ByteString IO ()
solve = do
!xs <- U.toList <$> intsU'
printBSB . concatMap show $ sortBy (comparing Down) xs
B 問題
数列を並び替え、 0 以外から始まる最も小さな値を作成せよ。全探索が楽なようです:
solve = do
!xs <- sort . BS.unpack <$> line'
printBSB . fromJust . find ((/= '0') . head) $ permutations xs
C 問題
難しめの問題です。問題文を省略します。
\(X\) または \(Y\) (\(X < Y\)) を合計 \(n_i\) 個取るとき、和 \(s\) が取り得る値の集合は、 \([n_iX, n_iY]\) の区間を \(d := Y - X\) で移動した点の集まりです。この集合を \(S_i\) とすると、 \(\{S_i\}_{i \in [1, N]}\) の共通集合の最大の値が必要です。
\(\{S_i\}\) が空集合でないためには \(n_iY \equiv n_jY \pmod d\) が必須です。この条件下では、積集合を \(S_i \cap S_j = [\max(n_iX, n_jX), \min(n_iY, n_jY)]\) により計算できます。
feat :: Int -> Int -> Int -> (Int, Int, Int)
feat a b n = (modX, minX, maxX)
where
d = b - a
maxX = b * n
minX = a * n
modX = maxX `mod` d
solve :: StateT BS.ByteString IO ()
solve = do
(!n, !a, !b)<- ints3'
!xs <- intsU'
let (mods, mins, maxes) = U.unzip3 $ U.map (feat a b) xs
let b1 = U.all (== U.head mods) mods
let l = U.maximum mins
let r = U.minimum maxes
let b2 = l <= r
if b1 && b2
then do
let d = b - a
printBSB . U.sum $ U.map ((`div` d) . (r -)) mins
else do
printBSB "-1"
D 問題
長方形が配置された空間にねじれを加えていく問題です。千切れた長方形もまとめてねじって行き、最終的な連結成分のサイズを回答します。
長方形毎に位置とサイズを追跡し、千切れた部分は後から連結判定することで、 \(O(4^N)\) で解けそうです。
長方形の隣接判定がこちら:
isAdj :: (Int, Int, Int, Int) -> (Int, Int, Int, Int) -> Bool
isAdj r1@(!y, !x, !h, !w) r2@(!y', !x', !h', !w')
| x + w == x' || x' + w' == x =
let yMin = max y y'
yMax = min (y + h - 1) (y' + h' - 1)
in yMin <= yMax
| y + h == y' || y' + h' == y =
let xMin = max x x'
xMax = min (x + w - 1) (x' + w' - 1)
in xMin <= xMax
| otherwise = False
長方形の追跡と、連結成分の個数確認が以下です。上下と左右のねじれでコードがダブっているとはいえ、重いです:
-- (2^n)^2 < 10^9. Neraly safe.
solve :: StateT BS.ByteString IO ()
solve = do
(!n, !w0, !h0) <- ints3'
!cds <- U.replicateM n ((,,) <$> char' <*> int' <*> int')
-- track rects
let res1 = U.foldl' step s0 cds
where
s0 = U.singleton (0, 0, h0, w0)
step rects ('X', !atX, !dy) = U.concatMap f rects
where
f (!y, !x, !h, !w)
| x + w <= atX = U.singleton (y - dy, x, h, w)
| x >= atX = U.singleton (y + dy, x, h, w)
| otherwise = U.fromListN 2 [b1, b2]
where
b1 = (y - dy, x, h, atX - x)
b2 = (y + dy, atX, h, x + w - atX)
step rects ('Y', !atY, !dx) = U.concatMap g rects
where
g (!y, !x, !h, !w)
| y + h <= atY = U.singleton (y, x - dx, h, w)
| y >= atY = U.singleton (y, x + dx, h, w)
| otherwise = U.fromListN 2 [b1, b2]
where
b1 = (y, x - dx, atY - y, w)
b2 = (atY, x + dx, y + h - atY, w)
step _ _ = error "unreachable"
-- merge and return counts
let res = U.filter (/= 0) $ U.create $ do
let len = G.length res1
groups <- Dsu.new len
counts <- U.unsafeThaw $ U.map (\(!_, !_, !h, !w) -> h * w) res1
U.iforM_ res1 $ \i r -> do
let rects = U.take i res1
U.iforM_ rects $ \i' r' -> do
when (isAdj r r') $ do
-- change the belonging group
r1 <- Dsu.leader groups i
r2 <- Dsu.leader groups i'
r <- Dsu.merge groups i i'
-- move the count to the group
a1 <- GM.exchange counts r1 0
a2 <- GM.exchange counts r2 0
GM.write counts r $ a1 + a2
pure counts
printBSB $ U.length res
printBSB . unwordsBSB $ U.modify VAI.sort res
なお 解説 によると、長方形の区間は \(N = 14\) のとき最大で \(471\) になるそうです。 \(4^N\) ではないのですね……。安易な計算量解析で結論を出してはいけないことが分かります。形上せよ！
E 問題
Clamped range sum 的な問題です。僕は本番で解けませんでしたが、頻度分布を持てば解けるようです。確かに……。
- エッジケースとして、 clamp のクエリが \(l > r\) である場合があります。
感想
D のような PAST 的、実務的な泥臭い問題が好きです。
Misc
音楽
Bliss of Flesh の 新盤 が出ました。最高の出来とは言えないのですが、やはり曲調が僕の中では No. 1 です。
これが最後のアルバムとなるのでしょうか。誰も歳には勝てませんね。