ABC 342, Rolling Hash

ABC 342

ABC 342 に参加しました。 3 完 (A, B, D) でした。

A 問題

1 問目から強敵が来ました。ワシはアプリカティブ・スタイルが大好きじゃ。

main :: IO ()
main = do
  !s <- BS.getLine
  let !cns = map ((,) <$> head <*> length) . group $ sort (BS.unpack s)
  let !c = fst . fromJust $ find ((== 1) . snd) cns
  print . succ . fromJust $ findIndex (== c) (BS.unpack s)

どんな方法でも良いので、淀み無く解けることが大事だと感じました。

B 問題

都度 elemIndex を走らせる \(O(NQ)\) の解法が簡潔で良いと思います。

マップ (人 x \(\mapsto\) その人の位置 i_x) を作れば \(O(N)\) で解答できます。

-- 密なマップは配列で実現します
let !is = U.accumulate (const id) (U.replicate (n + 1) (-1)) $ U.imap (flip (,)) xs

C 問題

置換関数を構築する方法

毎回すべての文字を置換すると、計算量は \(O(QN)\) です。ここで文字の置換を \(f_i\) として、 \(f_q (f_{q - 1} (.. (f_1 \mathit{xs}) .. ))\) の計算を \((f_q \circ f_{q - 1} \circ .. \circ f_1) \mathit{xs}\) に置き換えると、 \(O(Q f)\) で計算できます。賢い。

Union-Find を使った解法

それぞれの文字をバケットに見立てます。文字の書き換えとは、バケットの中身を別のバケットに移すことだと考えると、 Union-Find を使うことができます。

できません。 Union-Find を使う場合は、破棄した文字に対応する新しい頂点を都度追加し、過去の頂点を引きずらないよう工夫する必要があります。ほげえええええええ

3
abc
2
a x
a z

xbc

D 問題

これは面白かったです。 \(\{A_{n}\}_{n}\) の走査は一度で済ませたいところですが、 \(A_j\) と掛け合わせて平方数となる \(A_i\) の取り寄せを高速化する必要があります。実はこれを 1 点に集約できるスロットの持ち方があって、それは \(2^3 \cdot 3 \cdot 5^2\) に対する \(2 \cdot 3\) のような数です。

言語化が辛いのでコードで:

feat :: Int -> Int
feat = foldl' (*) (1 :: Int) . mapMaybe f . primeFactors
  where
    f (!p, !n)
      | n `mod` 2 == 0 = Nothing
      | otherwise = Just p

また \(0 = 0^2\) の処理は頑張ります。

E 問題

終点からの Dijkstra 的なアレです。最も遅い時間を求めるため Max ヒープを使います。

競技プログラミング

meooow25/haccepted

meooow25/haccepted (API ドキュメント) を見逃していました。 Array 派 Haskeller や Codeforces 勢は垂涎かも知れません。

• Dijkstra
  さらっとヒープ (木) を自作しています。
  
• RerootFold
  全方位木 DP です。良い命名ですね。
  

位取り法

• 辞書順比較のために文字列を整数に単射する際は、無を 0 番、 'a' を 1 番とします。
  

Rolling Hash

ABC 331 - F で rolling hash をセグメント木に載せる問題が出ました。セグメント木に乗るデータ型と言えばモノイドですが、鉄則本の rolling hash はヘビー級コンテナの印象でした。

\(\{B^{n}\}_n\) の事前計算は不要なのか問題を解決すべく、我々は cojna/iota の Data.RollingHash に向かいます……。

群としての rolling hash

鉄則本では累積和を使って rolling hash を実装しました。累積和とは、結合と分解のできるデータ型、つまり群の列が与えられた際に、 \(O(N)\) の前処理によって任意の \([l, r]\) 区間データの結合が \(O(\mathit{recip \cdot \diamond})\) で得られるアルゴリズムです。

群とは逆元が定義されたモノイドです。狭義の累積和では csum[r] - csum[l] を計算しますが、一般的には \(L^{-1} \diamond (L \diamond R)\) のような群に対する計算だと捉えられます。

