シングルスレッドの神に会いたいか！？

情報収集

リンク

• AtCoder
  国内の競技プログラミング運営社

• 蟻本
  ガチ勢向けのアルゴリズム本

• AtCoder Clans
  情報収集に (問題をダウンロードする CLI ツールなど？)

レートについて

AtCoder コンテストについての tips

レートの上げ方

過去問をたくさん解く

コンテストについて (AtCoder)

水色を目指すなら、 ABC に出るだけでも良さそうです。

ABC (atcoder beginner contest)

• 毎週土曜の 21:00 に開始
• 制限時間は 100 分
• 問題は A ~ H の 8 題
• レート制限は 2000 まで

ARC (atcoder regular contest)

• 毎週日曜の 21:00 に開始
• 制限時間は 100 分 or 120 分
• 問題は A ~ F の 6 題
• なんか難しそう

その他

• 問題毎に使用言語を変えることはできる？
  たぶんできそう

その他リンク

• tourist
  世界最強の人

おや、兄貴の様子が……？

なんか兄貴さん (実兄) が蟻本を買っていてテンション爆上がりですよ！　競プロに絞れば全然僕にも勝てるので頑張ってほしいです。

お遊びレベルで C++ を始めるとのことで、 cppmap を薦めたら、早速初心者向けの 2 冊を購入していました。いいですね

ABS (Atcoder beginners selection) で入門開始

とりあえず リポジトリを作りました 。動的計画法の 1 番簡単な問題も解けない自信があるけれど、完答できるのだろうか……？

経過としては、 Haskell のコンパイルエラーから『何かが間違っている』雰囲気しか読み取れません。また全探索の解答しか思いつかないという状況です。

解答後は『AtCoder Beginners Selection を Haskell で 』を参照したいと思います。僕も ByteString を使いたいですね。 Haskell 盆栽 70%, アルゴリズム 30% ぐらいの割合で学習できたらちょうど良いと思います。

謎の WA (wrong answer)

$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 9.0.2

$ stack config set resolver ghc-8.8.3
/Users/tbm/dev/hs/abs-hs/stack.yaml has been updated.

$ cat stack.yaml
packages:
- .
resolver:
  compiler: ghc-8.8.3

$ stack setup
stack will use a sandboxed GHC it installed
For more information on paths, see 'stack path' and 'stack exec env'
To use this GHC and packages outside of a project, consider using:

$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 8.8.3

$ stack build
ghc: panic! (the 'impossible' happened)
  (GHC version 8.8.3 for x86_64-apple-darwin):
	Prelude.chr: bad argument: 1543503875

Please report this as a GHC bug:  https://www.haskell.org/ghc/reportabug


--  While building simple Setup.hs (scroll up to its section to see the error) using:
      /Users/tbm/.stack/programs/x86_64-osx/ghc-8.8.3/bin/ghc-8.8.3 -rtsopts -threaded -clear-package-db -global-package-db -hide-all-packages -package base -main-is StackSetupShim.mainOverride -package Cabal-3.0.1.0 /Users/tbm/.stack/setup-exe-src/setup-mPHDZzAJ.hs /Users/tbm/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs -o /Users/tbm/.stack/setup-exe-cache/x86_64-osx/tmp-Cabal-simple_mPHDZzAJ_3.0.1.0_ghc-8.8.3
    Process exited with code: ExitFailure 1

続行

謎のエラー解決

キャッシュが？　残っていたようです:

$ rm -rf ~/.stack
$ stack setup
$ stack build # 成功

ちなみに GHC 8.8.3 用の HLS (1.5.1) ではシンボルのリネームができませんでした。プロジェクト毎に HLS のパスを差し替える方法も考えないといけません。保留……

WA 解決

後方互換性が原因でなかったようです。GHC のバージョンを 8.8.3 にしても正常に実行できました。

ず〜〜と原因を探していたら、 YES ではなく "YES" を出力していました。目でチェックすると脳みそを貫通する〜〜

ABS 1 周しました

意外と難しかった……。 難度 問題 C までなら全探索でも AC になる (ことがある) というのが分かりました。

AtCoder Beginners Selection を Haskell で を見て効率化を目指しつつ、今晩の ABC に備えようと思います。

