ABC 390

ABC 390 に参加しました。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
提出 AC AC AC TLE AC -
予想 diff 10 50 150 1,000 1,400 2,000
実際 diff 43 147 247 1,607 1,227 1,801

A 問題

\(1, 2, 3, 4, 5\) の順列が与えられたとき、隣接項の入れ替えによって \(1, 2, 3, 4, 5\) と一致させられるか答えよ。

modify と swap の組み合わせで解けます。 Haskeller の A 問題はハードモードです:

solve :: StateT BS.ByteString IO ()
solve = do
  !xs <- intsU'
  let trySwap i =
        let xs' = U.modify (\vec -> GM.swap vec i (i + 1)) xs
         in xs' == U.generate 5 (+ 1)
  printYn . U.or $ U.generate 4 trySwap

B 問題

与えられた数列が等比数列であるか調べよ。公比が分数の場合があり、除算を回避するのが無難です。 \(a : b = c : d \iff ad = bc\) より比率を比較できます:

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !xs <- intsU'
  let x1 = xs G.! 0
  let x2 = xs G.! 1
  let test y1 y2 = y2 * x1 == x2 * y1
  printYn . U.and $ U.zipWith test xs (U.tail xs)

Data.Ratio を使う回答が上手いです:

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !xs <- intsU'
  let r = xs G.! 0 % xs G.! 1
  let test y1 y2 = y1 % y2 == r
  printYn . U.and $ U.zipWith test xs (U.tail xs)

なお (%) のソースを見ると、ちゃんと約分してから (GCD で割ってから) Ratio に包んでいるようです。確かに約分しての比較で良いですね:

-- | 'reduce' is a subsidiary function used only in this module.
-- It normalises a ratio by dividing both numerator and denominator by
-- their greatest common divisor.
reduce ::  (Integral a) => a -> a -> Ratio a
{-# SPECIALISE reduce :: Integer -> Integer -> Rational #-}
reduce _ 0              =  ratioZeroDenominatorError
reduce x y              =  (x `quot` d) :% (y `quot` d)
                           where d = gcd x y

x % y                   =  reduce (x * signum y) (abs y)

C 問題

2 次元グリッドが与えられたとき、ある長方形 \(R := [x1, x2] \times [y1, y2]\) の中にすべての # が収まり、かつ \(R\) の中に . が無いかを調べよ。

2 次元配列のテンプレートを持っていると、定型的なプログラムで処理できます:

solve :: StateT BS.ByteString IO ()
solve = do
  (!h, !w) <- ints2'
  !gr <- getGrid' h w
  let (!ys, !xs) = U.unzip $ findIndicesIV (== '#') gr
  let y1 = U.minimum ys
  let y2 = U.maximum ys
  let x1 = U.minimum xs
  let x2 = U.maximum xs
  printYn $ and [gr @! (y, x) /= '.' | y <- [y1 .. y2], x <- [x1 .. x2]]

D 問題

集合 \(S := \{ A_i \}_i\) を \(\{ S_i \}\) に分割したとき、ユニークな \(\mathrm{XOR} \{ \mathrm{sum}(S_i) \}_i\) の数を求めよ。 (雰囲気で書きました)

\(A_i\) の値域が広い (\(A_i \lt 10^{17}\)) のが絶望的ですが、集合分割の場合の数は ベル数 らしく、 \(N = 12\) の場合は \(10^7\) 未満に収まるそうです。

というわけで、すべての分割 (partition) を列挙すれば解けます。 TLE が厳しい:

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !xs <- intsU'
  let eval = foldl' xor 0 . map (U.sum . U.backpermute xs . unBitSet n)
  let results = map eval $ partitionsOf (bit n - 1)
  let count = U.length . U.uniq . U.modify (VAI.sortBy compare) $ U.fromList results
  printBSB count

E 問題

制約 \(X \le 5000\) に注目します。ビタミンを価値 (v) 、カロリーを重さ (w) と言い換えると、概ねナップサック問題です。実装はそんなに難しくないですが、コンテスト中に気付くのが難しい。

F 問題

数列の孤島の数を数えよ。うーん

Misc

言語アップデート 2025

AtCoder の 言語アップデート 2025 (Discord) にて、対応作業を実施しました。

gksato さんの server-gen のおかげでスムーズに更新できました。レビューも懇切丁寧に実施頂きありがとうございました。

一旦インストールスクリプトを提出しました (install.toml) 。 GHC 9.8.4 に更新された他、以下のパッケージが追加されます:

まだ若干の更新点があるため、 PR を投げて行きたいと思います。

INLINE 以外信用しない

Haskell は 1 行の違いで 10 倍遅くなる言語です。 Main.hs 単ファイルだと問題無いのですが、ファイル分割すると顕著な違いが現れます。特に INLINE を付けなければ目を当たられなくなるほど遅くなる場合があります。

Data.Vector.Algorithms の関数には INLINE が付いていないため、 nub, nubBy, nubByMut が鈍足のようです。 gksato さん情報です。

またこちらも gksato さん情報ですが、 Intro.sort などは INLINABLE 指定です。 INLINABLE は実質何もしない pragma (体感) なので、やはり特殊化されず低速です。この辺り、 ベンチマークを根拠に PR を出そうと思います。

キーボード

moNa2 が欲しいかと言われると、本当に欲しいのは 34 キーの keyball, あるいは狂気の 16 キー・キーボードです。今持っていないということは、喉から手が出るほど欲しいわけでもないですね……。

音楽

Eluveitie の新曲 が出ていました。やはり僕の好みからは外れますが、 Thousandfold でスペースリークの悲哀を歌っていて (※) 関心を惹かれます。 ※ 嘘です
。