ABC 373, Fenwick Tree, ACL 移植開始

ABC 373

ABC 373 に参加しました。

Table 1: Diff 予想
問題	A 問題	B 問題	C 問題	D 問題	E 問題	F 問題
提出	AC	AC	AC	AC	-	AC
予想 Diff	40	200	10	1,000	1,800	1,600
実際 Diff	11	54	75	765	1,592	2,018

A 問題

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

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) -- #(ref:1) -- # 3
  printBSB $ U.sum ds

1 ord 関数を活かして英大文字を 0, 1, .. に写します。これは (位置 → アルファベット) の数列になっています。
2 逆に (アルファベット → 位置) の配列を作ります。
3 この配列の隣接二項間の差の絶対値の和が答えです。

C 問題

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

Listing 1: 1,852 ms

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

D 問題

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

Listing 2: 末端の頂点が複数あり、単純なトポロジカルソートでは解けない

      4
      ^
      |
1 --> 2 --> 3
      ^
0-----|

より正統的な解法としては、辺 (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(\alpha)\), の衝撃の実力！

E 問題

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

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

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

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

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

G 問題

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

Fenwick Tree

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

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

Fenwick Tree の頂点数は \(N\) です。
\(i\) 番目の頂点は \([i - \mathrm{lsb}(i), i)\) の区間和を持ちます。

操作

1 点加算 (add)
頂点 \(i\) から頂点 \(i + \mathrm{lsb}(i)\) への移動を続けると上手く状態更新できます。
\([1, i)\) の区間和の取得 (prefixSum)
頂点 \(i\) から親頂点 \(i - \mathrm{lsb}(i)\) への移動を繰り返して \([1, i)\) の区間和 (prefix sum) を取得できます。
区間取得 (sum)
prefixSum の差により求めます。