レート戦 1: ABC 255 惨敗

Haskell 盆栽が辛い。最初の 2 問を解くのに 55 分もかかりました。実戦でモタモタするのは意外に悔しいことが分かりました。

『パフォーマンス』は 700 らしいですが、どういう値か分かりません。 レートは 42 になりました*。なんともネットミーム感のある値……w 解答を見つつ、盆栽慣れとアルゴリズム力強化を並行してやっていきたいと思います。

• AtCoder Beginners Selection を Haskell で
• Haskellで解くAtCoder
• Atcoder 典型90 (GitHub, Qiita)

ミーム収集

• AC
• 学歴

コマンドラインツール導入

atcoder-cli + online-judge-tool を導入しました (リポジトリ) 。テストが楽になった他、解答提出も acc (atcoder-cli) で可能です。

現状のテンプレート:

#!/usr/bin/env runghc

module Main (main) where

main :: IO ()
main = do
  xs <- map read . words <$> getLine :: IO [Int]
  print $ solve xs

solve :: [Int] -> Int
solve xs = undefined

コンパイルせずに (?) runghc で実行しています。依存パッケージなどを考えると stack か cabal-install? で管理できた方が良さそうですが、様子を見ます。

ペール本 1

関数プログラミング　珠玉のアルゴリズムデザイン

この本を読めるようになることが、 Haskell で競技プログラミングを始める最大のメリット？！

1. 最小自由数

リストに無い最小かつ 0 以上の整数を求めます。

Array による解法

まず Haskell の Array は特殊で、フィールド？は定義域と [(kev, value)] です。 Vector でよくないですか？

accumArray も大変な関数でした:

$ ghci
Prelude> import Data.Array

Prelude Data.Array> :i accumArray
accumArray ::
  Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
        -- Defined in ‘GHC.Arr’

使ってみると理解できます:

Prelude Data.Array> accumArray (++) "a-" (1, 7) $ zip [3..5] (replicate 3 "b")
array (1,7) [(1,"a-"),(2,"a-"),(3,"a-b"),(4,"a-b"),(5,"a-b"),(6,"a-"),(7,"a-")]

しかし理解したって何のリターンも無いですよ！　高揚してきました。

コードの書き方も良くない部分がありました。特に replicate をフィルタリング (0 なら有、 1 なら無) に使っていたのは良くないと思います。 mapMaybe (filter_map) の方が意味が明確です。

逆に良い点は数学的で厳密な言葉遣いです。

分割統治法による解法

単なる 2 分探索です。 partition の計算量が最大 N で、最大 log_2 N 回繰り返すので、計算量のオーダは N log N のはず？　1 問目は Haskell 盆栽を過ぎれば余裕ですね。

2. 上位者問題

運算でトップダウンに式変形して分割統治法を実装します。ボトムアップでよくないですか……？　検討中

3. 鞍型探索の改良

む、難しくて何が書いてあるのか分からない！

Union-Find

頻出らしいデータ構造に関する アルゴ式のページ をペラペラと読んで来ました。全ページサクっと読めて素晴らしいですね。蟻本を見たら、栞の 20 ページくらい先に載っていてモチベーションになりました。

環境構築 3

Stack script で import するとき、

• HLS 上で認識
• 実行に成功

今夜の ABC は言語サーバオフで参加するしかない。。

package.yaml の executables を書くとちゃんと補完してくれました。うーむ

レート戦 2: ABC 256 惨敗

前回からの進歩

• Haskellで戦う競技プログラミング を読んだ
  Vector, ByteString, runST の初歩を学んだ (たぶん人のコードが読めるようになった)
• コマンドラインツールでテストケースをダウンロードできるようにした
• 関数型プログラミング 珠玉のアルゴリズムデザイン を 2/30 読んだ

結果

所感

ぐああああああああああああああああああああああああああああああああああ

誤答のペナルティが痛かった……。でも D 問題までは Haskell に慣れるだけで解ける気がします。アルゴリズム力が問われるのは E 問題からでしょうかね。

リストから Vector に乗り換えたい投稿 (WIP)

これで D 問題の TLE を避けられたら今週は優勝！　← ボトルネックは、むしろループの書き方でした。

