ABC 352

ABC 352 に参加しました。

A 問題

比較演算子の練習問題です。

main=interact$(\[_,b,c,d]->if min b c<=d&&d<=max b c then"Yes"else"No").map (read @Int).words

cojna さんの提出 を読むと、 if then else よりもガードを使った方が短くなるようです。

B 問題

2 つのイレテータをマッチさせていくような問題です。 Haskell においてはパターンマッチを使うのが簡単です。

main=(f 1<$>getLine<*>getLine)>>=putStr.unwords.map show
f i[]_ = [];f i(x:a)(y:b)|x==y=i:f(i+1)a b|True=f(i+1)(x:a)b

cojna さんの提出 では再帰関数ならぬ再帰演算子 % が定義されており面白いです。 shows で unwords.map show を手動実装しているのもゴルフ界の重要な典型に違いありません。

ghci> (show 13 ++) "abc"
"13abc"
ghci> shows 13 "abc"
"13abc"

C 問題

設定が面白い問題でした。モハラン先生の新作が生まれました。

C - Standing On The Shoulders pic.twitter.com/BFgDlxPgmy

— モハラン (@programsamisii) May 4, 2024 
main=interact$show.((+)<$>sum.map snd.filter(even.fst).zip[0..]<*>f).tail.map read.words
f[]=0
f(x:y:r)=max(y-x)(f r)

cojna さんの提出 ではリスト内包表記を使ってコードが短縮されていました。強い……！

D 問題

値 → 添字のマップ (配列) is を作ります。

is <- U.update (U.replicate n (-1 :: Int)) . U.imap (flip (,)) . U.map pred <$> intsU'

IntSet を状態として is を幅 k の窓で見る尺取法を実施すれば良く、以下の形で解けました。

U.foldl' step s0 $ U.zip (U.drop k is) is
  where
    s0 = {- .. -}
    step acc (!push, !pop) = {- .. -}

E 問題

辺の数が異常に多いですが、最小全域木を作る問題なので Kruskal 法を実施するだけでした。

F 問題

ポテンシャル付き Union-Find 木を使って楽をしつつ、全探索解を提出しました。

集合 DP らしいですがピンと来ていません。 Upsolve するぞ〜

HL 分解 (heavy-light decomposition)

HLD を習得しました。 HLD の機能は、ダブリングによる LCA の上位互換だったと思います。更新に強く、非可換なモノイドも任意の経路に沿って畳み込みできます。

以下は HLD のお気持ち解説です。かえって混乱する危険もありますが、悪しからず……

LCA (ダブリング) の復習

木に対して (親頂点, モノイド) のペアをダブリングすると、 LCA および可換モノイドの畳み込みが \(O(\log N)\) 程度で計算できるのでした (メモ) 。

注: 僕の実装は \(O(\log^2 N)\) でした。 \(O(\log N)\) 実装はどうやるんでしょう……

HLD の学習資料

HLD の概要を掴むため、以下の資料を参照しました。難航しました。

詳細は cojna/iota の HLD および maspy さんの提出 を写経して理解しました。

HLD の概要

HLD の出力を以下とします。フィールド毎に解説します。

data HLD = HLD
  { -- | `Vertex` -> Parent `Vertex`.
    parentHLD :: !(U.Vector Vertex),
    -- | `Vertex` -> Reindexed vertex (`VertexHLD`).
    indexHLD :: !(U.Vector VertexHLD),
    -- | `Vertex` -> The line's head `Vertex`.
    headHLD :: !(U.Vector Vertex)
  }
  deriving (Show, Eq)

元の木

木にはランダムな頂点番号が割り振られているものとします。

  0--8--7--3--1--2--12--13--15--14     XX: Vertex
     |        |                         --: 辺
 10--5        11--8--6                   |: 頂点
     |
     4

indexHLD: Vertex -> VertexHLD

indexHLD は頂点番号の再割当てです。木を列に分けた時、同じ列にある頂点の番号が連続するように再割当てを行います。

 0==1==2==3==4==5==6==7==8==9     XX: VertexHLD
    |        |                     ==: 同じ列にある辺
14==13       10==11==12            |: 他の列を繋ぐ辺
    |
    15

