ABC 374, PrimArray

ABC 374

ABC 374 に参加しました。

Table 1: Diff 予想
問題	A 問題	B 問題	C 問題	D 問題	E 問題	F 問題
提出	AC	AC	AC	AC	AC	-
予想 diff	10	100	400	800	1,000	1,600
実際 diff	11	28	226	694	1,504	2,026

A 問題

文字列が san で終わるなら Yes, そうでなければ No を印字せよ。改行文字に注意して答えます。

main=interact$y.take 4.reverse;y"\nnas"="Yes";y _="No"

B 問題

文字列 s, t が等しいならば 0 を、異なるならば最初に不一致となる位置を答えよ。

cojna さんの提出を見てみましょう。短過ぎです。

main=interact$show.f.lines
f[s,t]=sum[s%t|s/=t] -- 1
(x:s)%(y:t)|x==y=1+s%t -- 2
_%_=1 -- 3

1 s と t が一致する場合を sum とガードで暗に処理しています。
2 再帰演算子で文字数を節約しています。
3 エッジケースの処理も万全！

C 問題

整数列 \(\{K_i\}_i\) を 2 つのグループに分けたとき、グループ毎の和の差を最小化せよ。慣れると反射で書ける問題ですね。

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !xs <- intsU'

  let !s = U.sum xs
  let candidates = U.generate (bit n) id -- 1
  let eval bits =
        let is = U.findIndices (testBit bits) $ U.generate n id -- 2
            sum1 = U.sum $ U.backpermute xs is -- 3
            sum2 = s - sum1
         in max sum1 sum2

  printBSB . U.minimum $ U.map eval candidates

1 Bit 全探索
2 testBit x iBit == (x .&. bit iBit) /= 0 == (x .&. (1 .>>. iBit)) /= 0
(Data.Bits)
3 U.backpermute xs is == U.map (xs U.!) is

D 問題

順列と bit mask を全探索せよ。最近ほぼ同じ問題が最近出た覚えが？　順列を固定した上で、 bit mask の適用は DP にするとさらに良しです。

dist :: Int -> Int -> Int -> Int -> Double
dist !x1 !y1 !x2 !y2 = sqrt . intToDouble $ (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)

solveDP :: [(Int, Int, Int, Int)] -> Double
solveDP = inner 0.0 0 0
  where
    inner :: Double -> Int -> Int -> [(Int, Int, Int, Int)] -> Double
    inner !acc !_ !_ [] = acc
    inner !acc !x1 !y1 ((!x2, !y2, !x3, !y3) : rest) =
      let !cand1 = inner (acc + dist x1 y1 x2 y2) x3 y3 rest
          !cand2 = inner (acc + dist x1 y1 x3 y3) x2 y2 rest
       in min cand1 cand2 -- 2

solve :: StateT BS.ByteString IO ()
solve = do
  (!n, !speedM, !speedL) <- ints3'
  !lines <- U.replicateM n ints4'

  let lengthL = U.sum $ U.map (\(!x1, !y1, !x2, !y2) -> dist x1 y1 x2 y2) lines
  let lengthM = minimum . G.map (solveDP . U.toList) $ lexPerms lines -- 1
  printBSB $ lengthM / intToDouble speedM + lengthL / intToDouble speedL -- 3

intToDouble
1 lexPerms で順列全探索
2 辺の向きを両方試して DP します
3 移動 (M) 距離とレーザー (L) の距離に分けて考えます

E 問題

工程のボトルネックを最大化する機械の購入方法を答えよ。反射で答えると、判定問題で 2 分探索ができそうです。

判定問題では \(ax + by \ge w\) の下で \(px + qy\) を最大化します。基本的に効率の良い機械を購入すれば良いのですが、実は \(w \bmod \mathrm{lcm}(a, b)\) 部分の最適解が分かりません。ここで \(a, b \le 100\) より余りの部分は全探索できます。

ヤケクソで探索範囲を広げたら通りました。運です。

F 問題

DP です。 \(O(M^2 \log M) (M = 10^4)\) 解法は思いつくつもりなのですが……。考えます。

Note

最近は満足の行く実装が書けるようになり、以前ほど人の提出を読まなくなりました。良いのか悪いのか……。 Common Lisp, Fortran, OCaml あたりも読んでみたいですが、手つかずのままです。

Haskell

Data.Primitive.PrimArray はあまり使わない

Mutable なデータを IORef に入れると (2 重に) box 化されて重くなります。 Library Checker の問題で 200 - 300 ms 程度影響が出る程度には遅く、絶対に避けたいレベルです。

代わりに unboxed な MVector にデータを入れることが多いのですが、 PrimArray の方が速い可能性が出てきました。

先日「可変な変数を使うのにIORefを使うか1要素Vectorを使うか」みたいな話があったけど、Data.Primitive.PrimArrayにあるMutablePrimArrayの方が2ワードほどメモリ使用量が少ないので良いのかもしれない（検出できる違いは出ないと思うけど）
— mod_poppo (@mod_poppo) April 25, 2019

中身は ByteArray で違いがなさそうなんだけど、Primitive Vector は offset と length の情報を持っている分のメモリのオーバーヘッドあるいはslicing の安価さというのはありそう
— スマートコン (@mr_konn) July 23, 2020

検証

雑な検証になりますが、 Library Checker の Splay Tree の問題 (Dynamic Sequence Range Affine Range Sum) で比較しました。コード差分。

誤差レベルで遅くなりました (!?) 。リジャッジすれば結果はひっくり返るかも。

なお MVector 版で使用していた unsafeModifyM の実装を見てみると、 stToPrim により型パラメータ m を ST に確定させ最適化しています。とりあえず使う分には MVector の方が無難かもしれません。

ACL 移植メモ

Disjoint Set Union (Union-Find Tree)

サクっと移植できました。先行きの良いスタートです。

Fenwick Tree (Binary Index Tree)

添字の動きに戸惑いながら移植しました。群の区間和が取れて定数倍が良いです。

Floor sum

何も分からない。離散化すると周期性が出てくる覚えはあります。完全な写経です。

Max flow

可変長配列

可変長配列 (std::vector) に依存しています。 VUM.MVector をラップして可変長配列を実装しました。しかし MVector を MutVar の中に入れるため効率は落ちます。

Break

ループの break のため、ループを再帰関数で表現しました。 break しなくて済む場合でも、なるべく忠実に実装したいと思います。

イテレーションと destructuring

タプルの unboxed vector は SoA (struct of arrays) なので、走査しない配列はスキップした方が速そうな気がしています。速度の比較はしていません。

(VUM.MV_3 _ vecTo _ vecCap) <- mutableVector
neighbors <- VU.zip <$> VU.unsafeFreeze vecTo <*> VU.unsafeFreeze vecCap
VU.forM_ neighbors $ \(!to, !cap) -> do
  -- ~~