標準入力

Haskell で解く AtCoder が良さそうです。

固定長配列は無い

固定長配列の Vector を持ちたい！　Haskell に固定長配列は無い。替わりになるものは？:

• LTS 16.11 には Data.Vector.Fixed が無かったよ！
• タプルは遅延評価が怖そう。使い勝手も悪そう
• Array はヒープに配置される気がする
• repa は大変そう

とりあえずリストでいいか……。

リスト内包表記

Stream Fusin の恩恵を受けながら組み合わせを列挙するには？　WIP

再帰

スライスはある？　WIP

ABC 256 D 問題の AC

人の関数をコピペして TLE を突破 (?) してみました。真の AC は遠い……なお公式の解説は 単なるループ で処理していました。 Haskell においても、単なるループになるように再帰関数を書けば良かったのですね。 (書けませんでした)

次回までは、蟻本を読みつつ過去問の A ~ D 問題を解いてみようと思います。もしくは積み本崩しに逃げます。

レート戦 3: ABC 258 圧倒的惨敗

1 問しか解けませんでした。 Haskell 難し過ぎる……競技プログラミング以前の壁があまりに分厚いです。つらいよ！

次回までにやりたいこと

エディタサポートを強くしたいと思います。現在は、 Haskell のバージョンを下げたせいで言語サーバの機能が弱まっています。せめて変数の型はまともに判定したいです。 Slack で聞こうかな。

今回は実力不足を思い知りました。蟻本を読みつつ、 A ~ C 問題に絞って解いてみようと思います。この辺の問題は Rust なら一瞬なのですが、今しばらくは Haskell だからこその味を追い求めてみたいです。

追記

問題 B を読み違えて DFS の問題だと思っていました。ダメ過ぎる！！

レート戦 4: ABC 259 惨敗／好転の兆し

所感

文法エラーで詰まることは無くなりました。今は実装力が足りません。

• B 問題: 小数の精度で死亡
• C 問題: 読解力不足、知識不足 (group / groupBy に気付かなかった)
• D 問題: 明らかにグループ分け問題だが union-find 木が書けなくて死亡

パフォーマンス

そろそろ色変を狙っていきたいですね (成績から目を逸らしながら)

次回まで

解き方が分かる問題は実装できるようになりたいです。ST モナドと mutable vector を試してみるか、人の解答を読みます。

レート戦 5: ABC260 辛勝

D 問題まで行けなかった のですが、心理的には勝利です。 B 問題がキツかった……

所感

• A 問題: 読解力が必要
• B 問題: Haskell では難しい。データ数が増えたら死んでた
• C 問題: 単なる再帰 (ただし整数の桁数制限に気をつける)

パフォーマンス

全然ダメか……。 提出時間で大幅にパフォーマンスが変わる ような気がします。

次回まで

次こそは、出場した ABC の D 問題 (5 問) を解きたいと思います。

レート戦 6: ABC261 もうダメかもしれない

所感

• A 問題: あああ
• B 問題: グアアあああああ
• C 問題: ホワァアアアアアアアアアアアアアアアアアア

所感

• A 問題: 算数ができなくて死亡
• B 問題: 連結リストや Char の boxing が遅すぎて死亡
• C 問題: hashtable と思ったが Haskell が難しくて死亡

パフォーマンス

次回まで

明日は復習だ！

Fold

ただしコードの方 (evil-vimish-fold):

これでスタイリッシュにスタートできます。

レート戦 7: ABC262 末期

VU.Vector は多次元配列には利用できないという罠がありました。たぶん Array を使うのが定石ですね。

所感

パフォーマンス

次回まで

Array を使えるようになろう。。

レート戦 8: ABC264 勝利

前回から

何もしてない……。

所感

今回は易しかったです。前回の反省を活かして、 2 次元の Vector を作ろうとせず Vector.Unboxed.concat しました。

単純に Haskell が書けなくて C 問題で苦戦しました。

パフォーマンス

次回まで

C 問題、 D 問題の他ユーザの解答を読みます。

レート戦 9: ABC265 敗北

前回から

ほぼ何もしてない……。勉強量は成績に如実に現れるものですね。

所感

パフォーマンス

次回まで