Vertex と VertexHLD は注意深く区別する必要があります。 newtype を作った方が良かった かもしれません。

なお長い列を貪欲に作ると、列の数は十分小さくなるようです (\(\log N\) 程度？) 。

headHLD: Vertex -> Vertex

headHLD は、各列の頂点を列の『頭』に写します。

 0==0==0==0==0==0==0==0==0==0    XX: Vertex (VertexHLD ではない)
    |     |
 5==5     11==11==11
    |
    4

parentHLD: Vertex -> Vertex

parentHLD は頂点を親頂点に写します。

 (-1)==0==8==7==3==1==2==12==13==15   XX: Vertex (VertexHLD ではない)
       |        |
    5==8        1==11=8
       |
       5

LCA の求め方 (\(O(N \log N)\))

lca(u, v) を求めるには、 2 頂点 (u, v) を徐々に上へ引き上げて行きます。

let lca = do
  let 引き上げ操作 = do
    `headHLD` を使って列の頭まで移動する
    `parentHLD` を使って列の頭から親の列へ移動する
  let loop u v
    | headOf u == headOf v = indexHLD の小さいほうが LCA
    | otherwise = do
      indexHLD の大きい方に対して引き上げ操作
      loop u' v'
  loop

セグメント木によるモノイドの畳み込み (\(O(N \log^2 N)\))

1 本のセグメント木にすべての頂点 (VertexHLD) が収まります。 LCA と同様の計算過程で各列の (indexHLD U.! u, indexHLD U.! headOf u) を残せば、セグメント木の上で畳み込みできます。

可換モノイドを畳み込むためには、下から上 (u -> lca(u, v)) と上から下 (lca(u, v) -> v) の双方向の畳み込みが必要です。そのため Dual a を載せたセグメント木を併用します。この辺りは maspy さんの TreeMonoid を写経しました。

verify

toy-lib に verify 用のディレクトリ を追加しました。ここで verification-helper によるシステムテストを実施しています。

感想

HLD は木の基本機能と言って良いほど馴染みがあって強力でした。良いカードを手に入れました。

HLD は 高度典型 (高 diff 典型) とされるデータ構造ですが、最大流や遅延セグメント木に比べれば簡単でした。改めて、遅延セグ木が緑 diff だったのが異常だったと思います。

HLD を実装したことで、高度典型も基本装備に過ぎないことが察せられました。 CHT や FFT, Suffix Array なども習得しようと思います。

フーリエ変換が内積なのはよく分かりましたが、バタフライ演算が分からなくて……。

Misc

ライブラリ (CLI) の強化

ライブラリ更新機能

Main.hs に埋め込まれたライブラリ (Main.hs の 15 行目) を、現在の toy-lib のソース内容で上書きします:

$ toy-lib -u d/Main.hs | tee d/Main.hs

依存モジュール読み込み機能

指定範囲内のモジュール (および依存モジュール) をソースファイルに埋め込みます:

$ cat Example.hs
-- 提出前に埋め込みに変える
-- {{{ toy-lib import
import Math.Manhattan
-- }}} toy-lib import

main = putStrLn "Hallo"

$ toy-lib -e Examle.hs
-- 提出前に埋め込みに変える
rot45 :: (Int, Int) -> (Int, Int);rot45 (!x, !y) = (x - y, x + y)

main = putStrLn "Hallo"

特に oj-verify 用のソースは toy-lib を import して使っているので、これを AtCoder に提出する際は toy-lib -e にかけてライブラリを埋め込みます。

提出用ソースに verify 用のコメントを追加

oj-verify 用のコメントをテンプレートに追加しました。 Dropbox にテストケースが追加された後は、 oj-verify run の対象にできます。

-- verification-helper: PROBLEM https://atcoder.jp/contests/abc294/tasks/abc294_g
main :: IO ()
main = do {- .. -}

問題文を開きやすくなるし、入れるメリットは一応あるはず……？

Youtube

宮崎雄也と音楽の話 がめちゃめちゃ面白い。全部観ました。

アークナイツ

インテリオタクたちの激推しコンテンツです。未プレイのため、 Gaming on an Android VM on Linux を参考に Android のエミュレータを作成……したい