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

ABC 373, Fenwick Tree, ACL 移植開始

ABC 373

ABC 373 に参加しました。

問題A 問題B 問題C 問題D 問題E 問題F 問題
提出ACACACAC-AC
予想 Diff40200101,0001,8001,600
実際 Diff1154757651,5922,018
Table 1: Diff 予想

A 問題

文字列の列 {si}i(i≥1)\{s_i\}_i (i \ge 1) に対し length si=i\mathrm{length}\ s_i = i である ii の数を求めよ。リスト内包表記で文字数を節約します。

main=interact$show.f.lines;f x=sum[1|(i,s)<-zip [1..]x,i==length s]

B 問題

A, B, .., Z の順列が与えられたとき、 (A, B) 間、 (B, C) 間、 .., (Y, Z) 間の距離の和を求めよ。 vector 芸でサクっと解けて楽しい問題でした。

solve :: StateT BS.ByteString IO ()
solve = do
  !s <- U.fromList . map (subtract (ord 'A') . ord) . BS.unpack <$> line' -- #1
  let !is = U.update (U.replicate 26 (-1 :: Int)) $ U.imap (flip (,)) s -- #2
  let !ds = U.zipWith ((abs.) . (-)) is (U.tail is) -- #1 -- #(ref:3)
  printBSB $ U.sum ds

C 問題

2 つの数列それぞれの最大値の和を求めよ。 maximum のエイリアスを作って文字数を節約しました。

main=interact$show.f.map read.words;f(n:x)=m(take n x)+m(drop n x);m=maximum
Listing 1: 1,852 ms

D 問題

頂点間の距離の制約が与えられた時、制約を満たす重みの割り当てを 1 つ求めよ。 WA 後、解法を思いつかず重み付き Union-Find に手を出してしまいました。

      4
      ^
      |
1 --> 2 --> 3
      ^
0-----|
Listing 2: 末端の頂点が複数あり、単純なトポロジカルソートでは解けない

より正統的な解法としては、辺 (u, v, w) に対して辺 (v, u, -w) を加え、連結成分の重みを DFS で一挙に確定します。順序付きグラフだと思い込むと出てこない発想でした。難しくないですか……?

solve :: StateT BS.ByteString IO ()
solve = do
  (!n, !m) <- ints2'
  !uvws <- U.replicateM m ints110'
  let !gr = buildWSG n $ (uvws U.++) $ U.map (\(!u, !v, !dw) -> (v, u, -dw)) uvws

  printVec $ U.create $ do
    res <- UM.replicate n (0 :: Int)
    done <- UM.replicate n False
    forM_ [0 .. n - 1] $ \u0 -> do
      flip fix u0 $ \dfs u -> do
        unlessM (GM.exchange done u True) $ do
          w0 <- GM.read res u
          U.forM_ (gr `adjW` u) $ \(!v, !dw) -> do
            GM.write res v $! w0 + dw
            dfs v
    return res

ちなみに重み付き Union-Find は DFS と同速でした。償却 O(α)O(\alpha), の衝撃の実力!

E 問題

数列 {Ai}i\{A_i\}_i に KK を分配するとき、 ii 毎に上位 MM に入りが確定するための最小の割り当てを求めよ (同率でも良い) 。未だに解けていません。

畳み込みできる Map があれば、挿入・削除で楽できるのかなと思いました。 おこていゆさんの得意技 です。

F 問題

EDPC の Tower を見に行って、近くの問題を見返すと Z - Frog が類題だと思いました。つまり CHT! CHT の式整理を真似ると 2 乗が消えませんでした。ところが {i2}i\{i^2\}_i は {0,1,4,9,16,..}\{0, 1, 4, 9, 16, ..\} という形ですから、 {(i+1)2−i2}i\{(i+1)^2 - i^2\}_i は {1,3,5,7,..}\{1, 3, 5, 7, ..\} の等差数列になります。よって 1 ステップ手前を振り返るだけの単純な DP になります。

dp[i]\mathrm{dp}[i] を (重さ → 最大価値) の配列とします。 dp[i]\mathrm{dp}[i] と合わせて set[i]\mathrm{set}[i] にて各品物の使用数を記録して AC しました。しかし よくよく 考えると 嘘解法 だった気がします。 dp[i]\mathrm{dp}[i] の候補が複数あるとき、どの品物の使い方が将来的に最適であるか分からないためです。

嘘解法が無ければ緑パフォでした。残念。

G 問題

evima さんの解説 を見ると最小費用流で解けそうで ジ・エンド です。ジ・エンド!

Fenwick Tree

Fenwick Tree (Binary Index Tree; BIT) は群の区間和が O(log⁡N)O(\log N) で求めるデータ構造です。セグメント木よりも定数倍が良く、盆栽コンテンツとして重要です。

まだ理解しておらず、詳細は Wikipedia の通りとします。図を見れば確かにそうなんですが、 LSB を使った動きがマジック……!

操作

Haskell

Unbox vector に boxed なデータ型を保存する

Unboxed vector における Vector とはデータ族 (≒ 関連型) であり、効率の良い配列型を返します。 Boxed 化された配列型を返しても問題は無く、 newtype Boxed a により boxed vector を割り当てられることにします。なるほど……!

https://github.com/haskell/vector/issues/503

たとえば cojna さんの Data.Buffer にリッチなコレクションを入れることができるようになるはずです。 未検証ですが Boxed 型を導入しました 。

ac-library を Haskell に移植します

ac-library の移植を始めました: toyboot4e/ac-library-hs 。ワシが作ったと言いたいだけです。放っておいても完成しますが、完成後にさっと目を通してもらえると大変助かります。

iota 速すぎ問題

自分で ACL を移植するよりも、 cojna/iota の縮小版を ACL とした方が高速なライブラリができます。実際、 cojna/iota はしばしば ACL よりも高速です。 ACL としてはレギュレーション違反と言えなくもないですね (?) 。

意図

このように欲を出すと際限が無く、合意できる線を探るのも困難です。そこで ac-library の写経をベースラインにしようと思います。

Misc