ABC 368

ABC 368 に参加しました。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
予想 10 200 1,100 1,000 1,400 1,600
実際 20 56 368 816 2,140 1,180

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

C 問題

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

D 問題

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

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

fix $ \loop -> do
  whenJustM (deleteBH heap) $ \x -> do
    {- ~~ -}

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.png

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

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

verify

余談

SWAG (sliding window aggregation)

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

Stack ベースの SWAG

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

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

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

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

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

Deque ベースの swag

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

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

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

verify

セグ木で \(O(N \log N)\) で良くない？

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

Misc