Rolling hash においては \(L^{-1} \diamond (L \diamond R)\) の計算に \(B^{-n} \bmod p\) が現れ、非常に大きな定数時間の計算が要求されます。したがって \(\{B^{n}\}_{n}\) を事前計算し、 \(B^{-n_1} B^{n_2} = B^{n_2 - n_1}\) として逆元の計算を打ち消すことで、 \(O(1)\) でハッシュ値を計算可能にします。

モノイドとしての rolling hash

モノイドとしての rolling hash は \((B^{n}, \mathit{hash})\) です。これがすべて、超簡単！

\[ \begin{aligned} \mathrm{mempty} &:= (B^{1}, 0) \\ (B^{n_1}, \mathit{hash}_1) \diamond (B^{n_2}, \mathit{hash}_2) &:= (B^{n_1 + n_2}, B^{n_2} \mathit{hash}_1 + \mathit{hash}_2) \end{aligned} \\ \]

セグメント木を使って rolling hash を実装する場合、結合の逆操作は必要ありません。 \(\{B_{n}\}_{n}\) を持たなくて良くなったため、理解も実装もシンプルになりました。しかもセグメント木は 1 点更新ができます。唯一、計算量は \(O(N \log N)\) となりますが、そこを突く問題は AtCoder では出ません。

回文の判定では逆方向のハッシュ値を計算するため、セグメント木が 2 本必要です。逆方向の <> の計算には flip (<>) を使えば良く、それは Dual モノイド なんだって cojna さんのコードが言っていました。

cojna/iota の高速化ネタ

MagicHash と natVal'

KnownNat からの値の取得を natVal から natVal' に変えると少し速くなりました。

+{-# LANGUAGE MagicHash #-}
-import Data.Proxy
+import GHC.Exts
import GHC.TypeLits

-fromInteger (natVal (Proxy @p))
+fromInteger (natVal' (proxy# @p))

Unbox の実装を SoA から AoS に

2 要素のタプルは 2 本の unboxed vector に格納されますが、 2 要素の配列は 1 本の unboxed vector に詰めてしまえばいいじゃない！　それが Affine の Unbox の実装です。

効果は……ほぼありません。ただ Mat3x3 に至っては primitive パッケージの ByteArray にすべての要素を詰め込んでいますから、流石に効くのではないかと思います。

Misc

人

Codeforces 時代

少し調べてみました。

tanakh 氏

エディタ拡張となっていた tanakh 氏 を発見。 Emacs にポートした 。オーバー。

DT

Distro Tube から書籍 The Super Wheel Options Strategy が出ました (ポチッ) 。一時は xmonad, Evil Emacs, exwm などで夢中になったチャンネルです。 新しいチャンネル も観る、かも

キーボード

MiniAxe が届きました。 36 キーで組み立てが楽しみです。今後はさらなる操作性の拡張を目指したいです。

Steno キーボード

Stenography は複数キーの同時押しを活かした文字入力の方式です。キー数は 30 を切る程度。近年は Open Steno Project や StenoKeyboards が活躍しており、誰でも 2 万円以下で気軽に挑戦できます。

• Symbols and Shortcuts With Steno! Emily's Symbols And Modifiers
  数値キーとして 8, 4, 2, 1 を用意します。たとえば 5 は 1 と 4 の同時押しです。天才……！
  
• emily-symbols
  Steno キーボードにおけるキーマップ例と図解が載っています。魔境です。
  
• emily-modifiers
  同上です。
  

18 キーのキーボード

Ben Vallack のキーボードは steno よりもさらにキー数が少なく、驚異の 18 キーです。しかも一番目立つ位置に『リピートキー』なるものが置かれており、同じキーを 2 回連続で打つ必要が無くなっています。

• Has Your Keyboard Got Too Many Keys? - Ben Vallack (Youtube)
  
• BSAG » Hold me closer, tiny keyboard
  

PCBWay で 買えるらしいです……？　気になります。