このスクラップは

本やガジェットをひけらかしつつ、水色コーダーを目指す投稿です。

方針

水 diff を 100 問解けば水色コーダーになれる説 (願望) を検証します。スクラップ作成時の進捗は 32/100 です。

注意

Haskell 目当てなら、もう見所が無いと思います……！

良かったもの

消化用ノート

PAST まで

• 水 diff streak (ABC 255 まで)
• 残件処理
  • 鉄則本 ゲーム
  • Chokudai Speedrun 02 残り
  • PAST 第 8 回 残り
• PAST (6 月) 対策
  • PAST 13 回
• PAST 上級本
  • 遅延セグメント木
  • 最小費用流
  • 平面走査

PAST 後

• PAST 上級本 2/2
  • 考察テクニック
  • DP
• 水向け演習
  • TDPC (既知の範囲)
  • 典型 90 問 ☆ 4, ☆ 5
• もっと DP
  • EDPC (未知の範囲)
  • TDPC (未知の範囲)
• 典型収集漏れ
• 過去問がすべて解ける考察フローチャート作成

典型ノート

水 diff 演習が落ち着いてから、取りこぼした典型問題を拾って行きたいと思います。

少なくともこれだけ零しているのか……怖すぎる！

https://ei1333.github.io/luzhiled/

日報 2023-05

400 AC

水 diff は 40 問解きましたが、 9 割方解説 AC でした。非常に厳しい……！

AC heat map (max difficulty)
水 diff は 1 日 1 問が限界のため演習期間がやたら長い

難度感

本番は時間制限が厳しいのが気にかかっています。水 diff までは trivial という感覚に到達しないといけません。今は茶〜緑も大分怪しいけれど……。

これまでの主な学び

全探索を信じよ！

今後の方針

もうすぐ演習量が こちらの色辺記事 に匹敵してしまいます。この先三ヶ月で現在のタスクをすべて消化し、それでも色変が厳しい場合は、 ARC 特攻するか高度典型を狙うしかないです。。

WIP: 木の実装を読んでみたい

エアロバイクと Kindle Scribe のコンボで情報収集します。

Fast mergable interger maps

IntMap の元ネタであるという Chris Okasaki and Andrew Gill. Fast mergable integer maps, 1998 を読みました。こういう実装紹介の論文 (論文？) はエアプに最適です。

• 解説コードは Standard ML です。
• 完全二分木から patricia tree (基数木？) へ。
  • 整数値キーの完全二分木は、各 branch が各 bit の 01 の分岐に相当します
  • 完全二分木をうまく圧縮すると patricia tree になります。へー
• lookup, insert, union が再帰的になるのが分かりました。
• 平衡処理が無くてあれっとなりました。
  • 確かに IntMap も lookup とか insert は O(\min(n ,w)) ですね。
  • ここで W とは木の最大の深さ (64) なので、操作コストは定数です。
  • まあ平均したら O(\log n) なんじゃないでしょうか。
• 赤黒木は検索・挿入は速いがマージが遅い。 IntMap (big-endian patricia tree) はマージもそこそこ速い。

QuickChecking patricia trees

上の論文には バグがあるらしい ので、その修正を含むという Jan Midtgaard. QuickChecking patricia trees, 2018 を読んでいきます。

• QuickCheck で patricia tree をテストして正しさを保証、しようとして上記論文のバグを発見した
• テストにはプロパティベースのテストとモデルを使用したものがある？
• WIP

Haskell ネタ

思い切って入力処理を短い名前に

こんな感じにしてみます。

main :: IO ()
main = do
  -- list
  [n] <- ints
  -- tuple
  (!x1, !x2) <- ints2
  -- vector
  !xs <- intsVU

  putStrLn "TODO"

kill-emacs に学ぶ trivial 解への分岐法

競プロ限定なら exitSuccess すれば良し！　やっぱり Emacs Lisp は勉強になるなぁ ()

import System.Exit (exitSuccess)

main :: IO ()
main = do
  let isTrivial = True

  when isTrivial $ do
    putStrLn "trivial!"
    exitSuccess

  putStrLn "run a non-trivial solution"

初歩的な回転の復習

人は皆、二次方程式の解の公式を忘れ、平方完成するようになる。信じられないかもしれないが本当の話だ。遠くない内に君も経験することになる。

マンハッタン距離の典型問題で 45 度回転が出てきました。回転、回転……？　回転といえば複素数、思い出さねば……！

関数のべき級数展開

無限回微分できる関数 f を x = x_0 の周りで展開するとこうなるとか:

オイラーの公式

\sin, \cos をマクローリン展開して上手に処理すると e^{i\theta} = \cos \theta + i \sin \theta が求まったはず。

回転

r e^{i\theta} で表される点を、いや極座標表示する意味は無かったが、原点を中心に \phi 度回転させると:

特に \phi = \frac {\pi} {4} の場合、回転行列は:

基底を元に回転行列を求めるやつ

忘れた (そもそも線形代数が正しくインプットされていない orz)

マンハッタン距離と 45 度回転

2 点間の距離を d = |\Delta x| + |\Delta y| と定義するやつですが、 45 度回転すると d = \max (|\Delta x|, |\Delta y|) になって素直に求めやすくなります。思いつかなかった……。

45 度回転は、上の回転行列を \sqrt 2 倍すれば、 x, y 座標の足し算・引き算で処理できます。しかも \sqrt 2 倍に拡大したことで、回転後の座標系の \max (|\Delta x|, |\Delta y|) が元の座標系のマンハッタン距離と一致するトリビア付き。

感想

正しくインプットできなかった数学は、改めて学び直そうかと思いました。 FFT も典型らしい……！

グリッド上の 01-BFS or 枝刈り BFS

問題

グリッド上の始点から終点へ駒 (例: 飛車) を動かす。始点から終点まで移動する最小の行動回数を求めよ。

方法 (01-BFS or 枝刈り BFS)

普通にグラフ探索を書いても通りますが、重複除去が難しく TLE しがちです。 01-BFS を使うと安定します。

参考になるのは 典型 043 の解答コード、 けんちょんさんの ABC 246 E 解説 など。とくにけんちょんさんの解説が良さそうです。

僕は重複した探索の除去を頑張っていましたが、そうかスコアで枝刈りすればよいのか……？

問題例

• 典型 043: 飛車
• ABC 246 E: ビショップ
• ABC 176 D: 周囲 5x5 (方向不要)

コードメモ

Python の倍くらいのコードになって非常に厳しい……

