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

ABC 368, Splay tree (2), SWAG

ABC 368

ABC 368 に参加しました。

問題A 問題B 問題C 問題D 問題E 問題F 問題
予想102001,1001,0001,4001,600
実際20563688162,1401,180
Table 1: Diff 予想

oj が動かない……?

確認中です。

エラーログ
abc368/contest.acc.json created.
create project of Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)
node:events:497
      throw er; // Unhandled 'error' event
      ^

Error: spawn /nix/store/q8gf4f7373l92a5sd472mbxqci1d1v20-python3.11-online-judge-tools-12.0.0/bin/oj ENOENT
    at ChildProcess._handle.onexit (node:internal/child_process:286:19)
    at onErrorNT (node:internal/child_process:484:16)
    at process.processTicksAndRejections (node:internal/process/task_queues:82:21)
Emitted 'error' event on ChildProcess instance at:
    at ChildProcess._handle.onexit (node:internal/child_process:292:12)
    at onErrorNT (node:internal/child_process:484:16)
    at process.processTicksAndRejections (node:internal/process/task_queues:82:21) {
  errno: -2,
  code: 'ENOENT',
  syscall: 'spawn /nix/store/q8gf4f7373l92a5sd472mbxqci1d1v20-python3.11-online-judge-tools-12.0.0/bin/oj',
  path: '/nix/store/q8gf4f7373l92a5sd472mbxqci1d1v20-python3.11-online-judge-tools-12.0.0/bin/oj',
  spawnargs: [
    'dl',
    'https://atcoder.jp/contests/abc368/tasks/abc368_a',
    '-d',
    'test-cases'
  ]
}

Node.js v20.15.1

A 問題

リストを splitAt (n - k) して入れ替えます。

main=interact$unwords.f.words;f(n:k:x)=(++).snd<*>fst$splitAt(read n-read k)x

B 問題

Mutable にシミュレーションで解きました。序盤からオセロットですが、オセロットしたくて Haskell を使っていることもあり、苦渋の決断を踏み切りました。

res <- (`execStateT` (0 :: Int)) $ fix $ \loop -> do
  -- 操作完了まで繰り返し
  unlessM isDone $ do
    run
    modify' succ
    loop
Listing 1: リロードタイムがこんなにも戦場に息吹を!

C 問題

40 分苦戦しました。素直にループを書きましょう……!

D 問題

次数 1 の頂点を消して行きます。 cojna さんの Binary Heap をお借りしました。

コードはぐちゃぐちゃになりましたが、手グセを持っていて助かりました。やはり手続き型プログラミングが楽ですね……。

fix $ \loop -> do
  whenJustM (deleteBH heap) $ \x -> do
    {- ~~ -}
Listing 2: ヒープが空になるまでループする

E 問題

hogeeee

F 問題

hogeeee

Splay tree (2)

Splay tree とは何者なのか

No: SplayMap

以前 は map としての splay tree を作りました。しかし top-down splaying で集約の計算ができず、単なるマップになったのでした。欲しいやつじゃなかった……!

Yes: SplaySeq (遅延伝播反転可能 splay tree)

今回は列 (sequence) としての splay tree を作りました。 maspy さんの splaytree.hpp を写経します。列を木にすると、親が子の集約 (畳み込み) を持つことができます:

2024-08-25-sequence.webp

セグメント木との主な違いとしては、要素の挿入・削除ができ、区間反転ができます。出ないと思いますが、部分木の入れ替えなども可能です。

区間反転は左右の子を貪欲に swap して実装できます。また可換モノイドの畳み込みは反転の影響を受けないため、反転の反映は遅延させます。

verify

余談

SWAG (sliding window aggregation)

SWAG は簡単かつマイナ過ぎて解説が少ない気がします。

Stack ベースの SWAG

尺取り方でモノイドの畳み込みを償却 O(1)O(1) で求めるためのデータ構造 (?) です。群ではなく、逆操作が存在しない点がポイントです。双対右スキャンで壁を作って pop に備えます。

       配列  [1]-[2]-[3]-[4]-[5]-[6]-[7]-[8]-..
        窓  [---------------------]
     バッファ                  [5]-[6]
バッファの畳み込み                  *******
  双対右スキャン  <--------------

双対右スキャンとは、右から作る左畳み込み (scanr' (flip (<>)) mempty) です。造語だったらすみません。

この図において各操作の内容は、

※ popFront で双対右スキャンが空になったとき、バッファ中の値を双対右スキャンへ移動します。よって償却 O(1)O(1) です。

Deque ベースの swag

push/pop を左右から操作可能にします。これは左右方向にスタックとスキャンを持てば良いです。

     右窓                ------------->
  左スキャン                ------------->
     左窓  <-----------
双対右スキャン  <-----------

もう pop できない時は、要素を左右均等に振り分けてバランスをとります。これで償却 O(1)O(1) になるみたいです。未証明……

verify

セグ木で O(Nlog⁡N)O(N \log N) で良くない?

セグ木で十分だと思いました。競プロ小説を書くなら主人公は SegTree です。

Misc