ABC 389, Justfile, 競プロ盆栽.hs

ABC 389

ABC 389 に参加しました。後半は高 diff 二分探索の良問だった模様です。

A 問題

文字列 AxB が与えられたとき、 A * B を計算せよ。パターンマッチします:

solve :: StateT BS.ByteString IO ()
solve = do
  [!a, !_, !b] <- BS.unpack <$> line'
  printBSB $ digitToInt a * digitToInt b

B 問題

整数 \(X\) が与えられとき、 \(N! = X\) となる \(N\) を求めよ。遅延評価の出番です:

solve :: StateT BS.ByteString IO ()
solve = do
  !x <- int'
  printBSB $ fromJust $ elemIndex x $ scanl' (*) (1 :: Int) [1..]

C 問題

キューに要素追加・削除していく時、キューの中で \(k - 1\) 番目の要素の累積和を求めよ。先に全要素の累積和配列を作っておけば、 pop 回数 \(\mathrm{nPop}\) を用いて \(S[k + \mathrm{nPop}] - S[\mathrm{nPop}]\) が答えになります。

まずクエリをパースします:

solve :: StateT BS.ByteString IO ()
solve = do
  !q <- int'
  !qs <-
    U.replicateM q $
      int' >>= \case
        1 -> (1 :: Int,) <$> int'
        2 -> pure (2 :: Int, -1)
        3 -> (3 :: Int,) <$> int'
        _ -> error "unreachable"

Push クエリを先読みし、累積和配列を作ります:

  let (!spawns, !other) = U.partition ((== 1) . fst) qs
  let pos = dbgId $ U.scanl' (+) (0 :: Int) $ U.map snd spawns

unfoldr でクエリ 3 の答えを作ります:

  let res = U.unfoldr f (0 :: Int, other)
        where
          f :: (Int, U.Vector (Int, Int)) -> Maybe (Int, (Int, U.Vector (Int, Int)))
          f (!nPop, !qs_) = do
            (!q, !rest) <- U.uncons qs_
            case q of
              (1, !_) -> f (nPop, rest)
              (2, !_) -> f (nPop + 1, rest)
              (3, pred -> k) -> pure (pos G.! (k + nPop) - pos G.! nPop, (nPop, rest))

  printBSB $ unlinesBSB res

D 問題

半径 \(r\) の円に内包される正方形の数を数えよ。第一象限 (\(Q_1 = \{ (x, y) \mid x > 0, y > 0 \}\)) 中のカウントを 4 倍し、 X, Y 軸上の正方形の数を足すと答えになります。行ごとに右端の正方形の位置を二分探索すれば、 \(O(r \log r)\) で解答できます。

-- | 正方形の 4 点と原点の間の距離が r 以下ならば true
testPoint :: Int -> Int -> Int -> Bool
testPoint r y x = all (<= 4 * r * r) [d1, d2, d3, d4]
  where
    y2 = 2 * y + 1
    y1 = 2 * y - 1
    x2 = 2 * x + 1
    x1 = 2 * x - 1
    dist a b = a * a + b * b
    d1 = dist y1 x1
    d2 = dist y1 x2
    d3 = dist y2 x1
    d4 = dist y2 x2

-- | 行をカウント
solveRow :: Int -> Int -> Int
solveRow r y = fromMaybe 0 $ bisectL 0 r $ \x -> testPoint r y x

-- | 四分円をカウント
solveQuater :: Int -> Int
solveQuater r = sum [solveRow r y | y <- [1 .. r + 1]]

-- | 円全体をカウント
f :: Int -> Int
f r = solveQuater r * 4 + 4 * (r - 1) + 1

solve :: StateT BS.ByteString IO ()
solve = do
  !r <- int'
  printBSB $ f r

E 問題

頑張って解説 AC するかも……？

F 問題

頑張って解説 AC するかも……？

Misc

just

お試しタスクランナー の後、 ac-library-hs に Justfile を導入しました (該当のコミット) 。これが結構良い感じです。書き味良し、見た目良し！:

$ j t # サブディレクトリからも実行可

ABC 環境にも導入しました (該当のコミット) 。リポジトリ毎に簡潔なコマンドレシピを持てるようになり、見通しが良くなったと思います。

just の解説は 📜タスクランナーのjustを試してみた - Minerva が良いです。 tomoya さんのブログ と同系統のレイアウトで、ページも格好いい。

言語アップデート 2025

cabal-plan の license-report および gksato さんの server gen のおかげで、特に問題無く更新できそうです。最悪、 10 分あれば今すぐに更新を申請できます。良かった〜〜！

未だ天下の C++, Python の更新申請が無いので、新ジャッジ環境のテストは 2 月になると予想しています。今振り返ると、 ac-library-hs を作り始めたタイミング (昨年 10 月) は、ちょうど十分な時間が得られて良かったと思います。十二分にバッファを取ったつもりでしたが、テストが重かったです。

競プロ盆栽.hs

ac-library-hs 開発は 競プロ盆栽.hs に載せています。直前まで ac-library-hs を弄っており、実はほぼ 3 日で書きました。ブログ替わりの Issue を下敷きにしたのが良かったです。

競プロ盆栽.hs は半分以上テストの話です。何と言っても QuickCheck が大活躍しました。サクっと乱数生成してエラー内容を確認できるのが嬉しい。要所のバグを早期確認できるのはもちろん、単位元やモノイド則のように明らかに重要な法則がある場合は効果抜群です。

気が早いですが、今年も Haskell のカレンダーに何か出したい気はします。順当に行くなら、 Heuristic コンテストでどれだけ戦えるかに興味があります。 Heuristic の能力を磨くのは相当しんどいはずですが、 CTF よりはマシです。やっていくのか……？？