B 問題、 D 問題の人の解答を読みます。

> コンテスト開始5分以内にRatedで登録しない場合は、自動的にUnrated扱いとなります。

コンテストには時間通り参加しましょう……

スキルアップの方針

未だ C 問題でも解けないことがあります。 1,000 問くらい解けば水色になれるらしい ので、単なる演習不足と思います。できることとしては、

• Qiita で ABC の解説 (Haskell) を挙げてくれている人がいる ので写経する
  他人の解答は必須です。自分の頭はバグっていて、 2 分探索を始めたら永遠に制御が返ってこないこともありました。 どうせ解けないなら写経した方がマシ です。 Array など、見知らぬライブラリの使い方も身に付くと期待できます。

• 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 の一部問題を解く／解き直す
  余り計算や素数判定などの基本的な算数、動的計画法や貪欲法などの基本的なアルゴリズムを身につけます。しんどいけれど片手間でやっておく必要はあります。

• 競プロ典型 90 問 をやってみる
  たぶんアルゴリズムのカバー率が良いのでやってみるべきではあります。蟻本を読むより、蟻本でカバーされるような問題を解いて身につけるべきと思います。

• 競技プログラミングの鉄則 (解説記事) を読んでみる
  アルゴ式をやればいいのですが、 web サイトを継続的に読むのが苦手なので本を読んでみます。

どれかがアタリだと良いのですが。

Array vs boxing vector

ABC 270 C では、入力を受けてグラフを作成する必要があります。 Mutable な 2 次元配列が必要だと見て死にました。一生 Haskeller にはなれないのかもしれない……

ABC 270 C の Haskell 解答例 では accumArray を使った解答が挙がっています。これが Haskell における典型的な解答であることは理解しています。しかし Array はメモリの使い方が良くないので、 Vector の解答を作って 比較してみました。差分はグラフの生成のみです:

abc270c :: Int -> Int -> Int -> [(Int, Int)] -> [Int]
abc270c n x y uvs = fromJust $ loop 0 y []
  where
    -- flat map in Haskell is `>>=`.
    graph = accumArray (flip (:)) [] (1, n) (uvs >>= (\(u, v) -> [(u, v), (v, u)]))
    loop p c log
      | c == x = Just (x : log)
      | null ns = Nothing
      | otherwise = msum $ map (\n -> loop c n newLog) ns
      where
        -- neighbors of the child
        ns = filter (p /=) (graph ! c)
        newLog = c : log

solve :: Int -> Int -> Int -> [(Int, Int)] -> [Int]
solve n x y uvs = fromJust $ loop 0 y []
  where
    graph = V.create $ do
      -- +1 for 1-based index
      vec <- VM.replicate (n + 1) []
      forM_ uvs $ \(u, v) -> do
        VM.modify vec (v:) u
        VM.modify vec (u:) v
      return vec
    loop p c log
      | c == x = Just (x : log)
      | null ns = Nothing
      | otherwise = msum $ map (\n -> loop c n newLog) ns
      where
        -- neighbors of the child
        ns = filter (p /=) (graph V.! c)
        newLog = c : log

どちらでも良いことが分かりました。 Array も mutable vector もまともに使った……もといコピペしたのは初めてです。 特に boxing な mutable vector を得たのは 銀の弾丸 感が凄い。次の C 問題は強引に突破できるかな……？

一歩一歩が非常に重いのですが、鉄則本の練習問題を含め、前に進んでいきたいと思います。

repa は unboxing らしいので accumArray の代わりにはなりません。

モナドへの興味

Data.Vector.Unboxed.create の中で mutable vector 以外の可変変数を作れなくて困ったことがありました。これは do 記法の中が ST モナドか何かのチェインになっていたためだと思います。

すべてを IO モナドにするみたいな抜け道と、『モナドの設計』のような成功法、どちらにも興味が湧きます。 Haskell ならではの味が少しだけ見えてきました。

標準ライブラリ

sortBy [DONE]

sortBy の使い方は 3 冊の Haskell 入門書にも載っていませんでした。まあ sortOn とか Down が使えれば十分かな……

https://qiita.com/TTsurutani/items/d069363e9f4d613abf10

アルゴリズム