bfs246E :: (Int, Int) -> UArray (Int, Int) Bool -> UArray (Int, Int, Int) Int
bfs246E !start !isBlock = runSTUArray $ do
  -- dp ! (y, x, iDir). The third dimension is required!
  !dp <- newArray ((0, 0, 0), (pred h, pred w, pred 4)) undef
 
  forM_ [0 .. 3] $ \iDir -> do
    writeArray dp (fst start, snd start, iDir) 0
 
  let popLoop Seq.Empty = return ()
      popLoop (((!y0, !x0, !iDir0), d0) Seq.:<| seq0) =
        foldM step seq0 [0 .. 3] >>= popLoop
        where
          -- collects neighbors
          step !acc !iDir
            | not (inRange bounds_ (y, x)) || isBlock ! (y, x) = return acc
            | otherwise = do
                !lastD <- readArray dp (y, x, iDir)
                -- REMARK: we can come to the same point in the same direction in different ways:
                if lastD /= undef && lastD <= d'
                  then return acc
                  else do
                    writeArray dp (y, x, iDir) d'
                    if iDir == iDir0
                      then return $ nextItem Seq.<| acc
                      else return $ acc Seq.|> nextItem
            where
              (!y, !x) = add2 (y0, x0) (dyxs VU.! iDir)
              !d'
                | iDir == iDir0 = d0
                | otherwise = succ d0
              !nextItem = ((y, x, iDir), d')
 
  popLoop . Seq.fromList $ map (\iDir -> ((fst start, snd start, iDir), 0)) [0 .. 3]
  return dp
  where
    !undef = -1 :: Int
    !bounds_ = bounds isBlock
    (!h, !w) = both succ . snd $ bounds isBlock
    !dyxs = VU.fromList $ [(1, 1), (-1, 1), (1, -1), (-1, -1)]

TODO: 枝刈り BFS

作用付き モノイド (m, *) (operator monoid)

注: 群は初見です。意図せぬ誤りが含まれると思いますが、ご了承ください。

半群とは、モノイドとは

集合に結合的な演算 <> を与えたものを半群と呼びます。たとえば (Integer, max) の組 Max を半群のインスタンスにできます。半群の型クラスは以下です:

class Semigroup s where
  -- (s1 <> s2) <> s3 == s1 <> (s2 <> s3)
  (<>) :: s -> s -> s

半群に <> に関する単位元を加えたものを モノイド と呼びます。たとえば (Int, (+), 0) の組 Sum をモノイドのインスタンスにできます。モノイドの型クラスは以下です:

class Semigroup s => Monoid mwhere
  -- s1 <> m == m <> s2 == m
  mempty :: m

作用付きモノイド (m, *)

モノイド m に以下の性質を満たす作用 * :: m -> a -> a を加えた (m, *) を作用付きモノイドと呼びます。

作用付きモノイドの観点で見ると、 (m, <>, mempty, a, *) がすべて視野に収まります。

この式は (結合法則でもないし) 何かと聞いてみたところ、作用付きモノイドを教えていただけました。感謝！

例: 置換配列は作用付きモノイド

たとえば、整数の置換を表す配列は作用付きモノイドであるとみなすことができます。

• モノイド m: 置換配列です。
  • 結合的演算 <>: 置換配列の合成を行います。
  • 単位元 mepmty: 恒等置換を表す配列 [0, 1, 2, ..] を返します。 ^[1]
• 作用の対象 a: 置換される整数 Int です。
• 作用 *: * :: 置換配列 -> Int -> Int は置換を実行します。
  作用は置換配列を置換関数 Int -> Int に変えるものであるとも捉えられます。

ダブリング (binary lifting)

作用付きモノイドはダブリング (binary lifting) の対象となります。ダブリングの際は作用付きモノイドを事前に結合できることを活かし、 m_1 同士の 2^i 回結合を事前計算しておきます。

ダブリング後は、 m_1 の n 回適用を定数時間で計算できます:

ここで (m_1)^{n} は事前計算しておいた (m_1)^{2^i} の結合によって計算できるため、 (大きな) 定数時間で計算可能です。 (もしくは (m_1)^{2^i} による置換を順次適用すれば良いです。こっちの方が一般的な上に高速ですね)

なぜ作用付きモノイドなんてものを考えるのか

考察と実装が穴埋めゲームになって簡単になるためです。

なぜ作用付きの半群ではなく作用付きモノイドを考えるのか

なぜ mempty が必要なのかという点ですが、いや別に無くても良いかもですね……。 m_1 の 0 回適用は、 n == 0 の場合で分岐すれば単位元は必要ありません。

ただダブリング以外の例では、分岐が減ると嬉しい場合が多いです。 mempty を遠慮なく畳み込み (結合 <>) の初期値として使えます。モノイドである必要は無いかもしれませんが、モノイドとした方が便利であるため、モノイドに限定して考えています。

どうしても半群が モノイド にならない場合、 Maybe で単位元 Nothing を加えれば半群がモノイドになります。分岐を外出しできて便利なので、やはりモノイドだけを考えれば良いのだ！

Haskell で作用付き モノイド を表現するには

1. 型クラスを使う

やはり class OperatorMonoid を作るのが最も美しい方法に思えます。 Maybe でラップすると半群がモノイドになる、モノイドのタプルはモノイドの直積であるなど強力な機能を利用できます。しかしモノイドへの慣れが必要なので、一旦置いておこうと思います。

2. データ型の中に関数を入れる

data や newtype を使っても良さそうです ^[2] 。まずこちらの実装を試し、慣れてきたら型クラスに移行してみようと思います。

data OperatorMonoid m a = OperatorMonoid m (m -> m -> m) (a -> m -> a)

-- 作用は m -> a -> a ではなく a -> m -> a の形にしました。
-- m -> a -> a の方が数学的に美しいですが、畳み込みの際は不便だと思います。

data BinaryLifting m a v = BinaryLifting (OperatorMonoid m a) (v m)

-- TODO: 使ってみる

binLift :: (VG.Vector v m, VG.Vector v Int) => OperatorMonoid m a -> BinaryLifting m a v
binLift opMonoid@(OperatorMonoid !op0 !mapp !_) = BinaryLifting opMonoid ops
  where
    step !op !_ = op `mapp` op
    !ops = VG.scanl' step op0 $ VG.enumFromN (0 :: Int) 62

binLiftReplacement :: VU.Vector Int -> BinaryLifting (VU.Vector Int) Int V.Vector
binLiftReplacement !op0 =
  binLift $ OperatorMonoid op0 (\op1 op2 -> VU.map (op2 VU.!) op1) (flip (VU.!))

-- | Binarily lifted operator monoid action application.
mactB :: (VG.Vector v m) => (BinaryLifting m a v) -> a -> Int -> a
mactB (BinaryLifting (OperatorMonoid !_ !_ !mact) !ops) !acc0 !nAct = VU.foldl' step acc0 (rangeVG 0 62)
  where
    step !acc !nBit
      | testBit nAct nBit = acc `mact` (ops VG.! nBit)
      | otherwise = acc

他の作用つきモノイドの例

• 全方位木 DP
  作用の型が m -> m -> m だと思うのですが、正しい説明では無い気もして省略しました。

• 遅延セグメント木
  実装中..

確認中……

もう少し整理できそうなので色々あたってみたいです。

https://zenn.dev/santamn/articles/81f4bf9a4cb139

AtCoder 以外のジャッジ環境

他サイトを覗いてみました。使用可能ライブラリの一覧すら見つからなくて辛い。ひとまず AtCoder におけるテンプレートを提出してみると……

• Yukicoder: primitive が無い、 extra が無い
  要望を出せば通りそうな気はしています。
• Codeforces: vector すら使用不能、コード長に制限あり
  C++ 前提という感じがしますね。
• Topcoder: 実名前提なので登録したくない
  もはや登録したくない。

結局富豪スタイルで挑戦できるのは AtCoder だけでした。その AtCoder でもジャッジ環境の更新は隔年であり、競プロって凄くローカルなものだなと認識を改めました。

そもそもファイル分割ができない特殊な環境ですし、今から Common Lisp のライブラリを大量に入れようと思っても不可能ですものね。

Codeforces を覗いた後、 AtCoder の窓口は随分と広かったんだなと感激しています。 Haskell のジャッジ環境も奇跡的に良くできていて、先人に感謝するばかりです。今の AtCoder が無ければ、一生 Haskell を書く機会が無かったかもしれません。

AtCoder Charts

パフォーマンスの変化を可視化してもらいました。もっと水パフォが欲しい (。ω。)

遅延評価セグメント木を実装してみた

PAST 上級本 と cojna/iota を参考に遅延評価セグメント木を実装しました。 cojna さんのコードは入出力やグラフを始め、全体的に理想的な構成に見えます。今後も参考にしていきたいです。

典型 90 問: 029 - Long Bricks（★5）

これを通しました。 とにかく大変でした 。色々な自信を失います…… (定期) 。今後リファクタリングしていきます。

https://atcoder.jp/contests/typical90/submissions/41609860

現在の疑問点

• バグは無いのか
  PAST 上級本の類題などで検証します。

• 正格なセグメント木と lazy なセグメント木のデータ型は分けるべきなのか
  分けない理由があるとしたら、正格版セグメント木の 1 点更新のコードを再利用できること？

• class MonoidAction はまだ早い
  僕のレベルだと、問題毎に MonoidAction のシンスタンスを作ることになります。汎用的なモノイドだけ定義しておき、モノイド作用は変数で表現した方が良い気がしてきました。

derivingUnbox
  "Height"
  [t|Height -> Int|]
  [|\(Height h) -> h|]
  [|\h -> Height h|]

instance Semigroup Height where
  h1 <> h2 = max h1 h2

instance Monoid Height where
  mempty = Height 0
  mconcat = maximum

instance MonoidAction Height Height where
  mact = max

やはり Blender をやらなければならない

遅延評価セグメント木では、区間の移動時にプラットフォーマーゲームのグリッチみたいな変な挙動があって面白かったです (隣の区間へ壁抜けした後に親区間へ移動する) 。やはりこれを (無駄に) 3D モデルで共有してみたい……！

LCA を経由して、木の上の任意の 2 点間を畳み込む (構想のみ)

本日のモノイドはー、 (ドゥルルルルルルッルルルン) 可換モノイドです！

LCA (最小共通祖先) 高速計算法 (ダブリング + 2 分探索) の復習

共通祖先とは (例)

以下の木において、頂点 root, 頂点 child は 2 頂点 (v1, v2) の共通祖先です。特に child は、 (v1, v2) の最小共通祖先です:

      . root: common ancestor
      |
      . child: lowest common ancestor
     /  \
V1 .      .             # 見栄えしない
            . v2        # やはり Blender をやらなければ……！

木の上の任意の 2 点間の経路は、 v1 - lca(v1, v2) - v2 という 2 つの経路で構成できます。

lca(v1, v2) が v1, v2 のどちらかと等しい場合は、片方の経路が長さ 0 であると言えます。

LCA 計算の事前準備

木の根から DFS して 2 つの配列を作成します:

• 配列 1: 頂点 → 根からの距離
• 配列 2: 頂点 → Maybe 親

配列 2. をダブリングすると、『頂点 v の n 番目の親』を O(1) で計算できるようになります。

LCA を求める

1. (v1, v2) を同じ深さまで移動させて (v1', v2') とする
2. 2 分探索で LCA を求める
   判定問題 parentN d v1' == parentN d v2' は d に関して単調です

      . root
      |
      . # 長い木の LCA も O(log N) で求まる
      |
~~~~~~~~~~~~~~~~
     |  |
     |  |
     |  |
     /  \
V1 .      . v2'
            . v2

LCA を経由した畳み込みを行うには

本題の畳み込みですが、事前準備でもう 1 つ配列を作成します:

• 配列 3: 頂点 → 親へ移動する際に結合するモノイド
  ダブリングします

畳み込みのシグネチャとしては、おそらくこうなるはずです: けっこう難しい

実装しよう…… (・ω

cabal でビルドするとテストが爆速になった

今更ですが QoL が上がりました。アルゴリズムのオーダーが間違っていたらすぐに気付けそうです:

$ cabal build a-exe
$ cabal run a-exe

なぜ stack script を使っていたのか

stack でビルドすると、 a-exe, b-exe, .. がすべてビルドされ、 1 つのファイルにエラーがあるとテストが実行できなくなりました。

cabal だとそんな心配は無さそうですね。謎……

TODO: haddock

cabal haddock a-exe とかやっても html が生成される気配が無く……？

PAST 対策中

2023/06/03 (土) 13:00 ~ 18:00 にアルゴリズム実技検定があります。上級認定を目指すなら、 15 問中 12 問解けねばなりません。もう遅いですが対策します。

https://past.atcoder.jp/

PAST 第 8 回 をやってみて

PAST の出題傾向は狭く深く。 12 問までは解説 AC できました。

• 数列に関する問題が多い
  ソート、 2 分探索、尺取り法、座標圧縮、セグ木、主客転倒 (contribution の和) でゴリ押しすると解けます。方針通り 1 発で実装できるよう、ライブラリ化しておくことが重要です。
• 2 部マッチングが 1 問
• 考察が難し過ぎる問題が 2 問 (エキスパートは到底無理だ)

PAST 上級本

解きたい問題は 4 章・ 7 章で、解くべき問題は 5 章・ 8 章・ 9 章です。毎日 1 章は無理だな……

• 1. 2 分探索
  平均最大化、 n 番目に大きい平均値などはやっておくと良さそうです。中央値の問題は難し過ぎたので出ない気も。
• 2. 動的計画法
  ほぼ EDPC, TDPC の解説です。 PAST 過去問はあまり載っていませんでした。 PAST の出題傾向的にあまり解かなくて良い気がしています。 EDPC をわりと解いているしヨシ！
• 3. 頻出テクニック
  出そう。列挙で TLE したら参照します。考察激ムズ問題は解けなくて良い気もします。
• 4. 頻出アルゴリズム・データ構造
  Union-Find と LCA. 出てきたら美味しいですね。解いておきたい。
• 5. ネットワークフロー
  二部マッチングとか最小費用流とか、ど典型が出題されるけど解けないやつ！　一番やるべき章ですね。後はやる気が……
• 6. セグメント木
  遅延セグ木を実装しましたが、 これ過去問では出てないですね？ 13 回 PAST O に出てる……
• 7. セグメント木 + DP
• 8. 平面走査 [エキスパート編]
  何も分からない。優先度は低めかも。
• 9. 難問にチャレンジ！ [エキスパート編]
  見てません。既知の手法の組み合わせ？

競プロには意外と『コツ』が存在する

過去の自分 (伸び悩む競プロ初心者) には、案外『じゃあまず 100 問解いて！』以外のアドバイスがあり得る気がします。たとえば今の僕が知っているコツとしては:

コツは派生して多くの知識や解法に繋がります。逆に『コツ』を掴めていない分野を列挙すると、狭く具体的になりがちです。コツを掴みたいですね……！

競プロに限らず、たとえば Haskell においても『1 つの式の中にすべての文脈が載っているため理解しやすい』などの発見はあったはずですが、『コツ』言えるほど強力になることはまずありません。結局『じゃあまず 100 問解いて！』が最適なのかもしれません。

まず 100 問解くためのコツってありますか……？ (血眼) 習慣にはニワトリと卵問題がッ

また 1 つ手続き型プログラミングが上手くなってしまった

※ ただし Haskell に限る

具体例

一周回って 呼吸するように Haskell で手続きが書ける ようになってしまいました。喜んでいいんでしょうかw

今回は PAST #14: L で手続き型ループを書きました。

main :: IO ()
main = do
  [nVerts, nEdges] <- ints

  !outDegs <- VUM.replicate nVerts (0 :: Int)

  -- 1. do ブロックの中でやりたい放題:
  !edges <- replicateM nEdges $ do
    (!v1, !v2) <- both pred <$> ints2
    VUM.modify outDegs succ v2
    return (v1, v2)

  -- 2. `traceShow` でデバッグ出力:
  let !_ = dbg ("edges", edges)

  let !graph = accumArray @Array (flip (:)) [] (0, pred nVerts) edges

  -- 3. 気分はモナディック版 `until`:
  !result <- do
    !heap0 <- H.fromList <$> filterM (fmap (== 0) . VUM.read outDegs) [0 .. pred nVerts]
    let !_ = dbg ("heap", heap0)

    -- 4. `fix` 関数で再帰関数の定義・実行を同時に行う
    -- 5. `fmap` により `IO` モナドの中身をポイントフリースタイルで操作
    fmap (reverse . fst) . flip fix ([], heap0) $ \loop (!acc, heap) -> case H.uncons heap of
      Nothing -> return (acc, heap)
      Just (!v, !heap') -> do
        let !vs = graph ! v

        let !_ = dbg (v, vs)
        -- 6. `foldForM` で低インデントを保つ
        -- 7. `<=<` 演算子でモナディック関数合成
        loop <=< fmap (v : acc,) . foldForM heap' vs $ \heap'' v2 -> do
          VUM.modify outDegs pred v2
          !n <- VUM.read outDegs v2
          let !_ = dbg ("count", v2, n)
          return $
            if n == 0
              then H.insert v2 heap''
              else heap''

  putStrLn . unwords . map (show . succ) $ result

使用したテクニック

1. do ブロックの中でやりたい放題
   辺の入力をパースしながら、次数のカウンタ (MVector) を書き換えています。

2. traceShow でデバッグ出力
   スニペット定義して print 文のように traceShow を使っています。

3. 気分はモナディック版 until
until :: (a -> Bool) -> (a -> a) -> a -> a のうち、ステップ (a -> a) と初期値 a をモナディックにしたい！　この場合、 do ブロックの中で初期値を作り、再帰関数でループしてしまいます。

4. fix 関数で再帰関数の定義・実行を同時に行う
   ループをシュッと書く常套手段です。なぜこうなるのか知りませんが、不動点コンビネータ凄い。

5. fmap により IO モナドの中身をポイントフリースタイルで操作
   (\x -> f <$> g x) は (f <$>) . g または fmap f . g と書いてポイントフリーにできます。

6. foldForM で低インデントを保つ
   foldForM a b f = foldM f a b としています。関数部分を最後の引数にしたおかげで、インデントの数を減らすことが出来ています。

7. <=< 演算子でモナディック関数合成
   f >>= g と g <=< f は等価です。とりわけ f が長い場合は、 g <=< f と書くと端的な表現になります。

それ Haskell を使っている意味あります？？？

だ、だって、ポイントフリースタイルで関数合成する喜びは他の言語で味わえないから……！

それ他の Haskller が読めます？

無理かも……

AC 503 ボルト

記念用・観賞用です。

とか言って見返したことは無いですね……

AHC 020 に参加してみた

AHC 初参加で水パフォ取れました。やったー！

ヒューリスティック・コンテストに関して

AHC 020 は初心者を意識したコンテストだったらしく、かなり ABC に寄せられています。制約は以下でした:

• 制限時間は 4 時間 (15:00 ~ 19:00 の開催)
• 提出のペナルティ無し、提出間隔は 5 分以上

使用したアルゴリズムは最小全域木と 2 分探索です。途中からスコアが頭打ちになり、 ABC とは違った壁を感じました。もう打つ手が無いぞ！

使用言語に関して

今回も AtCoder ガチ言語 Haskell で参加しました。 Tier 3 までの言語なら、大きな差は出ないように思いました。特にランダム性無しで解を求める際は時間制限を持て余す程です。

Common Lisp でも問題無く参加できそうですが、新たな病気に罹患するまでは Haskell 続投かなぁと思います。

今後

公式解説放送 を観たりサンダー本を読んだりしようと思います。今回は焼きなましだったらしいですが、適用方法が見えません。勉強します。

ABC をやらなければ一生 2 分探索しなかったでしょうし、 AHC をやらなければ一生焼きなめししないでしょう。雰囲気が分かる程度まではやってみようかと思います。

木 DP 再び (典型 90 問)

部分技の畳み込み方法 (a -> [b] -> a vs foldl' + s -> a -> a)

典型 073 の 公式解説 において、部分木の畳み込みが a -> [b] -> a の観点で述べられていました。これは containers の foldTree に 相当します (foldTree を使った人の提出) 。この考え方は難しいよ……！

ステップ処理の s -> a -> a で入力 (子要素) を 1 つずつ畳み込む形、いつものナップサック DP のように考えると簡単になりました。言語化が辛いので、ここに blender の図を貼りましょう。

これは Blender の図、の図……

Unbox の実装に関して

タプルの newtype を使うと、 derivingUnbox が簡単になる気がしました:

newtype Op = Op (Int, Int)
  deriving (Show, Eq)

-- タプルの中のデータ数が増えても、 `derivingUnbox` の書き方は同じ:
derivingUnbox "Op" [t|Op -> (Int, Int)|] [|\(Op !x) -> x|] [|\x -> Op x|]

タプルの操作も便利なことが多く、フィールドを持つよりも良さげな感が……

全方位木 DP 再び

foldTree と foldTreeAll のシグネチャを見直し、 典型 039 を再び AC しました (提出) 。

もう 10 回目を超えているのでサクッといけました。

newtype Acc = Acc (Int, Int)
  deriving (Show, Eq)
 
derivingUnbox "Acc" [t|Acc -> (Int, Int)|] [|\(Acc !x) -> x|] [|\x -> Acc x|]
 
newtype Op = Op (Int, Int)
  deriving (Show, Eq)
 
derivingUnbox "Op" [t|Op -> (Int, Int)|] [|\(Op !x) -> x|] [|\x -> Op x|]
 
instance Semigroup Op where
  (Op n1) <> (Op n2) = Op $ add2 n1 n2
 
instance Monoid Op where
  mempty = Op (0, 0)
 
instance SemigroupAction Op Acc where
  sact (Op (!n1, !d1)) (Acc (!n2, !d2)) = Acc (n1 + n2, n1 + d1 + d2)
 
instance MonoidAction Op Acc
 
main :: IO ()
main = do
  [nVerts] <- ints
  !edges <- replicateM (pred nVerts) (both pred <$> ints2)
 
  let !tree = accumArray @Array (flip (:)) [] (0, pred nVerts) $ concatMap2 (second swap . dupe) edges
  let !results = foldTreeAll tree (const (Acc (1, 0))) (\(Acc nd) -> Op nd)
 
  print $ (`div` 2) . VU.sum $ VU.map (\(Acc nd) -> snd nd) results

考察で全方位木 DP を引っ張り出してくるのが難しいなと思います。木において O(N) で答えを出そうと思えば、パタンマッチで全方位木 DP になるのですが、毎回自分の頭で解き方を考えるのが高難度帯では効いてくるそうで、難しいです。考えるってパタンマッチじゃないんですよね……？

参考になった色変記事

巷の入水記事では、よく『(狭めの範囲) を勉強したら入水できました！』となっています。それがいかに凄いか身にしみて理解していますが、自分の参考にはならないのです……！

逆にどういう記事が参考になったかメモしておきます。

どの記事も面白い (から読んでいる) のですが、参考になるかは別の尺度ですよね。

ピックアップ

• 【競プロ】新人SEがAtCoderを始めて水色になった【色変記事】
  プレゼンが上手いです。まずタイトルが目立ちますし、中身を見れば隙きの無い実力を得たことが伺えます。 全部解けるようになれってことか……！
  モチベーション面 で参考になっています。半年で水色、 1 年で青 というリアルタイム性が刺激的です。 Twitter も面白いし何もかも凄い。

• AtCoder黄色を目指してやってきたこと
  色辺記事にしては珍しく、主に 考察やライブラリ整備 に関して言及されています。マメに考えて自分に適用できると役に立ちそうです。
  この方は解くのが遅いと言っていますが、 ABC で並走する限り、青色コーダーよりちょっと速いぐらいのスピードです。つまり僕からすれば爆速なのです。ギョギョーッ

• RubyとCrystalでAtCoder青色になりました
  ライブラリ整備の具体例として、累積和が挙げられていました。 csum.sum(l..r) のようにアクセスするようです。僕は毎回図を書いて添字を考えていますが、その (認知的) 負荷が無くなる ということですね。上 ↑ の記事はこういう発見の重要性を伝えていたのかと非常に参考になりました。

感想

コツを見つけるのがコツだ！？　そんな記事たちが刺激的でした。その他の記事も楽しく拝見しております。色辺記事を書いてくれた人の SNS は (忘れていなければ) 大体フォローしちゃう

cojna/iota メモ

美麗…… d(•, •)

完璧過ぎて、自分でライブラリを書く意味が無い気さえしてきます！

読みました

Data.Buffer

長さ n or 2n のMVector のバッファと、その使用領域を表す [front, back) を持っています ([front, back) は長さ 2 の MVector で持っています) 。

バッファは stack / queue / dequeue として利用できます。ただしリングバッファではないため、 キューとして使用する場合は (たとえ popFront しても) n 回までしか pushBack できないはずです。

生の vector では pushBack できないため、 pushBack できるだけでも相当ありがたかったりします。 Seq をキューとして使うのも中々つらいし……

基本すべてのスロットが使い捨てであり、 push の最大回数を見積もって使うのが良さそうです。競プロ的ですね。

Data.Prelude

• vector の stream 部分で爆速イテレーション
• binarySearch .. = runIdentity $ binarySearchM ..
• ByteStringBuilder 関連
  • なお ByteStringBuilder は Unbox ではないため、 a -> ByteStringBuilder を受け取って Vector a を直接 fold します (map を挟みません) 。
• 基数ソート関連？ (使い所は？　速い？)

app/Main.hs

haskell-src-exts で関数定義を取り出して、 Main.hs に appendFile する運用のようです。 AST を文字列に変換する際、それぞれの関数を 1 行に minify しています。

#define MOD のようなマクロ定義はパース前に取り除きます。ファイルごとに #define があるため重複するのと、マクロを消さないと Haskell としてパースできないようです (たぶん) 。

Data.Graph.Sparse

SparseGraph w は CSR 形式 (隣接リストを 1 つの配列で済ませる形) のグラフです。重み付きグラフや木も同じデータ型で持つようです。

• 重さを別の Vector で持ち、 adj と adjW を両方提供する
• Builer を切り出す
• RecordWildCard 言語拡張で destructuring ができる
• 添字は 1 次元限定
  2 次元グリッドなどで SparseGraph を使う場合は、手動で次元を変換しているようです。ここは盆栽の余地ありですね。

読みたいです

• Data.Doubling
  鉄則本とは少し違う？

• Data.BitSet
  # の嵐

分かりません

• Data.PrimParser
  モナディックパーサっぽいですが……？　runSolver と組み合わせると、とにかく main がカッコいいです。羨ましい。

いつか Haskeller に聞きたいこと

溜まったら特攻して聞きに行きます。

1. ソースのバンドリングの方法
   cargo-equip 相当のツールを持っている？　(つまりライブラリのソースをマージして Main.hs を生成している？)　この際に minify したり IL(..) を自動で付けている？

2. 可変長 vector
   標準的なライブラリが無いと思うが、自作している？

3. 1 次元 vector への多次元 view
   これはソースを読めば分かるはずですが、どれだったかな……？

4. 考えています……

Main.hs の bundler を作る (1): 構想

自作ライブラリ (stack/cabal プロジェクト) からファイルを選び、適宜 Main.hs に合成できるようにします。要は cargo-equip の Haskell 版、自分専用の cojna/iota/app/Main.hs を作ります。 ~200 行くらいの軽いコードになるはずです。

動機

HLS を動かしたいです。大きなソースで Template Haskell を使うと HLS が動かなくなり (泣), 変数の一括リネーム等が不可能になります。必要なコードのみ Main.hs に取り込む形にすれば、 HLS も動くようになるはずです。

先駆者の動き

運用方法 (想像)

1. My.Prelude のみをバンドリングした Main.hs をテンプレートとします。
2. 随時 iota Data.Algorithm.BinarySearch a/Main.hs のようにライブラリを追加していきます。

ソース構成

先駆者の Main.hs は以下の並びです:

1. 言語拡張
2. Import
3. main 関数
4. 合成されたライブラリのコード

実装

言語拡張・ Import は、テンプレート内ですべて列挙すれば良いです。ライブラリ中のファイルを Main.hs に合成する際は、言語拡張・ Import を取り除いた上で Main.hs の末尾に追記できれば良いです。

haskell-src-exts を使うと、 Haskell のソースファイルの AST が得られます。これで関数やデータ型の宣言のみを print したり、コードの prettify/minify をするようです。

追加でやりたいこと

ライブラリ部分を 1 行に minify する

なんかできそうなんですよね……。 AST を 1 行に minify したやつを ; で繋げて行きます。これでいいんじゃないかという気がしてきました。

f :: Int -> Int ; f a = a + 3 ; g :: Int -> Int ; g x = x + 4 ;

Main.hs をブロック分けしてソートする

Main.hs のパーツごとにヘッダを作り、パーツの順番を操りたいと思います。

• main 関数をファイル末尾へ持っていく

  • 僕含む Vimium ユーザが、 G 一発で main を発見できるのがメリットです。
  • Main.hs が壊れている (パースに失敗する) 場合も動作して欲しいと思います。
    やはり AST ではなくテキストとしてパーツをパースするのが良さそうです。

• 取り込まれたライブラリをアルファベット順でソートする

  • たとえば MyLib.Algorithm.BinarySearch は MyLib.Prelude よりも先に来るようにします。

CLI

• テンプレート (全言語拡張・Import + Prelude) の自動生成
  • 全言語拡張・ Import は、ライブラリファイルの AST から抜き出したものの和です。
• ファジーファインダで合成するファイルを選ぶ

やらない (けどやりたい) こと

依存関係の自動解決

• A が B に依存している場合、 A の合成時に B も自動で読み込む
• もしくは合成ファイルのセットをファジーファインダから選ぶ

提出コードを最小化する

• ソース提出前に、未使用のコード (関数・ Import) を削除する
  • AST 上で未使用コードを探るツールが無いか
  • cabal をライブラリとして使う
  • cabal (CLI) のエラー出力を使う
    cabal のエラー出力から未使用関数名を取り出す → AST から関数を削除する → cabal のエラー出力から未使用 Import を取り出す → 未使用 Import を削除する？

Bundling 化を意識させない

• 自作ライブラリを直接 Import 可能とする
  Main.hs の中で import MyLib.Algorithm.BinarySearch と書いたら、提出時に自動で展開されます。もちろん Main.hs の編集中は、自作ライブラリのコードにジャンプしたりできます。

Unrated 対策下で常設コンにおける Haskell の提出を読むには

提出が多すぎて、クエリ処理が終わらないっぽいですね……！

• 👍: ユーザで絞り込む (mod_poppo 氏！)
• 👎: 言語で絞り込む (遅過ぎて弾かれる)

CSR 形式のグラフ

隣接リスト形式のグラフにおいて、すべての辺を 1 本の配列に納める方法に名前が付いています。 cojna/iota の Data.Graph.Sparse はこれですか。上手い！

https://qiita.com/AkariLuminous/items/31faea745b5dd4fb9edc

Haskell 同人誌が読みたい

妄想です。

勝手にこういう画像作っちゃダメですね……

ドリームキャストはともかく、実際 Haskell で茶色コーダーになるための本があればいいなと思います。ループ処理やリストで FIFO など、『当たり前』だけれど経験値の溜まりにくい部分を、スラスラ読み流すだけで補える本があれば……！

グラフ典型メモ

やはりグラフが難しい。。水 diff まではパタンマッチで解けると思いたいです。

• 無向グラフの閉路収集 (ABC266 F など)
  すべての頂点の次数を数える。次数 1 の頂点から順次取り除く。新たに次数 1 の頂点ができた際はキューに入れていく。残った頂点が閉路上の頂点である。

• すべての盤面を頂点としたグラフを考える (ABC 224 D など)
  初期の盤面から最終の盤面までを BFS するなどして解く。盤面の遷移は Vertex -> [Vetex] と捉え、動的に構築して良い。特に盤面の数が多い時には、遷移可能な盤面のみがメモリに載って良い。

• 超頂点を経由して遷移の本数を減らす (どれだっけ)
  特に全頂点間に辺が張られている場合、辺の数が N (N - 1) から N になって大幅に計算量が下がる。

• 考察により負の辺を除去して Dijkstra (ABC 237 E)
  ダブルカウントの成分を辺の重みとする。その他はオフセットの差で求まる。

• UnionFind 巻き戻しもどき (ABC 264 E, PAST のどれか)
  クエリを後ろから処理する／毎回 Union-Find を作り直すなど。

• 探索状態の数だけグラフを複製する。グラフからグラフへの有向辺で状態遷移を表す。
  社長のツイート: https://twitter.com/chokudai/status/1551834978748489728

• 01-BFS (典型 90 など)
  コスト 0 の遷移先が N 個ある場合、コスト 0 の遷移を N 回繰り返すと捉える。ただし探索時に状態を加味する。たとえばグリッドの場合、位置 * 方向を探索する空間とする。遷移先を集める際は、 Seq の前後に順次挿入する。遷移は Vertex -> [Vetex] と捉え、動的に構築して良い。

• 全方位木 DP (典型 90 など)
  全頂点間の計算を O(N) で実施する。木の畳み込みが有効な場合のみ有効。

• 徐々にネットワークを広げる (ABC 214 D)
  全頂点間の計算を O(N) で実施する。経由する 1 辺のみが結果を決める場合に有効……、、、

• LCA

レーティング 4 桁！

っしゃらい！

包除原理 レベル 1

忘れそうなのでメモしておきます。

包除原理とは

すべての積集合を元に和集合を求めるやつらしいです。 tsutaji さんのスライド の『初級』の部分を参考にしています。

包除原理の使い方

\{\mathbb{k} \}_{\mathbb{k}} を \{ n \le N \} \cap \mathbb {N} の空ではないすべての真部分集合の集合として ^[1] ……

• |\mathbb {k}| が奇数なら -, 偶数なら +
• \mathbb k のイテレーション方法
  • ビット全探索
  • |\mathbb k| 毎にイテレートして、対称性を元に {}_N C_{|\mathbb k|} をかける

問題

• ABC 304 F
  AtCoder ABC304-F Shift Table を 2 通りの方法で解く の方針 1 は DP で普通に解けます。方針 2 の包除に帰結するやつは考察が無理だ……！

2D MVector, 爆速……！

ABC 307 C で Arrray を MVector に変えるだけで 763 ms の解答が 134 ms になりました。なんか知らんけどいいぞ……！

Data.Ix が遅いとか vector のストリームが速いとか？

2D MVectorへの view

MVector を slice すると 2D vector のように扱うことができます (元ネタ)。基本はこんな感じで行こうと思います。

-- | Creates a 2D view to a mutable vector.
{-# INLINE view2dVGM #-}
view2dVGM :: (VGM.MVector v a) => (Int, Int) -> v s a -> V.Vector (v s a)
view2dVGM (!h, !w) !vec = V.generate h (\i -> VGM.slice (w * i) w vec)

{-# INLINE read2d #-}
read2d :: (PrimMonad m, VGM.MVector v a) => V.Vector (v (PrimState m) a) -> (Int, Int) -> m a
read2d !vec (!y, !x) = VGM.read (vec V.! y) x

{-# INLINE write2d #-}
write2d :: (PrimMonad m, VGM.MVector v a) => V.Vector (v (PrimState m) a) -> (Int, Int) -> a -> m ()
write2d !vec (!y, !x) = VGM.write (vec V.! y) x

TODO: haddock test を書く、ここに貼る

AHC 021

親方、ビジュアライザから Arch Linux が！

https://archlinux.org/

隣接行列 と行列累乗

概要

正方行列 A_{i,j} で有向グラフを表す (頂点 i から j へ辺が張られていれば 1, 張られていなければ 0 とする) 。 (A^k)_{i,j} は頂点 i から頂点 j への長さ k の経路の数を表す。

本当は walk の数らしい？　重さも載りそう

• 対角成分は自己ループを表すため注意 (大抵 0 のはず)
• 累乗計算はダブリングすると高速化できる

行列累乗 (mod) の計算方法

Array

mod_poppo 氏の提出 からパクりました。ただしaccumArray よりも listArray の方が速いです。

MVector

TODO

massive

TODO

対角化

TODO

問題

• EDPC R - Walk
  頂点数 50 遷移回数 10^{18}
• ABC 212 E
  頂点数 5000 でダブリングすると TLE になりました。 N^3 くらいかかりそうだし。思案中…… → 参りました、、！

EDPC / TDPC の難度

EDPC をある程度やると、水 diff DP がサクっと解けることもあります。グラフの EDPC 、転倒数の EDPC というような高難度問題セットがあれば、同じように高山トレーニングできて良さそうですが。

https://twitter.com/kyopro_friends/status/1674365327285833728

案外黄 diff 過去問を解くのがレーティング向上の最短ルートだったりして……？　そんなことを考えながらも、本日も解説 AC をキメて行きます。

どうしたことだ、この Haskell の提出の数は……！

増えているッ……！　提出の種類が、圧倒的にッ…………！！

Twitter が見れない時も、 Zenn が Twitter なので平常運転だったりします。コミュニティガイドライン的にはよろしくないですが……

内部レーティング

AtCoder のレーティング計算式には『リセマラ補正』がかかっているそうです。

レート（第三段階）=レート（第二段階）−リセマラ対策補正

https://qiita.com/anqooqie/items/92005e337a0d2569bdbd#性質3-リセマラ対策

Type Checker で補正前のレーティングを確認できます。参加回数さえ増やせばとっくに色変してるじゃないか！　という場合もあるようです。早々と色変する人は、 1 色上の実力を持っているかもしれません。

https://atcoder-type-checker.herokuapp.com/

Stan (Haskell static analyzer)

久しぶりに Mac を開くと、 HLS から謎の lint が:

これは stan による提案 STAN-0210 のようです。

古い GHC では forM_ が遅くなりがち

改善方法としては、モナディックループには loop を使えとあります。いや〜使いにくい。

当面は cojna/iota の stream (vector パッケージの monadic stream) 相当の関数を使います。 関連の Issue は既に閉じており、最近の GHC では改善が期待できそうです。

Data.Ix.range に対する forM_ の高速化

Data.Ix と vector ベースのグラフ実装のため、 range をイテレータで高速化したいと思います。まずは Data.Ix のソースコードを見てみます。

instance  Ix Int  where
    {-# INLINE range #-}
        -- The INLINE stops the build in the RHS from getting inlined,
        -- so that callers can fuse with the result of range
    range (m,n) = [m..n]

    {-# INLINE unsafeIndex #-}
    unsafeIndex (m,_n) i = i - m

    index b i | inRange b i =  unsafeIndex b i
              | otherwise   =  indexError b i "Int"

    {-# INLINE inRange #-}
    inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n

instance (Ix a, Ix b) => Ix (a, b) where -- as derived
    {-# SPECIALISE instance Ix (Int,Int) #-}

    {-# INLINE range #-}
    range ((l1,l2),(u1,u2)) =
      [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]

    {-# INLINE unsafeIndex #-}
    unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
      unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2

    {-# INLINE inRange #-}
    inRange ((l1,l2),(u1,u2)) (i1,i2) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2

    -- Default method for inde

instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
    {-# SPECIALISE instance Ix (Int,Int,Int) #-}

    range ((l1,l2,l3),(u1,u2,u3)) =
        [(i1,i2,i3) | i1 <- range (l1,u1),
                      i2 <- range (l2,u2),
                      i3 <- range (l3,u3)]

    unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
      unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
      unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
      unsafeIndex (l1,u1) i1))

    inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
      inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
      inRange (l3,u3) i3

    -- Default method for index

リストの範囲構文やリスト内包表記を使った素直な実装でした。これらに替わりの手動でイテレータを実装していきます。

WIP

高速化関係

Libary Checker (Yosupo Judge)

AtCoder Library Practice Contest の強いやつという感じです。これはいつか制覇してみたいですね。記事のネタにもなりそうですし。ジャッジの仕組みも気になります。

• Dockerfile.HASKELL
• GHC による提出一覧
• Library Checker を支える技術

なんとサイト自体に AC 表示機能がある。できれば最速 AC 時間と自分の AC 時間も表示してほしい。

online-judge-tools/verification-helper

oj-verify は Library Checker と Aizu Online Judge の問題をローカルや CI でジャッジするためのツールのようです。実は AtCoder の問題もジャッジできるようで、なんちゃってベンチマークに使ってみたいと思います。

{- verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
 -}
-- ファイル冒頭のコメントで問題を指定できるっぽい

• Online Judge Verification Helper の細かい仕様
• 競プロライブラリに自動で verify をしてくれる CI を簡単に設定できる Web ページ
• HelloWorld.Test.sh

ACLにおける定数倍高速化

こたつがめ先生のスライドです。面白い内容がいっぱい。特にグラフを CSR 形式 で持つやつは最近僕も取り組んでいます。

• その他勉強会のスライド (Twitter)

array モドキの n 次元 vector

cojna/iota の SparseGraph w は見通しが良いです。辺に重みがある場合、無い場合も同じデータ型を使用できます。アクセサが複数あり、重みが不要なら gr `adj` v, 重みが必要なら gr `adjW` v を使います。

作りたいもの

添字を Ix に拡張した SparseGraph i w を作ろうと思います。 内部的には、頂点は Int 型になるため常に Vector を使えば良いです 。ただしユーザ側の API では Ix 型を使いたいです。そのため Ix, Int 間の相互変換を提供する Unindex 型クラス、 array より高速な array モドキとして IxVector, IxMVector 型を作ろうと思います。

以前の投稿

• MVector をスライスして添字アクセスを n 回行う
  2 次元用、 3 次元用のコードが分かれて良くない気がしました。
• forM_ (range ..) の高速化 (WIP)
  少なくとも古い GHC では forM_ の最適化が働きにくいため、 vector パッケージの monadic stream に置き換えます。 WIP

Unindex

index の逆操作があると、 i, Int の相互変換ができてグラフの API に良さそうです。実装は適当、制約は強めでいいかな……:

class (Ix i, VU.Unbox i) => Unindex i where
  -- TODO: Fusing
  -- https://wiki.haskell.org/GHC/Using_rules
  unindex :: (i, i) -> Int -> i

instance Unindex Int where
  unindex _ !v = v

instance Unindex (Int, Int) where
  unindex ((!y0, !x0), (!y1, !x1)) !yx =
    let !w = x1 - x0
     in yx `quotRem` w

instance Unindex (Int, Int, Int) where
  unindex ((!z0, !y0, !x0), (!z1, !y1, !x1)) !zyx =
    let !d = z1 - z0
        !h = y1 - y0
        !w = x1 - x0
        (!z, !yx) = zyx `quotRem` (h * w)
        (!y, !x) = yx `quotRem` w
     in (z, y, x)

途中、 UnIndex から Unindex に変更しました (LSP が死んでいるため手動で):

$ rg UnIndex -l | xargs -I{} sed -i 's;UnIndex;Unindex;g' '{}'

IxVector

Vector / MVector に添字範囲 (i, i) を付けるだけ。案外これで十分そうです:

-- | N-dimensional @Vector@ or @MVector@ with `Data.Ix`.
data IxVector i v = IxVector {boundsIV :: !(i, i), vecIV :: !v}

(.!) :: (Ix i, VG.Vector v a) => IxVector i (v a) -> i -> a
(.!) IxVector {..} i = vecIV VG.! (index boundsIV i)

-- | Reads a value from `IxVector`.
{-# INLINE readIV #-}
readIV :: (Ix i, PrimMonad m, VGM.MVector v a) => IxVector i (v (PrimState m) a) -> i -> m a
readIV IxVector {..} i = VGM.read vecIV (index boundsIV i)

-- | Writes a value to `IxVector`.
{-# INLINE writeIV #-}
writeIV :: (Ix i, PrimMonad m, VGM.MVector v a) => IxVector i (v (PrimState m) a) -> i -> a -> m ()
writeIV IxVector {..} i a = VGM.write vecIV (index boundsIV i) a

{-# INLINE modifyIV #-}
modifyIV :: (Ix i, PrimMonad m, VGM.MVector v a) => IxVector i (v (PrimState m) a) -> (a -> a) -> i -> m ()
modifyIV IxVector {..} !alter i = VGM.modify vecIV alter (index boundsIV i)

{-# INLINE swapIV #-}
swapIV :: (Ix i, PrimMonad m, VGM.MVector v a) => IxVector i (v (PrimState m) a) -> i -> i -> m ()
swapIV IxVector {..} !i1 !i2 = VGM.swap vecIV (index boundsIV i1) (index boundsIV i2)

Destructuring の構文 DataType {..} は {-# LANGUAGE RecordWildCards #-} による

動作未確認

ヒュ

一度でも焼きなまし (SA: Simulated Annealing) をやってみなければ……！　メモメモ

• Introduction to Heuristic Contest
• 鉄則本
• 直感でわかる、ヒューリスティック問題の羅針盤 ～貪欲法から山登り法まで～
• 競プロ始めました
  一度でもヒューリスティックに参加すると、ブログの内容が非常に楽しい

TODO: ガバベンチ

本をあたる

地道に全部調べるのが大事なんですね！ (あまりやっていない……)

• Algorith Design with Haskell 2 章
• Haskell High Performance Programming 3 章
• Haskell Optimization Handbook

ツールをあたる

• oj-verify
• hyperfine
• hspec
  • Haskellの単体テスト最前線
• QuickCheck
  • QuickCheckで競プロ用Haskellコードをデバッグする
  • 本物のプログラマはHaskellを使う 第17回　QuickCheckでデータ駆動型テストを行う
  • QuickChecking Patricia Trees
• criterion

ベンチマークを行う

• String vs ByteString
• N 回 print vs unlines
• N 回 print vs ByteStringBuilder

不採用: 無名関数経由で引数の順番を入れ替える

人の提出でこの手のコードを見ました。

foldM の場合

foldM の関数部分を複数行に渡って書きたい場合に便利です:

(\f -> foldM f s0 xs) $ \..

ただ $ の左辺がゴチャつきます。 foldM に関しては、特に foldForM s xs f = foldM f s xs を用意したのでそれを使っています。

fix の場合

fix 関数による再帰関数の定義・実行においても同様に、引数の順番を入れ替えて再帰関数を最後にできます:

(\f -> fix f (0 :: Int) undef start []) $ \loop !depth !parent !v1 !stack -> do

とはいえ flip fix (x1, x2, x3, x3) $ \loop (!x1, !x2, !x3, !x4) -> do .. と書いても大きくパフォーマンスに影響ありません。可読性を優先し、 flip fix を使っていこうかと思います。

Random

Modulus だと思っていたものが modulo でした……

10 \equiv 1 (\mathrm{mod} 3) において 3 は modulo らしいです。また 1 つ、悲しいコミットを積み重ねてしまいました。

ixmap の正体

ixmap は添字の写像を定義する？！:

ソース を見た限りは新しい配列が作られています:

ixmap :: (IArray a e, Ix i, Ix j) => (i,i) -> (i -> j) -> a j e -> a i e
ixmap (l,u) f arr =
    array (l,u) [(i, arr ! f i) | i <- range (l,u)]

しかし添字変換というのは、やりたいことの本質を突いていますね。 ixmap がその実現方法になるというのも凄い視点。。我田引水はいけませんが、人の盆栽は盗んでいこうと思います。

次に添字変換が必要になった時は、生の array を触る替わりに (Int, Int) -> Char を引数に取ることを考えてみます。実引数は (arr ! ) . f となり、 f によって添字をループさせたり回転させたり……

いや探索済み頂点の管理を考えると、新たに配列を作ったほうが安全そうです。

Prelude に古い部分がある (What I Wish I Knew When Learning Haskell)

日本語版を読んでいたら Data.List よりも Foldable や Traversable を使いなさいとあって愕然としました。僕の Haskell は、始めたときから obsolete だったかもしれません。確かにリストと vector で別名の関数を使わなくてもいいよね……。

自作関数を foldFor と foldForVG のようにバージョン分けしていたのも全く無意味……というわけではなく、 GHC 8.8.3 相当の vector には Foldable の実装がありませんでした。 Prelude の植え替えは、言語アップデート後に検討します。

f . runST $ do .. はなぜコンパイルできないのか

こうした事例 (playground) では謎のエラーが出ます。むしろ f $ runST $ do .. の方に特殊な推論が働いているようです。へー……。こういう知識を経験則として覚えてしまうため、言語オタクは名乗れません。プログラミング言語は難しいよ……！

https://stackoverflow.com/questions/9468963/runst-and-function-composition

ModInt に対する Enum 実装

Enum を実装すると succ, pred が使えるようになります。 (+ modInt 1) より succ と書きたいわけで便利です:

instance Enum IntMod where
  toEnum = intMod
  fromEnum = coerce

なんで preceding value が pred なのかと思いきや、 predecessor だったようです。 succ も succeding value じゃなくて successor だったのか……。英語音痴だったかもしれない。

キューが無い件

リストを引きずり回して cons していますが、書きにくい上に FILO になります。自然なコードになるようリスト関係のモナドを使う／作るとなると、いっそ ST モナドで可変 queue を使っても良い気がします。 mutable-containers や cojna/iota の Buffer の利用を真面目に検討して良さそうです。

• State モナドっぽい形 (Writer?) の利点
  引数からキューが消えます。 Haskell っぽいエレガントなコードになるかもしれません。弱点は、おそらくモナドの合成が必要になることです。 StateT を使いこなせる気がしない……

• ST モナドを使う利点
  push 操作の引数にキューを指定できて明示的なコードになります。無難ですね〜……。

n 次元 vector への考え

区切りが付きました。

グラフの頂点はフラットな 1 次元 Int で十分

• グラフの生成時に n 次元添字 i を 1 次元整数の頂点 Vertex に変換しておく
• DFS などの最中は常に Vertex にしか関心が無い
• ただし逃げ道として Int -> i という逆変換 (Unindex) も作っておくと土壇場で融通が効く

DP における n 次元配列はやはり必要

• これは n 次元添字越しのアクセスが頻発するため有効！
• STUArray を使っても IxVector (以前の投稿) を使ってもパフォーマンス上は大差無い

n 次元配列として使うべきデータ型とは (array vs IxVector)

• IxVector の方がイテレーションやスライスには強い
• IxVector にはタプルや ModInt を始めとしたユーザー定義型が乗る
• array を廃止した独自路線 (IxVector) で突き進んで良さそう

TODO: intsN

concat <$> replicateM n ints するよりも 1 回の unfoldr で済ませたい

• N 行読み取り (案外難しそう)
• 行ベースのパースを止めて、 Int ストリームから HW 個読み取る？
  • 1 本の vector に入れてスライスするとか

8 問体制の水 diff を埋めました

けっこう解きました。要求知識は意外と緑 diff の問題から変化ありませんでした。盆栽を止めて演習に専念したためか、レーティングも順調に上がっています。

しかしここから水パフォ後半を 4 連発しないといけないのはキツいです。 RPG においても、硬い敵が強いって相場が決まってますよ、、！

これでレーティングが上がらなければ、何をやったらいいのか分かりません。結果が出て欲しいな〜と思いつつ、 PAST 上級とか典型 90 問を埋めていこうと思います。

典型 90 問 ★ 4

埋めました。基本的な考察・実装を網羅した良問だらけで良かったです。僕の場合は、 01-BFS や整数問題が苦手であることがよく分かりました。

次々に AC できるのは最後の収穫の段階なので、それ以前のポテンシャルを高めるフェーズ、盆栽フェーズが重要だと感じました。 (外から観察する分には、解いた問題数から育てたポテンシャルも測れると思って良さそうです) 。

典型 90 問 ★ 5

埋めました。青 diff 級の問題も『水 diff です』という体で登場します。復習しないとですね。

DP 第一の類型: constructN

B - Frog 2 などは、畳込み (ナップサック問題など) よりも簡単な DP とされています。改めて解くと、 MVector ベースの解答となり苦戦しました。

このような『配列を左から埋める』 (もしくは配る) 類の DP は、 constructN を使うと簡潔に記述できます。 constructN の概要は、『配列の確定した部分を参照して新しい要素を作る』というもので、かつて諦めた遅延評価にも通ずる所があります。

mod_poppo 氏の解答

constructN の使い方

適当な具体例を載っけておきます:

*Main> :{
*Main| -- 長さ 6 の配列を生成する
*Main| VU.constructN 6 $ \vec ->
*Main|   if VG.null vec
*Main|     -- 最初の要素は 1 とする
*Main|     then (1 :: Int)
*Main|     -- 次の要素 = 以前の要素の和 とする
*Main|     else VG.sum vec
*Main| :}
[1,1,2,4,8,16]

フィボナッチ数列とかも作れそうですね。オーバーキルか。。

constructN の実装

内部実装 は完全に MVector です。配列中の値が確定した範囲を都度 unsafeFreeze して高階関数 f に渡しているだけ。それでも遅延評価無しで純粋関数によって解答を記述できるのはイカしています。

constructN !n f = runST (
  do
    v  <- M.new n
    v' <- unsafeFreeze v
    fill v' 0
  )
  where
    fill :: forall s. v a -> Int -> ST s (v a)
    fill !v i | i < n = let x = f (unsafeTake i v)
                        in elemseq v x $ do
                          v'  <- unsafeThaw v
                          M.unsafeWrite v' i x
                          v'' <- unsafeFreeze v'
                          fill v'' (i+1)
    fill v _ = return v

表面上 immutable だと使い勝手が良い……もとい、配列本来の使い勝手が得られます。マッチポンプなのか悩ましい。。ただ生の配列を触ると未確定の値を読んでしまう危険もあるので、 constructN へ導く Haskell は礼賛されて良いと思います。

Haskell 由来のフレームワークが、鋭い洞察と盤石な解答を生み出す。やはり Haskell が俺たちを強くする……！　微積で高校物理を解くのと似た類の栄養を摂取できます。リロードタイムに息吹を感じる類の人は Haskell を使えば間違い無いですね。

mod_poppo 氏の提出に関して

EDPC の mod_poppo 氏は神懸っています。真っ直ぐな Haskell で最速の解答を連発、件の B 問題の提出 (48 ms) すらまったく抜ける気配がありません。常時このレベルだったのではないかと妄想し、ゾクゾクしています。シンプルに強い。こうなりたいものです。

vector をリストと同じように扱う

vector 関連の手札を増やします。 vector を使うだけでリストの 4 倍速い提出になることもありますから、行く行くは vector へ完全移行したいと思います。

concatMap

あります。

uncons

リストへのパタンマッチで入力処理のループを書くことが多いです:

f [] = 0
f (x:xs) = x + f xs

パタンマッチの替わりに uncons を使用できます:

f xs = case uncons xs of
  Nothing -> 0
  Just (!x, !xs') -> x + f xs'

vector 版の uncons を作ると、同じように入力処理ができます:

{-# INLINE unconsVG #-}
unconsVG :: VG.Vector v a => v a -> Maybe (a, v a)
unconsVG v =
  if VG.null v
    then Nothing
    else Just (VG.unsafeHead v, VG.unsafeTail v)

f xs = case uncons xs of
  Nothing -> 0
  Just (!x, !xs') -> x + f xs'

というか vector 13 にはあるな……

groupBy

vector-13.0 〜 groupBy があります。現在の AtCoder 環境にはありません。

-- | TODO: Remove on 2023 langauge update.
-- @since 0.13.0.1
{-# INLINE groupByVG #-}
groupByVG :: (VG.Vector v a) => (a -> a -> Bool) -> v a -> [v a]
groupByVG _ !v | VG.null v = []
groupByVG !f !v =
  let !h = VG.unsafeHead v
      !tl = VG.unsafeTail v
   in case VG.findIndex (not . f h) tl of
        Nothing -> [v]
        Just !n -> VG.unsafeTake (n + 1) v : groupByVG f (VG.unsafeDrop (n + 1) v)

-- | TODO: Remove on 2023 langauge update.
-- /O(n)/ Split a vector into a list of slices.
-- @since 0.13.0.1
{-# INLINE groupVG #-}
groupVG :: (VG.Vector v a, Eq a) => v a -> [v a]
groupVG = groupByVG (==)

*Main> groupVG $ VU.fromList [0, 0, 1, 1, 2, 3 :: Int]
[[0,0],[1,1],[2],[3]]

nubSort

sortUniq がありました。

スタック

スタックにはリストを使います。

正確評価しなければサンクが溜まるやつ

『スペースリーク』で調べると色々ヒットしますね。

https://qiita.com/ruicc/items/bfa659c2ef9e1f75f7e1

サンクが増えるのを防ぐため、蓄積値を引きずり回すというのも理解できるようになりました (逆に a + b + .. + recursiveFunctionCall の形だとサンクが貯まる) 。

でも複雑過ぎて認識できません……

TODO: 末尾最適化

まだ末尾最適化が分かりません。セグ木の非再帰実装とかは、 Haskell においても高速化に繋がるのでしょうか。

prescsan / postscan 系関数を理解した

T - Permutation | EDPC の図解を作ってみました。別解として、 prescan / postscan 系関数を使う場合を考えました。

計算方法

複数回画像を差し替えました

prescan/postscan には慣れません……。こんな感じで 26 枚描いて Zenn に投稿したいと思います。

プレゼンがすべて

E8 さんレベルでは無いにせよ、映え画像で埋め尽くしたいですね〜

試行回数の期待値 DP: メンタルモデルと計算式

期待値 DP の等式を理解したくて考えています。

まだまだ整理中です。 i \rightarrow j は 1 回の遷移ですが、 j \rightarrow T は状態 j から T まですべての経路の集約となっており、曖昧さが残ります。うーん

\sum_{j, \Rightarrow} で i から j を経由したすべての経路を列挙できることにしました。さらに \Rightarrow が j を始点にすることを明示すべきです。

たぶんこんな感じ。。定義に戻れば大体何とかなりますね。

J - Sushi も完全攻略できる投稿を目指していきます。

Convex Hull Trick

TODO: 起きたらこれを最後まで読む

https://hcpc-hokudai.github.io/archive/algorithm_convex_hull_trick_001.pdf

良過ぎる、、 Z - Frog 2 の解説も入っていて神過ぎます。。。ブログも凄いしライブラリも凄い。サークルの スライド一覧 もいいですね。

https://rsk0315.github.io/library-rs/nekolib/

僕の盆栽は凡才だったか……。見上げ過ぎると首が折れそうなので、まずは CHT のスライドを実装してみます。

FPS とは..

DP が謎の計算で解けるそうですが、何も分からない……！

https://qiita.com/gg_hatano/items/3591ddf267092c235a23

異常高速化

バッファリング、 mmap, 異常パース……！　底知れぬ強さがいいですね。

https://twitter.com/mizar_tech/status/1683766795403137025

constructN は単なる N 回の push_back だった

A - Frog 1 を Rust で提出してみました 。イテレータに .rev() があるのはズルいですね〜〜 (Haskell で迂闊に reverse すると、コピーが発生して O(N^2) になる気が)

ツイート

ABC 312 まで

• Haskellで解くAtCoder - The curse of λ
  真面目に書かれているだけにオチが面白い

• vector 13 の嬉しさとして認識できているもの

  • derivingVia で Unbox 実装
  • iscanl' など添字付きイテレーションの追加
  • Traversable, Foldable の実装 (mapAccumL が使える他、汎用的な関数が書けたり？)
  • uncons, groupBy の追加

• EDPC - O | 集合 DP も大体 constructN で解ける 、確かに！
  セマンティック？ 的には完全に constructN ですが、普通は手続き的に書いたほうが速いようです。リンク先では constructN 中の計算をストリーム処理に仕上げて爆速にしています。 Rust で書くとさらに速くなります。 Python を C++ で書き換えて高速化するなら、 Haskell を Rust で書き換えて高速化するのもありでしょう。

• ポイントフリー Haskell メモ — Avendia
  2 変数関数やタプルが出てきてもポイントフリースタイルを諦めない！　*** でタプルの各要素に関数適用できることが分かったため、 VU.filter (uncurry (&&) . ((testBit s) *** id)) を書くことができました。目指せ point-less style..

• filter ((&&) <$> inRange (bounds grid) <*> ((== '.') . (grid !))) とかは使用頻度が高く便利です。

• maxBound を番兵にするとオーバーフローする場合がある件
  少し小さめにするか、オーバーフローせず maxBound を返す wrapAdd 的な関数を使うか

• Vimium で解答へのリンクが AC だった
  Vimium もまた AC への意志を持つ

• AC までの時間には、考察の正確さ・バグのない実装の腕前・デバッグの速さも織り込まれる
  速さで順位とレーティングが変わるシステムは悪くなさそう。

ABC 313 まで

• 知能の限界が近いかも知れない
  レーティングが上がりません……!!

• 解説 AC し過ぎ
  何もしないよりはマシか、、、

• 考察と解答を別の日に分けるやつ
  これを再開してみるか……！

• 実力のみが足りない
  前回・前々回でレーティングが下がりましたが、出題的には解けても良い問題でした。流れは来ています。

• (w, h) -> ((0, 0), (h - 1, w - 1)) のような関数の名前を考えたい
  むしろ Index0 という型クラスを作ってみるか

• 水 diff 99 問
  次回青パフォを出せなければ検証は失敗に

• 負けたよ……

ABC 314

• 実はあるらしい。よっしゃ！、！！
• ネタ探し中

constructN が思っていたよりも強い気がする

constructN の正体は N 回の push_back なわけですが、 DP 配列がトポロジカルソートされている場合はこの関数で構築できます。また 1 次元の添字を n 次元にバラす関数 (unindex) を使えば、 n 次元配列も構築できる気がします。

たとえば 1 次元配列の Bit DP を書けるのはもちろん、 Sushi とか LCS (最長共通部分列) のような複雑な遷移が要求される問題も constructN で解けてしまうと思います。

VU.constructN (h * w) $ \vec ->
  let i = VU.length vec
      (!y, !x) = unindex ((0, 0), (h - 1, w - 1)) i
      vec' = IxVector ((0, 0), (h - 1, w - 1)) vec -- Index 越しにアクセスする Vector
   in -- ..

constructIx みたいな関数にまとめる……ほどでもないかな。

ナップサック問題も 2 次元テーブルを constructN することで、 1 点毎の遷移を記述した解答が作れます。ただし畳み込みにより行毎に遷移を考えた方が筋が良いとは思います。