This article is not translated into English yet. Below is the Japanese original.

ABC 364, 遅延セグ木の定数倍高速化

ABC 364

ABC 364 に参加しました。

問題A 問題B 問題C 問題D 問題E 問題F 問題
体感4004003001,0001,6001,700
実際29401891,1361,4961,878
Table 1: 体感 diff

A 問題

長さ 2 の窓で見るのが良いですね。僕は group 関数に飛びついてしまい、厄介な処理になりました。

main=interact$y.or.(zipWith(&&)<*>tail).map(elem 'w').init.words;y b|b="No"|0<1="Yes"
Listing 1: ワンライナ (汚い)

B 問題

グリッドの問題です。 グリッドの入力処理 では Array が登場しますし、 Haskell 入門者には難問です。高橋くんの位置の追跡には畳み込みが登場します。

-- 和の計算
foldl' (+) (0 :: Int) [0 :: Int, 1, 2, 3]
Listing 2: 単純な畳込み
-- 高橋くんの移動の計算
foldl' walk (y0, x0) "LRUUDDLR"
Listing 3: 今回の問題も、実は単純な畳込み

脱線

naoya さんのコードには、以下の lrud が登場しました:

lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]

そういえばトップレベルでパタンマッチできるのですね。トップレベルのタプルの中身を正格評価しつつ {-# NOINLINE #-} を付けるなど、活用できそうです。

C 問題

それぞれの系列を降順ソートして貪欲に解きます。比較演算は strict な方 (x≥x \ge ではなく x>x \gt) です。 Strict な演算子というのは競プロ方言か何かで、英語では普通に greater/greater than と言うはずです。

D 問題

主に 2 分探索の問題です。 2 分探索の説明は FORCIA 社の記事 が一番分かりやすかったと思います。『めぐる式 2 分探索』なので元ネタにちなんで ok, ng が出てきますが、 yes/no の方が適切かと思います。この辺りも自由に決めて良いのが競プロ!

E 問題

ひと目見て最大流の問題だと思ったのですが、違いました。重さが 2 次元のナップサック問題と見て IntMap で枝刈りしてみましたが、 WA が取れず失敗しました。

公式解説は Kpapsack 2 でした。ガーン……

F 問題

遅延セグメント木の解法を考えていました。区間を set で管理するテクニックでも解けるらしいです? Upsolve します。

この問題は Library Chercker の問題案にあったらしいです。いずれテストケース生成係もやりたいですね……。

Splay tree メモ

Link/cut tree の前準備で splay tree を (まだ) 作っています。前提知識が見えて来たのでメモします。

[1] 2 種類の API

Indexed API (列としての API)

Data.Map.Strict の Indexed API (elemAt, deleteAt) がこのカテゴリに相当します。 split/merge のような splay tree 特有の API もあります。

maspy さんの splay tree は、値の列を管理するためのデータ型として実装されています。

Ord k ベースの API (平衡木としての API)

Data.Map.Strict の主な API (insert/delete や 2 分探索) がこのカテゴリに相当します。が、競プロでは必要の無い機能だったかもしれません。

Tarjan 氏の論文では平衡二分木の実装として splay tree が紹介されていますから、こちらの機能がフィーチャーされています。

[2] 2 種類の splay 実装

Bottom-up splaying

maspy さんの splay tree は bottom-up splaying を使って実装されています。たぶん。特に集約 (畳み込み) の計算は bottom-up 実装でなければ難しそうです (後述) 。

Top-down splaying

Tarjan 氏の論文では top-down splaying が速くて良いぞとなっています (そうかな?) 。 Top-down splaying でサイズを求める実装も見つかりましたが、 bottom-up 実装と比べてそこまで優位なのかは疑問です。

[3] 集約 (畳み込み) ・作用

ノードに部分木のサイズや畳み込みを持たせます。区間反転用のフラグを載せてあれこれする場合もあるようです。

以上

Splay tree は作り直しになりそうです。 Link/cut tree の情報も集めないとー

Misc

この頃は問題も解かずゴロゴロしています。

maspy さんの遅延伝播セグメント木の定数倍高速化

遅延セグ木の実装を PAST 上級本から maspy さん準拠に変更しました。

枝刈り

maspy さんのブログ記事 を読むと、 (1) 上から伝播 と (3) 上側を計算し直し において葉まで降りない実装になっていることが分かります。真似してみると、作用が重いときは若干高速になりました。作用が軽いときは PAST 上級本のように葉まで降りたほうが速かったです。やらなくても良かったかも。

作用が長さを引数に取る

区間の長さをモノイドに載せるより、セグメント木の畳み込み関数側から与えた方が速くなるようです (1.5 倍ほど? 未実装) 。真似して SemigroupActionWithLength みたいな型クラスを作るかもしれません。

繰り返し 2 乗法の再整理

stimes は繰り返し 2 乗法の効率的な実装ですが、正確評価をしないため遅いです。コピペで正格評価版を作りました。

-- | Strict, much faster `stimes`.
{-# INLINE stimes' #-}
stimes' :: (Semigroup a) => Int -> a -> a
stimes' n0 x0
  | n0 <= 0 = errorWithoutStackTrace "stimes: positive multiplier expected"
  | otherwise = mulTimes n0 (<>) x0

-- | Strict, much faster `mtimes`.
{-# INLINE mtimes' #-}
mtimes' :: (Monoid a) => Int -> a -> a
mtimes' n0 x0 = case compare n0 0 of
  LT -> errorWithoutStackTrace "mtimes: zero or positive multiplier expected"
  EQ -> mempty
  GT -> mulTimes n0 (<>) x0

-- | Multiplies @x@ by @n@ (N > 0) times using the binary lifting technique.
{-# INLINE mulTimes #-}
mulTimes :: Int -> (a -> a -> a) -> a -> a
mulTimes n0 op x0
  | n0 <= 0 = errorWithoutStackTrace "mulTimes: positive multiplier expected"
  | otherwise = f x0 n0
  where
    f !x !n
      | even n = f (x `op` x) (n .>>. 1)
      | n == 1 = x
      | otherwise = g (x `op` x) (n .>>. 1) x
    g !x !n !z
      | even n = g (x `op` x) (n .>>. 1) z
      | n == 1 = x `op` z
      | otherwise = g (x `op` x) (n .>>. 1) (x `op` z)

powMod 関係も整理がついて良かったです。

nextPermutation

gksato さんの nextPermutation がマージ間近です。マージカル! INLINE 化、アルゴリズムの改善、 prevPermutation の追加など、贅沢な内容です。

自ライブラリの Compat モジュールにコピーしました。