2 分探索 [DONE]

ソート済み配列を OK / NG に区切って境界を見つける方法が有名みたいです。

https://www.forcia.com/blog/001434.html

エッジケースを Maybe で処理してみました。もう少し綺麗になってほしい……

-- | Binary search for a sorted items which returns the `(ok, ng)` index pair at the boundary.
-- |
-- | Example
-- | -------
-- |
-- | With an OK predicate `(<= 5)`, list `[0..9]` can be seen as:
-- |
-- | > [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-- | >  <-------------->  <-------->
-- | >         ok             ng
-- |
-- | In this case `bsearchMain` returns the `(ok, ng)` = `(5, 6)` pair:
-- |
-- | > > let xs = [0..9] in do
-- | > >   print $ bsearchMain (0, 9) (\i -> xs !! i <= 5)
-- | > (5, 6)
-- |
-- | Note that the closure CANNOT BE an exact match. Use a range-based predicate instead.
-- |
-- | Errors in edge cases
-- | --------------------
-- |
-- | While this function works for the above example, be warned that it's incomplete.
-- | It makes errors in certain edge cases:
-- |
-- | 1. The only `ok` item is at the end of the list.
-- | 2. The only `ng` item is at the beginning of the list.
-- | 3. There's no `ok` item or there's no `ng` item.
-- |
-- | So this function is wrapped by `bsearch`.
bsearchMain :: (Int, Int) -> (Int -> Bool) -> (Int, Int)
bsearchMain (ok, ng) isOk
  | abs (ok - ng) == 1 = (ok, ng)
  | isOk m = bsearchMain (m, ng) isOk
  | otherwise = bsearchMain (ok, m) isOk
  where
    m = (ok + ng) `div` 2

-- | Binary search for inclusive range (from left to right only)
bsearch :: (Int, Int) -> (Int -> Bool) -> (Maybe Int, Maybe Int)
bsearch (low, top) isOk = bimap wrap wrap result
  where
    result = bsearchMain (low - 1, top + 1) isOk'

    isOk' :: Int -> Bool
    isOk' x
      | x == low - 1 = True
      | x == top + 1 = False
      | otherwise = isOk x

    wrap :: Int -> Maybe Int
    wrap x
      | x == low - 1 || x == top + 1 = Nothing
      | otherwise = Just x

Union-Find [DONE]

MVector ベースの実装 (スクラップの下の方) 。

• Union by rank or union by size
• 経路圧縮 (path compression)

https://algo-method.com/descriptions/132

ST array の場合:

https://kseo.github.io/posts/2014-01-30-implementing-union-find-in-haskell.html

データ構造

List [DONE]

• sort, sortBy
• group, groupBy
• cycle を使った uninterleave

 let dys = [a | (a, True) <- zip ds $ cycle [True, False]]
   in let dxs = [a | (a, True) <- zip ds $ cycle [False, True]]
    in

• nub で非ソート済みリストを deduplicate する
• ソート済みリストの deduplicateion = 圧縮:

compress []     = []
compress (x:xs) = x : (compress $ dropWhile (== x) xs)

bytestring vs text [DONE]

• Haskell の char は 40 バイトらしい
• bytestring をマルチバイト文字に使おうとすると罠が色々ある
• このバージョンの text は内部データを UTF-16 でエンコードしている

最新の text (AtCoder では利用できない) が Rust の String に近い？　まあ bytestring でいっか……

array [WIP]

• TODO: 内部のデータ構造は？
• ! 演算子で e を取り出せるが対応の i が無ければ死亡する (optional が欲しければ 2 分探索しよう?)
  • TODO: ! 演算子の計算量は O(1) と思って良い？
• assocs で [(i, e)] を取り出すことができる。 map や scan する場合はこれ？ でも内部的にはリストではないはずか……
• accumArray の使い方

TODO: 2 次元配列の使い道

containers

IntMap [WIP]

2 分探索木と思えば良い？

IntSet

vector [Done]

MVector 含め使えるようになってきた。

vector-algorithms [TODO]

MVector のアルゴリズム一覧で、たとえば in-place なソートを提供するみたい。

通常は標準入力を読む際に VU.fromList . mapAndSortList <$> readStdinAsIntList と書くだけで済む気がする。 Fusion のおかげで負荷も少ないはず……

モナド

IO / ST

というか Vector の内部実装が気になります。

https://stackoverflow.com/a/8197275

RealWorld?

https://wiki.haskell.org/Monad/ST

D 問題メモ

重い。。

IntMap (key / value), IntSet (key のみ)

辞書は計算量やメモリ使用量の削減に役立ちます。

ABC 274 D

全探索では 2^N の点が現れるため、まったく計算が間に合いません。しかし重複を取り除いていけば、実際に到達可能な点数 (N^2) まで計算量を下げる事ができます:

YouTubeのvideoIDが不正ですhttps://youtu.be/Oc1JP9XmIsU?t=3200

つまり Vector を使うと TLE だが IntSet を使えば AC!　しばらく理解できなかったし頭良いなと思いました。集合を使えば空間の大きさまで計算量を落とす事ができる時もある。なるほどなぁ……

点をオフセットで表現すると、単純な DP (空間配列のダブルバッファ) よりもシンプルな解答になって Haskell には易しいです。これも頭いいなぁ:

https://qiita.com/gotoki_no_joe/items/ffe6dad21b764eb03ead#d---robot-arms-2

ABC 275 D

フィボナッチ関数よろしくメモ化するのが簡単そうです。 Vector で出すと RE (runtime error) になりました。手元で大きな N を入力として与えると、デカい Vector を作った時点で heap overflow が発生します。

Atcoder のメモリ制限は 1GB (10^9 バイト) 程度らしいので、 8 バイト整数を 10 ^ 9 / 8 個ほどしか作れません。問題文によると N は最大 10^{18} ですから、明らかにメモリが足りないことが分かります。

IntMap を使えば 解決します 。ただし IntMap は immutable なので、返値で IntMap を返します。

https://qiita.com/gotoki_no_joe/items/83bd5795bbf795205116#d---yet-another-recursive-function

IORef に関して、 この辺を読む限り 参照先を変えられるポインタに過ぎないようです。 IORef に参照される値は immutable なので、全然手続型ではないな……？

Union-Find

ABC 259 D

TODO

https://qiita.com/gotoki_no_joe/items/17b55046a4ce4fc98566#d---circumferences

雑多メモ

Write Yourself a Scheme in 48 Hours を軽くやってみる (repo)

Text

• 記事中では String を使っているが、 Haskell の String は非常に効率が悪いことで有名だった。

  • UTF-8 を扱えるライブラリとしては Text が推されている。最近は Text の内部実装にも UTF-8 を使っているらしいが、パース中は ASCII 文字にしか興味がない。 bytestring を使ってみたい。
  • bytestring で UTF-8 を扱う場合に罠があるという。 Octets が失われる？　うーむ。。 Text は Text で面倒くさいけれども Text にしておこうか。

• Text における 1 文字は T.singleton で良い？ 恐ろしく面倒くさい上に自信を失う。所詮 Rust しか使えないミジンコなんだ…… → 1 文字は Char 。内部実装がよく分からない (Rust の String と思っていいのだろうか)

• Text を使ったリポジトリ を見つけたけれど unpack して String に変換している。

• UTF-8 でファイルを開く方法

どうも Tex.ParserCombinator.Parsec ではなく Text.Parsec と Text.Parsec.Text を import すると普通に動いた。 Text も単なる Char のストリームと見做せる気がする。このチュートリアルは古いのね……

Haskell

• サブモジュールは import できない？
  GHC.IO を qualified import しても IO.Encoding の形でアクセスできなかった。直接 GHC.IO.Encoding を import しなければならない。これは Odin と同じで、僕が Odin を止めた理由でもあった……。 Public / private を export で表現する点も苦手で、理想の関数型言語が Haskell 以外で現れてほしい気持ちがある。名前空間もグローバルだしな。今もどこかでポスト Rust の関数型言語が開発されているのだろうか。
• Haddock でドキュメント生成。重い。構文は reStructuredText みたい。
• こうしてみると GHC のエラー出力は Rust に似ている (Rust が似ている？)
• 言語拡張 (LANGUAGE pragma) はファイル毎に有効にするか、 Stack なら default-extensions を書いてプロジェクト全体で有効にできる。
• ポスト GHCup の時代に Stack を使うのは止めようという話をちらほら見る。 Stack は GHC のインストーラとして使われていた……？　cabal (CLI) には GHC のバージョンを切り替える機能もあるらしいので、今年の Advent Calendar 記事を参考に乗り換えたい。
• Nix に基づく開発環境も解説が欲しい。

Web 記事巡回

赤黒木とはノードに関連づけた『色』を利用してバランスされたソート済み二分探索木。これくらいサクッと書けたらよいのだけれど

https://gihyo.jp/dev/feature/01/functional-prog/0004#

Scala では本格的にモナドが使える。 Extensible effects ら辺が分からなかった…… (けどイメージは持てた)

https://blog.recruit.co.jp/rmp/server-side/post-21805/

Monad は基本的な表現を持った型クラスに過ぎない

https://kazu-yamamoto.hatenablog.jp/entry/20150128/1422413182

Monad が満たすべき性質をシュッとしたコードを書くための性質だと思って見てみる

https://kazu-yamamoto.hatenablog.jp/entry/2019/04/11/111238

カリー化には多変数関数をバラすものとタプルをバラすものがある。二変数関数と関数閉包で多変数関数を表現できて嬉しい話しか知らなかった。

https://kazu-yamamoto.hatenablog.jp/entry/20110906/1315279311

AtCoder ブラウザ拡張

ユーザースクリプト (grease) は Firefox でも動きました。問題の diff やユーザのレートを表示する拡張が良いです。ただ痒い所に手が届くものは Chrome 拡張も多かったです。

https://scrapbox.io/magurofly/AtCoderをするとき、入れておくといい拡張機能など

特に Haskell のハイライトを直すやつ:

https://qiita.com/mod_poppo/items/af11f07169fa9bdab844

灰 diff の C 問題が解けない (ABC 276)

つらすぎる。。 Haskell でバグり出すと止まりません。実装の方針が良くないのでしょう。

アルゴリズムのカバー率ではない部分で死んでおり、鉄則本を進めても案外レートは上がらないかもしれません。その方がある意味気は楽ですが。

• ZVON? にはコードの用例が載っていて良かった (たとえば accumArray)
• シグネチャはコードアクション (LSP) で出すこともできる

Union-Find の実装

Union-Find 木の内部データに Data.Vector.Unboxed.Mutable.MVector を使う解答 を見ました。いい！

計算量削減

元コードで union by rank (size?) と経路圧縮が行われており、大変参考になりました。アルゴ式に解説があります。

https://algo-method.com/descriptions/133

もう少し型を頑張ってみたい

Unbox を実装……できない

Int の代わりに data UfNode = Child Int | Root Int を使いたかったのですが、以下のエラーが出ました:

-- | * `Child parent`
-- | * `Root size`
- data UfNode = Child Int | Root Int

• No instance for (VUM.Unbox UfNode)
    arising from a use of ‘VUM.read’
• In a stmt of a 'do' block: node <- VUM.read vec i
  In the expression:
    do node <- VUM.read vec i <略>

UfNode が Unbox ではないと。これには Haskell High Performance Programming を持ってきて対抗します。富豪プレイは最高だぜ (Haskell 本を 5 冊持っている顔):

- data UfNode = Child Int | Root Int
+ data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int

あれコンパイル通らない……?　大量の boiplerplate が必要なようですね

https://stackoverflow.com/questions/22882228/how-to-store-a-haskell-data-type-in-an-unboxed-vector-in-continuous-memory

しかも代数的データの場合は載っていない。 Deriving 用クレートの template Haskell 展開結果を見ればいいのですが、もう boxed な MVector 使っちゃおっか……

IO モナドで実装

まずは IO モナドで実装してみました。型パラメータが減って簡単です。

newtype UnionFind = UnionFind (VM.IOVector UfNode)
data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int

{-# INLINE root #-}
root :: UnionFind -> Int -> m Int
root uf@(UnionFind vec) i = do
  -- ~~~

PrimState で実装

IO モナドと ST モナドを抽象する primitive パケージの PrimMonad 及び PrimState に移行しました。

newtype UnionFind s = UnionFind (VM.MVector s UfNode)
type IOUnionFind = UnionFind RealWorld
type STUnionFind s = UnionFind s

root :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
root uf@(UnionFind vec) i = do
  -- ~~

• do ブロックの中で Root s <- VM.read vec py のようにパタンマッチすると Could not deduce (MonadFail m) というエラーが出ました。代わりに unwrapRoot を使ってみました。
• PrimMonad m => .. が出る場合は INLINE プラグマを付けておくのが無難らしいです。

-- | Union-find implementation (originally by `@pel`)
newtype UnionFind s = UnionFind (VM.MVector s UfNode)

type IOUnionFind = UnionFind RealWorld
type STUnionFind s = UnionFind s

-- | `Child parent | Root size`. Not `Unbox` :(
data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int

-- | Creates a new Union-Find tree of the given size.
{-# INLINE newUF #-}
newUF :: (PrimMonad m) => Int -> m (UnionFind (PrimState m))
newUF n = UnionFind <$> VM.replicate n (Root 1)

-- | Returns the root node index.
{-# INLINE root #-}
root :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
root uf@(UnionFind vec) i = do
  node <- VM.read vec i
  case node of
    Root _ -> return i
    Child p -> do
      r <- root uf p
      -- NOTE(perf): path compression (move the queried node to just under the root, recursivelly)
      VM.write vec i (Child r)
      return r

-- | Checks if the two nodes are under the same root.
{-# INLINE same #-}
same :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> Int -> m Bool
same uf x y = liftM2 (==) (root uf x) (root uf y)

-- | Just an internal helper.
unwrapRoot :: UfNode -> Int
unwrapRoot (Root s) = s
unwrapRoot (Child _) = undefined

-- | Unites two nodes.
{-# INLINE unite #-}
unite :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> Int -> m ()
unite uf@(UnionFind vec) x y = do
  px <- root uf x
  py <- root uf y
  when (px /= py) $ do
    sx <- unwrapRoot <$> VM.read vec px
    sy <- unwrapRoot <$> VM.read vec py
    -- NOTE(perf): union by rank (choose smaller one for root)
    let (par, chld) = if sx < sy then (px, py) else (py, px)
    VM.write vec chld (Child par)
    VM.write vec par (Root (sx + sy))

-- | Returns the size of the root node, starting with `1`.
{-# INLINE size #-}
size :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
size uf@(UnionFind vec) x = do
  px <- root uf x
  s <- unwrapRoot <$> VM.read vec px
  return s

型ファミリー (型族) って何だろう

また謎が増えました。 Haskell 難しい……

TLE だと…… (277)

しかも解答の筋は別に間違っていないだと……。茶色にすらなれる気がしない (・ω・)

→ IntMap の更新ミスってるよ〜

ただデバフが無くても D 問題が解けないレベルと思うので、アルゴリズムをメインでやっていくのが良い気がします。

• IntSet でソートと重複除去ができるか
• compress = group . sort じゃん

セグメント木の実装

Inline module が欲しい

現在の Haskell には inline module が無いようです。Module.function と名前空間を区切ることができません。

ScopedTypeVariables

こちら forall a m. が無ければコンパイルエラーとなります:

queryByRange :: forall a m. (VU.Unbox a, PrimMonad m) => MSegmentTree a (PrimState m) -> (Int, Int) -> m a
queryByRange (MSegmentTree !f !vec) (!lo, !hi) = fromJust <$> loop 0 (0, initialHi)
  where
    !initialHi = (VUM.length vec) `div` 2 - 1
    loop :: Int -> (Int, Int) -> m (Maybe a)
        ..

forall a m. が無い場合、 queryByRange の a, m と loop の a, m が別物として扱われ、 a と a1 の不一致、 m と m1 の不一致が起こります。

激しいバグ

デバッグの仕方が分からない……。始めは IO で実装すれば print デバッグができて良いと思います。

TODO: MaybeT を使うべき？

TODO: freeze したい

MVector は Show できません。 MShow みたいなのものは std に無い気がしますし、 vector の generic モジュールを参考に freeze したり、より汎用的な関数を作る必要を感じます。

散らかって来たので閉じます〜