競プロ盆栽 (Haskell 盆栽 2 → 入緑)
toyboot4e茶色目指して
レート 400 が遠い。。 鉄則本 や Haskell High Performance Programming を楽しみながらボチボチやります。
toyboot4eHaskell の気づきメモ
NPlusKPatterns は危ない
これは数値にマッチするパタンを (n + 1) のように書くことができる拡張です。 1-based index を 0-based index に変換するときなどに使用しました。しかし n が負の数になる時はエラーが発生します。
N + K パタンが危険な例
言語拡張を有効にして ghci を起動します:
$ ghci -XNPlusKPatterns
Prelude>
一見 N + K パタンは問題なく動きます:
Prelude> let x = 1
Prelude> let (n + 1) = x
Prelude> n
0
しかし n が負の数になるとエラーが発生します:
Prelude> let x = 0
Prelude> let (n + 1) = x
Prelude> n
*** Exception: <interactive>:2:5-15: Non-exhaustive patterns in n+1
このように罠がある以上、多少冗長でも let や where を書こうと思いました。 詳細 (未確認)
2 次元の可変配列には vector よりも array の方が向いているかもしれない
2 次元の不変配列には
V.Vector (VU.Vector Int)のようなものが利用できます。ダブルポインタの発生は懸念されますが、そこまでパフォーマンスに影響は出ません。また各行の長さが違っても良い点はメリットになる時もあります。
2 次元の mutable vector が欲しかったのですが、 VU.create が使えず困りました。 State thread の表現力は予想以上です。
Vector で 2 次元配列を扱うならば、 (1, 2) のような 2 次元の添字を 1 次元の添字に変換すれば良いと考えました。たとえばグリッドの横幅を w として、 index = x + y * w のような式が考えられます。
実は、このような添字の汎用的な表現が型クラス Ix であると気付くことができました。また array は Ix を中心としたパッケージであると理解できました。
2 次元配列の添字の使い方 (array / Ix)
たとえば row-major な行列のリストを array の中に保存するなら、 newListArray ((0, 0), ((h - 1, w - 1)) list で array を生成し、添字 (y, x) でアクセスします。添字を (row, column) と見れば、 2 次元の array は row-major な行列であるとも解釈できます。
添字 (a, b) と { x, y } の対応について
Ix を試してみます。 Ix や array は標準？に入っているため、特に ghci にオプションは要りません:
$ ghci
Prelude> import Data.Ix
Prelude Data.Ix>
Ix クラスの index 関数は、添字範囲
Prelude Data.Ix> index (0, 4) 2
2
Prelude Data.Ix> index (2, 6) 2
0
これが n 次元に拡張されており、 2 次元の添字も使用できます:
Prelude Data.Ix> index ((0, 0), (5, 5)) (0, 1)
1
Prelude Data.Ix> index ((0, 0), (5, 5)) (1, 0)
6
Prelude Data.Ix> index ((0, 0), (5, 5)) (5, 5)
36
注意すべきなのは、タプルの右端の値が 1 次元目を表すということです。 Row-major な行列の場合は、タプルの 2 番目の要素を column とし、生成時のサイズは (h, w) にする必要があります。
遅延評価で DP ができるらしい？
map f xs の引数順は関数合成で便利
F# ではパイプライン演算子？ が使用されますが、 Haskell では関数合成が好まれる気がします。 map のシグネチャにもそれは表れているなと改めて思いました。
toyboot4e漠然とした興味
手続き型 Haskell は汚くてしんどい、純粋な Haskell は思いつくのが難しい
いずれにせよ、 Haskell は読むのも書くのも難しいと思います。
モナドのランク？
失敗しないモナドや、箱より文脈に近いモナドなど、何らかの違いを感じます。 State なんかは値というよりも関数のモナドですし。
toyboot4eABC ノート
面白い問題が多いと気づいてきました。
-
ABC 274 D: (
IntMapを使って) 重複を消去すれば、計算量をO(2^N) -
ABC 275 C: ある種の全探索で十分でした。つらい。。
-
ABC 275 D: Sparse なメモを使います。 274 D の経験後なら解けるべきだった (死亡) 。
-
ABC 277 C: DFS, union-find + 座標圧縮 (からの全探索) 、 sparse な union-find などの解答があります。良問な気がします (死亡) 。
-
ABC 278 D: 配列のゼロクリアは
O(N) O(log N) O(N) O(1)
言語拡張TupleSectionsにより\x -> (x, 1)を(, 1)と略して書くことができます。 Vector をタプルにマップするときなどに使えますね。 -
ABC 278 E: 考察で計算量を減らすことができず死亡。。あとタプルの unboxed array は作ることはできないので気をつけます。 これを Haskell で実装するのに 6 時間もかかったよ…… 。これが AtCoder を 実装 > 考察 に変えるハックです。
toyboot4eその他ネタになりそうな話題
レートは実力の対数のようなものらしい？
喩えだとは思いますが、もしも水色 (レート 1,200) を目指すなら今 (レート 400 弱) より約 10 倍強くなる必要があります。うーむ (普通にやっていたら無理では……？) 。
1 問解くとレートが 1 上がるという説もあり、逆に実力とは……？
AtCoder Problems を問題一覧にすると良かった
AtCoder Problems (使い方) では、コンテストを跨いだ問題一覧が見れます。解答状況も見えて、たとえば 僕の場合はこちら 。いずれレコメンド機能やバーチャルコンテストも利用する時が来るかもしれません。
流石に鉄則本には対応していないようですね。自分でカウントします。
レートのシミュレータ で目標のパフォーマンスが分かる
これで目標設定が可能に……？ とはいえパフォーマンス値に勘が働きませんし、問題の色を見れば良い気はします。問題の色 = その色の参加者の 50% が解けた問題……だったはずなので、目標のレートより少し下の問題を安定して解ければ良いはずです。まず茶色を目指すなら、灰色後半の問題が解ければ良いはず？
言語サーバが動いていない気がするんだけど！
HLS 1.5.1 だからだと思っていたけれど、さすがにフォーマットしかできない言語サーバが 1.5.1 なんて高いバージョンのわけもないよね……
toyboot4eHLS が動いてなかった
言語サーバは重要です。エラー表示したり、 変数の型を表示したり 、コードアクションで型ノーテーションを補完したり……。あまりの有用性に涙が溢れます。
今まで言語サーバ無しで Haskell を書いていたのはある意味凄くないですか？ (泣)
原因
現在のファイル構成は以下です。この状態で Emacs を起動すると、 LSP のプロジェクトルートが abc-hs になっていました:
abc-hs
├── abc-277
└── abc-278
├── a
│ ├── Main.hs
│ └── test-cases
├── b
└── g
対処方法 (暫定)
abc-* 以下に .projectile ファイルを置きます (Emacs の場合) 。これで ahc-* が LSP の workspace フォルダになります。他のエディタの場合は……最悪 .git を作ります？
また abc-* 以下で package.yaml を作り、実行ファイルごとに executables を書いて gen-hie (implicit-hie) で hie.yaml を作ります (Stack を使っている場合) 。これ自動化できないの……？
何とかしたいこと
- プロジェクトごとに GHC や HLS のバージョンを設定したい
-
package.yamlで 1 つ 1 つ実行ファイルを列挙する手間を省きたい (自動生成できる？ cabal だったら楽だったりする？)
toyboot4e
interact を使った宣言的な解答
Haskell で鉄則本を解く Youtube が現れました。 第一問の解答 の時点で、目を見張るほど宣言的です。これはかっちょいい。
YouTubeのvideoIDが不正です
interact について
解答を引用します:
module Main where
main :: IO ()
main = interact (encode . solve . decode)
decode :: String -> [[Int]]
decode = map (map read . words) . lines
encode :: [[Int]] -> String
encode = unlines . map (unwords . map show)
solve :: [[Int]] -> [[Int]]
solve dds = case dds of
[n]:_ -> [[n * n]]
interact を使えば、純粋な関数で解答を作ることができます。強制的な ByteString 縛りにすれば練習にもなりそうです。
interact :: (String -> String) -> IO ()
interact :: (ByteString -> ByteString) -> IO ()
interact :: (Text -> Text) -> IO ()
……と思いきや？
入力が複雑な場合は 、 decode (あるいは parse) の返値はタプルになるのでしょうか。あるいは solve . decode を 1 つの関数にしてしまえば良いですね:
main :: IO ()
main = BS.interact solve
solve :: BS.ByteString -> BS.ByteString
solve = ..
solve の中でも IO を使いたいとなれば:
main :: IO ()
main = BS.interact solve
solve :: BS.ByteString -> IO BS.ByteString
solve = ..
おや、 main 関数を書くのと大差無いかもしれません。改行文字の連結も大変そうですし。うーむ
toyboot4e翻訳等も凄い人でした。いい時代だ〜
toyboot4edirenv で Haskell 環境切り替え
AtCoder では GHC 8.8.3 / HLS 1.5.1 を使いますが、他のプロジェクトでは最新の Haskell を使いたいものです。 cabal で環境を変えるというのがあるそうですが、アドベントカレンダーで記事が出るなら自分から調べに行くのもなぁと思います。
代わりに direnv でプロジェクト毎に環境変数が切り替わるようにすれば、 Haskell の環境を切り替えられるかも？
インストール
direnv 公式サイト通りインストールして、シェルのフックを設定します。
$ curl -sfL https://direnv.net/install.sh | bash
~/.bashrc:
if command -v "direnv" > /dev/null ; then
eval "$(direnv hook bash)"
fi
~/.config/fish/config.sh:
if command -sq direnv
direnv hook fish | source
end
バージョン切り替え
$ direnv edit .
$ direnv allow
PATH_add ~/.ghcup/ghc/9.2.4/bin
PATH_add ~/.ghcup/hls/1.8.0.0/bin
~/d/h/rogue-hs ❯❯❯ which ghc
/Users/tbm/.ghcup/ghc/9.2.4/bin/ghc
~/d/h/rogue-hs ❯❯❯ cd ../
direnv: unloading
~/d/hs ❯❯❯ which ghc
/Users/tbm/.ghcup/bin/ghc
direnv: loading ~/dev/hs/rogue-hs/.envrc
direnv: export ~PATH ~XPC_SERVICE_NAME
~/d/h/rogue-hs ❯❯❯ which ghc
/Users/tbm/.ghcup/ghc/9.2.4/bin/ghc
これで動いた？
ビルドが長いのでまた明日〜
30 分後
完璧に動きました。バージョンの異なる GHC を使った 2 つのプロジェクトで同時にエディタを立ち上げることができます。やったぜ。
stack や cabal は特に切り替える必要がありませんでした。色々やりたいことはあるので遊んでいきます。
toyboot4e
[印刷用問題文]
『問題』ページ下部のボタンをクリックして、 競プロ典型 90 問 や 競技プログラミングの鉄則 演習問題集 の PDF をゲット？！ iPad に入れておきます。
iPad よりも高いけれど Kindle Scribe が欲しい
典型 90 問の解答は Twitter にある他、 リポジトリ に画像がまとまっているのでこれも PDF にしました。プリンタがあれば印刷するのですが。
toyboot4e
State モナドが分かってきたぞ！
State モナドで mapAccumL
mapAccumL は状態を持ちながら map する関数です:
#!/usr/bin/env stack
import Control.Monad.State
import Data.List
main :: IO ()
main = do
print $ mapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
-- (6, [1,2,3])
この関数は Traversable なデータ型にしか実行できませんから、 Vector には実行できません。ただし Vector にも mapM は存在するので、 mapM と State モナドを使って mapAccumL と同等な計算を作れば Vector に対しても実行できます。
State モナドと do 記法を使って、なんとか mapAccumL を実装できました:
汚い実装
#!/usr/bin/env stack
import Control.Monad.State
import Data.List
import Data.Tuple
myMapAccumL :: (Int -> Int -> (Int, Int)) -> Int -> [Int] -> (Int, [Int])
myMapAccumL f s0 xs =
swap
$ runState
( mapM
( \x -> do
acc <- get
let (acc', x') = f acc x
put acc'
return x'
)
xs
)
s0
main :: IO ()
main = do
print $ mapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
-- (6, [1,2,3])
print $ myMapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
-- (6, [1,2,3])
これの無名関数の部分が Int -> State (s -> (Int, s)) という型であることを考えると、 mapM は各要素を State に写し、移された State の入出力を連結するものであることが分かり:
#!/usr/bin/env stack
import Control.Monad.State
import Data.List
main :: IO ()
main = do
print $ runState (mapM (\x -> state $ \acc -> (x, x + acc)) [1, 2, 3]) (0 :: Int)
-- ([1,2,3], 6)
これでたとえば累積和の計算ができます:
-- 数列 → 累積和
print $ runState (mapM (\x -> state $ \acc -> (x + acc, x + acc)) [1, 2, 3]) (0 :: Int)
-- ([1,3,6], 6)
-- 累積和 → 数列
print $ runState (mapM (\x -> state $ \last -> (x - last, x)) [1, 3, 6]) (0 :: Int)
-- ([1, 2, 3], 6)
-- evalState = fst . runState
Vector には mapAccumL を実行できませんが、 State モナドを使った mapAccumL は Vector 版の mapM を使って実行可能です。
必要だった知識・理解
-
Stateはs -> (a, s)の wrapper-
stateで純粋関数をStateにできる -
runStateでStateに実引数を与えられる
-
-
mapMの過程は[a] -> [m a] -> m [a]という変換のイメージで、sequence . mapという 2 段階に分けて考えると、それぞれの要素をStateモナドに写し、それらの入出力を繋ぎ合わせて全体で 1 つのStateモナドにするもの
なぜ混乱したのか
脳みそが弱いからとしか言いようが無い。。
-
do記法が記憶に焼き付いた -
Stateを単なる関数として考えることを忘れ、ブラックボックスとして扱おうとした - そもそも
fmapmapMが mod_poppo 氏のブログ記事 から与えられた発想であることを忘れ、その意味を考えていなかった
何とかコンパイルできるコードを作り、質問して state 関数を教えてもらったことが取っ掛かりになりました。誰も僕の脳みそをデバッグできない。。こういう馬鹿さはずば抜けている気がします。でも自力で脱出するように上手くリードしてもらえると、意外になんとかなりますね。
まあなんとかやっていきます。。
toyboot4e部分適用とポイントフリースタイル
Pointless style と揶揄されることもあるポイントフリースタイルですが、 無名関数を in-place で書いたり関数合成が続く場合には非常に良いと思えてきました。久しぶりに Rust を書くと .map(|x| ..) という形が無念です。
構文
-
ifは関数ではない (if' は Prelude にはない) -
`f`で関数を演算子として使うことができる - 演算子の部分適用 (セクション) の
(a `f`)と(`f` b)は区別される -
(op)で演算子を関数として使うことができる
Prelude
id :: a -> aconst :: a -> (b -> a)flip :: (a -> b -> c) -> (b -> a -> c)-
succ,pred -
curry,uncurry
Wiki より
- Point とは空間上の点 (値) のことであり、関数が適用される値のこと
- つまり pointfree とは引数を省いた表記法
- Haskell の構文を pointfree にしたり元に戻す関数がある (
pl,unpl) 。これを使って 様々なポイントフリースタイルのコンビネータ が発見された。必ずしも人間が見つけたわけでは無いのか。- owl:
((.)$(.)) - dot:
((.).(.)) - swing:
flip . (. flip id) - squish:
f >>= a . b . c =<< g
- owl:
. や $ を関数として使うのが分かりません。 owl はコードゴルフで見た気がする？ 今読む気はしませんが、この辺も使いこなしていきたいところです。
toyboot4e関数の applicative, 引数の分身
\[a, b] -> (a, b)
<*> で入力を分身させて、出来上がった……アプリカティブに……？ <$> で関数を適用します (本当の仕組みは知りません):
Prelude> (,) <$> (!! 0) <*> (!! 1) $ [10, 11]
(10,11)
……いや (\[a, b] -> (a, b)) を書いた方が良さそうです。
toyboot4e
do 無しで書こう
bind を無くす
before
do
v1 <- readArray tbl (i2, i1 - 1)
v2 <- readArray tbl (i2 - 1, i1)
return $ max v1 v2
after
max <$> readArray tbl (i2, i1 - 1) <*> readArray tbl (i2 - 1, i1)
IO も applicative!
追記
『Applicatve スタイルを使おう』の方が正しいですね。
toyboot4e短い変数名もイケてる気がする
line ではなく ln, table ではなく tbl, step よりも f がイケている気がします。
などと書いていましたが、やはり慣習に従ったほうが良い気がして来ました。 initialLine よりも line0.
もっとも頭文字を取って error を e と書くような極端な省略は苦手です。 Go などに触れると適応できるかもしれません。
toyboot4e変数名の重複を防ぐ
主にナップサック問題から。
-
ローカル変数の名前が一時変数と被らないようにする (
main)
Haskell には shadowing が非推奨なので、変数名が被らないように配慮すべきです。nではなくnItemsなどと命名して名前の重複を避けられます。 -
同じ型のデータが 2 つある場合、
xやyなどの prefix を付ける
xs@(x:xrest) ys@(y:yrest)のようなパタンマッチを利用します。 -
あえてパタンを分解しない手もある
上の例で、さらにxを分解してx@(xw, xv)などと書くこともできますが、fst x,snd xでも事足ります。
toyboot4e
Stack script を :load するには (→ stack repl を使う)
デバッグのため REPL から stack script の関数を呼びたいとします。
ghci から stack script を :load すると、コメントを無視してしまうため Stackage のパッケージが読めません。かわりに stack repl の起動時にプロジェクトを選びます。もしくは stack repl a/Main.hs のように読み込むファイルを指定します。
toyboot4eStack script をやめよう
Stack script を使っていたモチベーションは、環境構築が楽だった (oj のテストコマンドを ./Main.hs にできた) ことでした。 package.yaml もちゃんと書くことにしましたし、普通に stack でビルド・実行した方が良い気がします。
さて stack build abc279:exe:a-exe を試してみましたが、 a, b, c .. とすべてコンパイルされてしまいます。実行ファイル 1 つだけコンパイルしたいのですが……。
TODO
toyboot4e関数適用と実引数の色が同じだ
意外と tree-sitter が仕事していない……？
toyboot4eMisc
再帰やリスト内包表記を使わなくなってきた
Vector には基本パタンマッチができませんし、大体 fold で片付いてしまいます。 fold なら他の言語でも再現が楽です。
Rust で fold したことはないかも。
計算が派生する場合 (DFS など) は再帰関数を書いています。ファイルツリーを下っていくときなども再帰になりそう。つまり単純なループは foldl で表現できるし、新たな入力を取り寄せるためには再帰が必要なのでしょう。
forM_ 内で print するか、文字列を作って print するか
後者の方が美しいです。パフォーマンス的には……？
IntMap は確かに State モナドと相性が良さそう
do 記法は各行をポイントフリースタイルに変えてしまうから、 State モナドの do 記法によって IntMap の受け渡しをポイントフリースタイルにするのは自然に見えました。パフォーマンスはどうでしょう。
Stream って直に触れるのだろうか (あるいは Iterator はある？)
Rust なら xs.iter().chain(iter::once(x)) のようにチェインができます。同じことを Haskell でやるには？
foldに限ってはfold step x xs `step` x'のように書けます。
toyboot4e茶色パフォ後半が出るようになってきたけれど
解ける問題数は 3 から増えていません。
提出速度
高速で解答できると、同じスコアの参加者の中で順位が上がるため、パフォーマンスも上がるというだけです。つまり Vimmer であるかが問われます (違う)
水色ライン
順位 1,000 でパフォーマンス 1,300 程度でした。 5 問完答で 30 分弱、この辺が水色到達のボーダーラインな気がします。
レーティングの上昇速度
現在のレーティングの倍のパフォーマンスを出しても、レーティングは 11/10 程度にしかなりませんでした。さっさと水色に到達するには、 6 問解くしかありません。無理では……？
緑色目指して
正しくは 4 完目指して。
- 動的計画法
- グラフ (DFS, BFS, 連結グラフでグループ分け)
- Mod 計算
- 素因数分解、最大公約数、最小公倍数など
toyboot4e遅延評価で動的計画法
ズルいけれども動きます。また再帰ケース部を let の中の関数や where 句の関数に分けるとより簡単です:
let dp =
array (0, n) $
(0, 1) : [(i, acc `rem` unit) | i <- [1 .. n], let acc = step i]
step i
| i >= l = dp ! (i - 1) + dp ! (i - l)
| otherwise = dp ! (i - 1)
print $ dp ! n
tabulate
Algorithm Design with Haskell より tabulate 関数:
tabulate :: Ix i => (i -> e) -> (i, i) -> Array i e
tabulate f bounds = array bounds [(x, f x) | x <- range bounds]
これで上記を書き直すと:
let dp = tabulate step (1, n)
step :: Int -> Int
step 1 = 0
step 2 = dp ! 1 + xs VU.! 0
step i = (dp ! (i - 1) + xs VU.! (i - 2)) `min` (dp ! (i - 2) + ys VU.! (i - 3))
ガードが増えて重くなる……かと思いきや速くなりました。うーむ……積極的に使っていきましょうか。
toyboot4eMLE (memory limit exceed)
遅延評価 DP, いいやつだった……
toyboot4e茶色後半までは解けるようになった気がする
とはいえ問題を難しくすると太刀打ちできません。まだまだ閉塞感が強く、 ABC が趣味と言える日は遠いようです。
今までも同じことを繰り返して来たのかもしれない
新しい表記法であれやこれやを書き散らかすのは、英語も数学も物理も同じですね。
どこまで行くのか
あと何回脳みそで発芽したような感覚を味わえば、 4 問 5 問と ABC を解いていけるのか。あるいは ARC やらヒューリスティックコンテストに挑むことができるのか。どこまで行けるか分かりませんが、経過を面白く思っています。
まだしばらくは這いつくばって行くしかないと思います。案外一生そんなものかな……
toyboot4eヒューリスティックの本が出るとか
ポチった！ 有名な人みたいですが、誰の本なんだろう！
僕もビーム飛ばしてみたいですね。何のことかさっぱりですが……
toyboot4eヒューリスティックコンテストの基本的手法は 2 つらしい！
ヒューリスティックコンテストも視野から外さないようにはしよう……
toyboot4e
fold で 2 次元の動的計画法
方針
動的計画法の肝は枝刈りだと思います。入力を 1 つずつ受け取って探索し、テーブル上の『重複』を削除することで計算量をテーブルサイズ程度に押さえます。
Tips
fold を scan に変えたら、テーブルとして print できます。また print する都合上、横列を次の列に写す関数を使って fold すると捉えます。
演習
-
鉄則 A 18. 部分和問題
- テーブルの形: 横軸は可能な値の組 (
Vector BoolもしくはIntSet), 縦軸は入力値 - 重複の削除方法: bool 値への和にする
- テーブルの形: 横軸は可能な値の組 (
-
鉄則 A 19. ナップサック問題
- テーブルの形: 横軸は可能な重さの組 (
Vector Int), 縦軸は入力値 - 重複の削除方法: より価値が大きい方を選ぶ
- テーブルの形: 横軸は可能な重さの組 (
-
鉄則 A 20. 最長部分列 (連続性を問わない)
- テーブルの形: 横軸は入力値、縦軸も入力値
- 重複の削除方法: より長い方を選ぶ
感想
入力が 2 種類だと fold するのはなかなかキツいです。それにせっかく純粋な解答を作っても、 IO / ST を使った方が速いんだ〜〜
IO / ST を綺麗に書けるようにするのも重要かもしれません。 tabulate を IO / ST 用に書き換えてみようかな
toyboot4eナップサック問題をリストで解く場合
つまり探索をリストで持つ場合、 (w, v) のペアが w, v 共に単調増加になるよう調整します。重さが増えて価値が下がった探索は捨てなければ TLE となります。
不要な探索を捨てた場合、捨てなかった場合
明らかに実行速度に差がありますし、保持する探索の数にも大きな違いが現れました:
- W = 985042904
- length state == 3512979 (不要な探索を捨てなかった場合)
- length state == 57 (不要な探索を捨てた場合)
それでも スキャン数 < W のはずなのですが、なぜ TLE になるのか……？
toyboot4e
IO / ST で 2D 動的計画法 (ナップサック問題)
tabulate の IO / ST 版を作ればいいじゃない！
パフォーマンス面の確認
-
Array(AC) はUArray(AC) よりも遥かに悪い- メモリ: 83 MB → 597MB
- 実行時間: 174 ms -> 2466 ms
- ループ部分を関数に切り分けると (つまり高階関数を使おうとすると？) さらにメモリ使用量が倍近くなる (MLE)
- ※ この
tabulateIO関数はまだまだ改良が必要
- ※ この
Haskell でナップサック問題を解く場合は、むしろ fold が安牌という気がしますね……
非インテリの所業
tabulateST を作りたいのですが、色々ハマって質問しています。全然課金して質問したいのですが、いつまでも taker のままで良いのでしょうか……
意外と Haskell の限界に近いのかもしれない
STUArray 版が通る ようにしてもらいました！ やや無念は残り、
- 型引数
eを具体的なIntに置き換えています。 - ユーザ関数 (
f) の型推論ができませんでした
毎回 runSTUArray とか forM (range bounds_) $ \i -> do .. とかを書く方が現実的な気がしてきました。 tabulateST を使う案は棄却します。
tabulateST では INLINE 化しても意味が無かった
なんでだろう……？
toyboot4e
tabulateST が通るようにしてもらった
あと一歩の修正まで来ていたようです。これは嬉しい！！
なぜ通るのかイマイチ分かってないですが、かなり応用が効くのではないかと思います。手続型プログラミングを簡単にしていこう。
toyboot4eメモ化で 2D 動的計画法 (ナップサック問題)
tabulate の Map 版を作ればいいじゃない！
Unboxed 版は当然 MLE
まず Map を使う と MLE 。 tabulateST より使い勝手は良いけれど……
IntMap ならギリギリ AC
あら意外……！ AC です 。メモリ使用量は STUArray 版と変わらず、実行速度は明らかに遅いという程度。 TLE の危機はありますが、低空飛行で実戦投入できそうです。
また IxMap は無いので IntMap を使うのは少し面倒です。 index bounds_ i のようにして IntMap の引数に変換します。
indexを忘れるとコンパイルエラーになるので、そこまで問題ではありません。
ただ、メモを sparse にする意味は無い
パフォーマンス的にも tabulateST の劣化版なのだなぁ……。
HashMap (unordered-container) では TLE
Strict 版なので MLE は避けられましたが、 時間制限を超えました 。妥当なところですね。 IntMap が TLE にならなかった方が意外でした。
toyboot4e型クラス Ix が便利でいいなぁ
n 次元座標の表現はもちろん、区間の表現もできることを知りました。 Prelude は総洗いした方が良いかもしれない……
$ ghci
> import Data.Ix
index
(min, max) 区間における相対位置を返します:
> index ((1, 1), (2, 4)) (1, 1)
0
> index ((1, 1), (2, 4)) (1, 2)
1
Row-major な行列では、添字は
(y, x), サイズは(h, w)のように書きます。
range
n 次元のイテレーションもお手のもの:
> range ((0, 0), (2, 4))
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(1,4),(2,0),(2,1),(2,2),(2,3),(2,4)]
inRange
Inclusive range 内にデータがあるかを判定:
> inRange (1, 5) 3
True
> inRange (1, 5) 5
True
> inRange (1, 5) 6
False
> rangeSize ((0, 0), (2, 2))
9
そう書けばいいのか
unless
モナディックアクション？ では if の代わりに when / unless を使うとスッキリします:
forM_ [1 .. (n - 1)] $ \i -> do
v0 <- VUM.read vec i
unless (v0 == -1) $ do
VUM.modify vec (max (v0 + 100)) (x100 VU.! pred i)
VUM.modify vec (max (v0 + 150)) (x150 VU.! pred i)
なぜ未だにこんなことを……
listArray @UArray
@ で部分的に型を書くと、全体を推論してくれる場合があります:
input <- concat <$> replicateM n getLineIntList
let mat = listArray @UArray ((0, 0), (m - 1, n - 1)) input
-- let mat = listArray @UArray ((0, 0), (m - 1, n - 1)) input :: UArray (Int, Int) Int
newArray でも同様に:
explored <- newArray @IOUArray ((0, 0), (h - 1, w - 1)) False
let で where モドキ
特に fold するときは、トップレベル関数を作るよりもクロージャを作ってしまいます。
let の中でサブ関数を定義する
let xs = foldl' step s0 [0 :: Int ..]
s0 = _
step = _
let の中でサブ関数を定義する + 本物の where
let xs = f
f = foldl' step s0 [0 :: Int ..]
where
s0 = _
step = _
ツイート
toyboot4eスニペットという手があったか
たとえば for3 を 3 重ループに展開するとか。なるほどね！ あるいは Copilot を巨大なスニペットとして扱う人もいそうです。
僕はクソデカテンプレートを持ち歩いていますし、 Haskell だとスニペットが不要なほど簡潔なコードを書けることが多いです。でも Tempel を使ってあげたいなぁ
toyboot4eMisc
-
競プロのコミュニティがあるらしいけれど
どこなんだ……毎週 7,000 人も参加しているのに………… -
けんちょん本 の高評価をよく見る
初期にこの本を買えばよかったかも。。
toyboot4e今欲しい Haskell の本
競プロから摂取できる Haskell には限界があります。 Haskell の機能にフォーカスした本が欲しいです。
- 小〜中規模プロジェクトの開発 (モジュール分割やテストなど)
- 型族などの言語機能の解説
-
lensなどのライブラリの使い方の解説 - 使えるモナド
たぶん Haskell in Depth が合う気が。
今いらない Haskell の本
関数型プログラミングにフォーカスした Haskell の本。 Richard Bird 先生、難しすぎる……！
toyboot4e高密度なコードを読み書きするのが楽しくなってきた
要因は慣れです。基本的な関数のシグネチャを覚えてきました。探しものをすると短期記憶が失われますが、そのまま読めるなら便利なことこの上なし！
逆に今の道具立てを失うと、スッキリとコードを書けなくなるかもしれません。関数型言語の中で完結しようとする人たちの目線も少しずつ取り込みたいものです。
toyboot4e進捗表を別のスクラップに分けてみた
toyboot4eMap vs Sorted array (バランス木 vs ソート済み配列)
メモリ
- Map: sparse
- Array: dense
操作
- Map
- 更新: K -> V
- 探索: K → V
- Sorted array
- 更新: K -> V
- 探索: V → K
toyboot4eビームサーチは貪欲砲
鉄則本のビームサーチをざっと読みました (A49) 。幅 k のビームサーチは、最善の探索を k 個保持します。入力を受け取る毎にそれぞれのビームから探索を進め、上位 k 本を抽出します。
どのビームを最善手とするかは評価関数が決めます。評価関数の取り方によって、最終スコアが大きく変わります。
toyboot4e制御構文が未だに分からない
continue や early return のやり方が分かりません。 Maybe モナドはやり過ぎな気がしますし、そもそもモナドを使うのはセンスが悪いような気もします。
Early return 不要にする方作
番兵を使えば分岐を削除できる場合があります。 Haskell だと、手続型プログラミングも技巧的になりがちですね。
toyboot4e
span で takeWhile + dropWhile
toyboot4e年末に ABC 無かった
(・ω・)
toyboot4eプライドを捨てよう！
- 解答 AC でもよかろうなのだ！
- 解答 AC できなくてもよかろうなのだ！
- TLE を直せなくてもよかろうなのだ！
- Haskell らしいコードが書けなくてもよかろうなのだ！
2 週目があるさ……
toyboot4e解ける問題を解くことで上がる実力がある
らしい……
toyboot4e意外と C++ よりも速いことがママある
toyboot4e謎の英単語
intersperse: 間に入れる (a -> [a] -> [a])
Prelude Data.List> intersperse " " ["a", "b", "c"]
["a"," ","b"," ","c"]
intercalate: 間に入れる ([a] -> [[a]] -> [a])
Prelude Data.List> intercalate " " ["a", "b", "c"]
"a b c"
どう違うんだ……
単語のニュアンスは分かりませんが、 Haskell の関数としては理解しました。
toyboot4eけんちょん本を買ったぞ！
ある程度鉄則本を解いたので、読み物寄りの本を購入しました。これでグラフや DP の考察に強くなれれば……いえ、単純に趣味ですね。
toyboot4e
無限リストを filter しても永遠に制御は帰ってこない
takeWhile にしよう
toyboot4esieve (エラトステネスの篩) の高速実装ができない
コピペしよう……
そうか
ふるいの網目 (filter) が増える毎に処理が重くなりますね (実質 xs `elems`) 。網目を IntSet で持てば十分高速だったということになります。
toyboot4eフェルマーの小定理も万能ではなさそう
フェルマーの小定理を使って逆数の素数 modを計算できる！
ところで
まあ階乗の mod 計算には安全に使えます (
toyboot4eテンプレート 800 行、だと……！
バカデカくなっちまって……！
toyboot4e今貴様が参加したのは ABC ではない
ARC だ……！ (曜日が逆なので気をつけましょう)
toyboot4eお気に入り機能の使い方が分かったぞ！
これで Haskell ユーザの動向をウォッチできるわけですね
toyboot4e鉄則本が A ~ EX までカバーしている
後は単なる実力不足ってコト……？！
toyboot4e集計を待たなくてもレーティングは分かるぞ！
ブラウザ拡張 (predictor) で競技中のレーティングが見れますし、コンテスト終了時も公式発表を待たずに結果が分かります。おやすみ (・ω・)
Predictor 上のレート表示が集計結果と一致しない
- 不正ユーザの BAN
- Predictor 自体のバグ (最近発生)
toyboot4eいろいろツールがあるみたい
-
AtCoderTags
投票によって問題を分類分けしてくれます。サイトの見た目からして非常に良さそうです。 -
AtCoder Problems
ABC の問題一覧 (diff 表示 + AC 状況) や統計など。助かっています。 -
AC heatmap
GitHub の芝のように AC 数を表示してくれます。 -
AtCoder Type Checker
同レートの人たちと比較して、回答速度で performance を稼いできたか、それとも AC 数で performance を稼いできたのかを確認できます。僕は残念ながら早解き型でした。
toyboot4eSequence でキュー (FIFO)
toyboot4eHeap で優先度付きキュー
toyboot4eHashMap で文字列キーのマップ
たぶん containers の Map よりも高速？
toyboot4eグラフの連結成分や塗り分け(?) のテンプレートが欲しい
まず既存の API を把握したいです。
Data.Graph だと……！ (containers)
内部的には Array Int [Int] です。
-
buildGでお手軽作成 (ただのaccumArray) -
componentsで連結部分をまとめ上げ (これが便利……！) -
scc(+ 長さ 1 を削除) で閉路も手に入る (便利……！)
Node, Tree, Forest あたりが複雑なので、直接使用するのは避けようと思います。
UnionFind
- ルート一覧 (連結成分の個数)
連結後、root v == vとなる頂点の数を数える
toyboot4e
さらば Data.Graph
Tree が使いづらいので Data.Graph の関数に頼るのは止めました。 topSort だけ借ります。
toyboot4eけんちょん本でグラフ問題をエアプ
動的計画法なんかはサッと流しつつ、グラフを本格的にやってくれますね。
単一始点最短経路問題
Dijkstra 法
エアプじゃないので省略します。昔の僕はヒープが無い環境でプログラミングをしていたので、
ベルマン・フォード法
(N - 1) 回の状態発展 (そんな用語があるかは知りません) を実施！ 負のループ (サイクル) が存在しなければ (N - 1) 回までの発展で必ず収束します。 N 回目の発展で状態変化が起きたかどうかで負のループがあるかを判定できます。
全点対間最短距離 (Floyd–Warshall 法)
DP で解いちゃう！
最小全域木問題 (Kruskal 法)
辺に対する貪欲法！ 連結の状態は Union-Find で持てます。
ネットワークフロー
最小カット問題 (辺連結強度の問題)
- s-t カットの最小容量は辺素な s-t パスの最大本数と等しい
- 辺素な s-t パスの最大本数は、残余
グラフネットワークを考えて取得できる
最大流 (フロー) 問題
- 辺に重みがある場合の最小カット問題 (最大流最小カット問題)
- 同様に残余
グラフネットワークを考えて計算できる (Ford-Folkerson 法)
なんとなく電流関連の定理 (テブナン？) と似ている気がします。一旦イメージだけ暗記してしまうか
2 部マッチング
始点と終点を追加して最大流問題に帰結！
点連結度
各頂点を 2 分割すれば辺連結強度に関する問題 (よく分からぬ)
プロジェクト選択問題
始点と終点を追加して、制約を重み無限の辺で表現する
積んでいる本
これを読んでおけば良かったなと今思います。 Robert Nystrom もグラフ理論はめちゃめちゃ使ったと言っていましたし。次はこの本か Haskell in Depth か Richard Bird か、それとも章末問題を解いてエアプ卒業か……
toyboot4etempel でスニペット挿入 (Emacs)
例
たとえば tr C-j で !_ = traceShow () () を挿入できます。通常の補完と名前空間が分かれているのが良いですね:
haskell-mode
(traceShow "!_ = traceShow (" (p "") ") ()")
今後は典型的なコードはテンプレートファイルにメモしていこうと思います。
その他便利そうなもの
(yn "if " (p "result") " then \"Yes\" else \"No\"")
(graphGen "input <- concatMap (\\[a, b] -> [(a, b), (b, a)]) <$> replicateM nEdges getLineIntList" n>
"let graph = accumArray @Array (flip (:)) [] (1, nVerts) input" n>)
(fold "let result = foldl' step s0 " (p "input") n>
" s0 = " (p "_") n>
" step = " (p "_"))
(for2 "forM_ [0 .. h - 1] $ \\y -> do" n>
"forM_ [0 .. w - 1] $ \\x -> do" n>)
(runSTUArray "let dp = runSTArray $ do" n>
"arr <- newArray ((0, 0), (h - 1, w - 1)) (0 :: Int)" n>
" return arr")
(VU.create "let dp = VU.create $ do" n>
"vec <- VUM.replicate (h * w) (0 :: Int)" n>
" return vec")
個別のケースをコードに書きつけても良い
一般解でなくても AC できれば良いのですし、むしろ境界を考慮したコードが書けて良いかもしれません:
main :: IO ()
main = do
[n, k] <- getLineIntList
print $ solve n k
modulo :: Int
modulo = 10 ^ 9 + 7
solve :: Int -> Int -> Int
solve 1 1 = 1
solve 1 k = k
solve 2 k = k * (k - 1) `rem` modulo
solve 3 k = k * (k - 1) * (k - 2) `rem` modulo
solve n k = _
Language Update 2023
vector が更新されると Unbox が簡単に導出できるようになるらしいので、それだけで満足な気がします。
toyboot4e螺旋本を買ったぞ！
先日のセールで『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』が Kindle 版 500 円になっていました。もちろん購入したので、 Kindle Scribe (*1) で読んでエアプしていきますよ〜〜
この本の評判としては、意外と競プロ (プロコン) に特化していないとのことです。たとえばソートの内部実装もやってくれます。娯楽としてはちょうど良いと思います。
(*1): マウントポイント
toyboot4e小ネタ集
-
IM.fromListWith (+)で sparse なaccumArrayができる-
fromListだと重複した要素が消えるため要注意 -
elemsやkeysは ascending order (昇順) がデフォルト -
IM.toAscList,IM.toDescListは共にO(N)
-
toyboot4eLang Update 2023 に備えて
追加予定のパッケージを見ていきます。
Misc
ありがとう有数の識者たち…… 🙏 普段の ABC 参加者は 10 人くらいですし、最新のハイパフォーマンス Haskell に詳しい人はさらに限られます 🙏 🙏ましてアップデートに注力してリサーチしてくれる人は 🙏🙏 🙏
ABC では通れば良いので、高速化ライブラリはヒューリスティックとかハイレート勢向け向けの気がします。しかし提出結果を比較して最適化の効果を実感できるので、趣味のためにもこうしたライブラリはガンガン入れてほしいです。
パッケージ
Hackage と Stackage の違いが分からないことに愕然としました。
-
attoparsec
速いparsec? -
bitvec
めちゃくちゃ速いBoolの vector! -
deepseq
seqや bang pattern と違って、データコンストラクタなどの内側まで評価してくれるようです。真に strict な評価が来た？！ -
exceptions
実行時エラー表示をマシにできるかも？ https://qiita.com/aiya000/items/6700753df2dfb9ae942e -
extra
準 Prelude 気分。 Data.Tuple.Extra が特に良さそう です。 both とは Bifunctor には無いやつやし、トリプレットへのアクセサはそもそも無いんよ -
fgl
グラフのつえーライブラリらしい 。なぜ見逃していた……？ -
integer-logarithms
Int#が出てくる謎ライブラリ。スルーかなぁ -
lens
構造体の部分的更新に使えるらしい？ 僕が AtCoder で使うことは無さそうですが、 AtCoder 外の準 Prelude みたいなライブラリを見ることができるのは良いですね。 -
linear-base
線形型、ということは所有権を Haskell に持ってこられるのだろうか……？ -
massive
repa 代打？！ -
mono-traversable
fmapならぬomap,traverseならぬofold? Monomorphic container というのはVec<T>のような普通のコンテナと思いますが、そんな一般的に実装できるのだろうか…… 。要チェックですね。 -
mutable-containers
Mutable な Deque なんかがあるっぽい？！ 鉄則本での純粋な解答を見直す機会になります。 -
mwc-random
乱数生成 ヒューリスティック向け？ topcoder みたいに撃墜システムもありませんしね -
parallel
ヒューリスティック向け？ parsec-
psqueues
Pure priority search queues. よく分かりませんがheapsの代わりになるかもしれません。 -
random
乱数生成 ヒューリスティック向け？ -
reflection
なにがなんだか。。 -
regex-tfda
正規表現 -
safe-exceptions
推奨されている方のやつ！ -
template-haskell
噂のやり過ぎてしまうテンプレートシステムだ！ -
tf-random
乱数生成 -
utility-ht
ビットシフトの演算子とか、Enumに対するIxとかif'とか。 それほしいやつやん！
repa は 1 回も使うことなく消えたよ……
インフラ強化
-
safe-exceptionsでマナーの良いコードが書けそう
前からあるじゃん
-
fgl,massive,mutable-containers,psqueuesが要チェックです！ -
mono-traversableも見てみたい。 -
extraとutility-htも良し！
最新 Prelude はまたの機会に
こちらも良いものが増えてそう！
toyboot4e見直すと、大半のライブラリが 2020 年環境で利用できたので履修していきます。逆に何が増えたんだろう…… (safe-exceptions くらい……？)
toyboot4e本日の ABC は D~ 異様に難しいらしい
つまり分が悪い。早解きと ARC A を解いてみるしかないか〜〜
待って
ARC 序盤って水色頻発地帯ですね……。ヤマ張って EDCP を進めますか……？
新たなリソースが
これはエアプと復習にめちゃめちゃ良いぞ……！
新しい本を買い増した
Richard Bird 先生が難し過ぎた。。鉄則本購入者のセンサーが働く限り、この本がとても良さそう！
toyboot4eABC 負けたよ (・ω・)
開始 60 分で 7,000 位になっていました。 危なかった ……。精彩を欠いた状態は露骨に結果に現れますね。精進しようにも全然解けないし、しばらく守りの番かもしれません。
Immutable な Vector の更新関数があった
これ良いですね。全要素更新するなら generate を使いますが、部分更新をシンプルにできそうです。 foldM を止められる 気がします:
| 入力がリスト | 入力が Vector | 更新方法 |
|---|---|---|
| VU.// | VU.update | 上書き |
| UV.accum | VU.accumulate | 関数適用 |
ただどちらも modify は高速 (in-place) になることもらしいので (所有権を追えるのかな) 、ソート以外にも使ってあげたいです:
結局 generate と modify がスタメンになる気がします。
ライブラリを見直そう
実は VUM.nextPermutation のような便利関数もあり、 extra, utility-ht を始め、既知のライブラリを見直した方が良さそうです。
toyboot4eDense で immutable な Union-Find を作ってみたい
Union-Find テンプレートの改良を図ります。
- VU.modify で immutable かつ in-place なデータ更新ができるはず！
- また vector-th-unbox で自作データ型を
Unboxにしたいです。
Union-Find の immutable 実装
Mutable な関数をタプルを返す関数に置き換えます。 State モナドにしてもいいかもしれません
Unbox の自動導出
古い vector パッケージではUnbox の実装するのは至難の業です。解決方法としては、
1. unboxing-vector (sum type 不可)
Vector.Unboxed と Vector.Unboxed.Mutable を unboxing-vector パッケージのモジュールに置き換えます。 Unbox の代わりに Unboxable を使うことになるので、既存のコードも編集が必要です。
ただし sum type に対しては Unboxable を実装できない ようです。今回は利用できません。
2. vector-th-unbox (sum type も可)
Template Haskell で Unbox 実装をコード生成します:
-- vector-th-unbox: https://www.stackage.org/lts-16.11/package/vector-th-unbox-0.2.1.7
import Data.Vector.Unboxed.Deriving (derivingUnbox)
newtype UnionFind = UnionFind (VU.Vector UFNode)
-- | `Child parent | Root size`. Not `Unbox` :(
data UFNode = UFChild {-# UNPACK #-} !Int | UFRoot {-# UNPACK #-} !Int
_ufrepr1 :: UFNode -> (Bool, Int)
_ufrepr1 (UFChild x) = (True, x)
_ufrepr1 (UFRoot x) = (False, x)
_ufrepr2 :: (Bool, Int) -> UFNode
_ufrepr2 (True, x) = UFChild x
_ufrepr2 (False, x) = UFRoot x
derivingUnbox "UFNode" [t|UFNode -> (Bool, Int)|] [|_ufrepr1|] [|_ufrepr2|]
Sum type に対しても問題なく実装できています。
謎のパースエラーが出たので関数を分けています。
結果
UV.modify は遅い。全然 in-place に動いてない気がしますね:
| 種類 | boxed | Unbox |
|---|---|---|
| Mutable (PrimState + INLINE) | 463 ms | 187 ms |
Immutable (VU.modify) |
TLE | TLE |
また既設の Union-Find は Unbox 実装で倍以上高速になりました。今回は明らかなミスの修正でしたが、競プロにも盆栽の余地がありますね。だから黒魔術に走る人がいるわけですか (あの方 C++ よりも速いんだもん……) 。
toyboot4eレートが横ばいだ
今日 80 分かかった 4 問を 20 分で解けるようになるとは思えません。やはり 1,000 問解いて E まで解けないとダメか……！
toyboot4e急速にレートを上げるには、 F や水 diff が解けないと無理よ……！
toyboot4eHaskell 界で A 問題最速だ
下っ端は任せろ！
toyboot4e人のコードも読んでみようかな
Haskeller のコードは参考にならないことが多いです。
- リストを使っている。技巧的で難しいです。
- 普通の Haskell. 普通に難しいです (絶望)
- 黒魔術である。 C++よりも速いし当然読めないのである。
ただ今より良いコードを書こうと思えば、他人から吸収するしかないので、そろそろコードリーディングの下地を作って行こうと思います。思うだけかも……。
toyboot4eHaskell の話
こういう話はあと 10 本ぐらい聞きたい……！
こっちも……！
こういうやつも……！
そういえば動画派もいる
ライブコーディングという手もあったか……！ しっかりついていく必要があるので、あまり観ることはないのですが、勉強にはなるので時間を割くべくかもですがうーむ
toyboot4eバーチャルコンテストだと……！
とりあえずこれに出る……！
https://mojacoder.app/users/Ajinoko/contests/Ajinoko_ASC ジャッジが Haskell 非対応だ！ 参加登録してごめんなさい！
定期開催
競プロのコミュニティはあるのか無いのかよく分かりません。
-
20:00 ~ 20:30: ABC 過去問
https://twitter.com/i/communities/1502662995817959432
短過ぎてうーむ -
朝の定期開催コンテストを探したいです
結局は
一人でやろうということに。
toyboot4ePAST 上級本を買ったぞ！
3 月末発売ということで楽しみにしています。
Thunder 本も買ったぞ！
今週出ますね。かなり楽しみです。
ヒューリスティックは言語の実行速度が点数に直結するはず (?) なので、 Haskell は辛いんじゃないかと思います。ここはまさかの Common Lisp か……？ 何か面白い言語を探したいですね
toyboot4e毎日 3 問解き続けた 3 か月目の自分に負けるんだろうな
今 AtCoder 9 か月目なのですが、 AC 数 227 を見てそんな計算ができました。身近な夢から叶えていこう
toyboot4eABC 290 (日曜開催) も半 ARC 仕様だ
すなわち早解き会……！
toyboot4e辞書順
ABC 276 C - Previous Permutation など
辞書順で何番目？
辞書順で次の順列は？
具体例を見ると:
- 123 45 → 123 54
- 1 2543 → 1 3245
つまり後ろから見て単調増加が崩れた点以下を加工します。
辞書順で 1 つ前の順列は？
具体例を見ると:
- 543 21 → 543 *12
- 54 312 → 54 231
つまり後ろから見て単調減少が崩れた点以下を加工します。
加工のやり方
めちゃくちゃ頑張る。。
nextPermutation で prevPermutation を作る
Haskell にも Vector.Mutable.nextPermutation があります。逆向きに nextPermutation するには、 Ord の向きを替えてしまえば良いので、それぞれの桁を Down で包みます:
prevPermutationVec :: (Ord e, VG.Vector v e, VG.Vector v (Down e)) => v e -> v e
prevPermutationVec =
VG.map (\case Down x -> x)
. VG.modify
( \vec -> do
_ <- VGM.nextPermutation vec
return ()
)
. VG.map Down
なお const () <$> VUM.nextPermutation や VUM.nextPermutation >>= \_ -> return () とは書けません。 ST モナドのライフタイム制限は厳密……！ (この例は安全側なので通してほしいけれど)
toyboot4eGHC 8.8.4 + lts-16.31 + HLS 1.8.0.0 がいいかもしれない
GHC 8.8.3, lts-16.11 と大差無い環境で、しかし変数のリネームができる！
なにより nixpkgs に ghc884 があるので NixOS でも環境構築できるのがありがたいです。難しすぎだよこの OS ……
toyboot4e
groupBy が思っていたのと違った
Data.List の groupBy
Prelude Data.List> groupBy (\a b -> a + 1 == b) [1, 2, 3, 4]
[[1,2],[3,4]]
リストの先頭の要素と次の入力を比較しています。リストの末尾の要素と比較してくれませんか！！、
https://stackoverflow.com/questions/1316365/haskell-surprising-behavior-of-groupby
== と同じ性質を前提とするみたいです。詳しく読んでいません。。
utility-ht
こちらの groupBy は隣接要素を比較するとか。完全にこれだと思っていました……
> Data.List.HT.groupBy (\a b -> a + 1 == b) [1, 2, 3, 4]
[[1,2,3,4]]
HT.groupBy という形で使っていこうかな。あるいは groupBy を使わないのが無難かもしれません。
toyboot4eそろそろ人のコードを読もう
ABC 290 D の提出 を読みます。
モチベーション
実行時間 41 ms ですって。 C++のどの提出よりも速いのです。バケモンだよ……！
冗談だろ、ハニー
Haskell は AtCoder で 2 番めに速い言語
我々がロブスターならば、彼はレックウザであると言わざるを得ない
冒頭
- まずは
LANGUAGEpragma から。- フォーマッタが
ormuluではないようです。 -
CPPを定義して#defineが有効になっています。 -
GHC.Exts に primitive 型があります。 Haskell では
Intも boxing の対象になるらしいですからね……
- フォーマッタが
-
#include MachDeps.h- 今、何が起きた……？
マクロ
1 行で INLINE プラグマ。まぁ #[inline] に比べて {-# INLINE <name> #-} はセンス悪いですよね:
#define IL(f) {-# INLINE f #-}; f
入出力
ABC 290 D では以下の入力が与えられます:
3
4 2 1
4 2 2
4 2 3
パース部分。 rIntL, rIntL, rInt1L が Int のパーサで、それらの出力を liftA3 (,,) を使ってタプルにまとめています:
main = do
t <- readLn
qry <- getVecURest t $ liftA3 (,,) rIntL rIntL rInt1L
rIntL, rInt1L
rIntL は Int を読み、 rInt1L は 1-based index な入力を 0-based な入力に変換します 。 Haskell では shadowing 非推奨なので超重要！ これなら NPlusKPatterns に依存せずにシュッと書けます。上手い:
IL(rIntL) :: StateT BSL.ByteString Maybe Int
rIntL = skipSpecialL $ StateT BSL.readInt
IL(rInt1L) :: StateT BSL.ByteString Maybe Int
rInt1L = subtract 1 <$> rIntL
TODO: なぜ StateT?
rIntL の L とは left かな？ 実装を追います:
IL(skipSpecialL) :: (MonadState BSL.ByteString m) => m a -> m a
skipSpecialL = (dropSpecialL *>)
IL(dropSpecialL) :: (MonadState BSL.ByteString m) => m ()
dropSpecialL = modify $ BSLW.dropWhile (< ord8 '!')
-- import qualified Data.ByteString.Lazy as BSLW
-
MonadStateはgetとかputのようなStateの基本的な API っぽいですね。ここ、すごい H 本で出てきた所だ！
TODO: 頑張って読む。
getVecURest
getVecURest は generic な実装に委譲しています:
-- import qualified Data.ByteString.Lazy.Char8 as BSL
IL(getVecURest) :: (VU.Unbox a) => Int -> StateT BSL.ByteString Maybe a -> IO (VU.Vector a)
getVecURest = getVecGRest
Generic な方の実装:
IL(getVecGRest) :: (VG.Vector v a) =>
Int -> StateT BSL.ByteString Maybe a -> IO (v a)
getVecGRest n s = VG.unfoldrN n (runStateT s) <$> BSL.getContents
WIP
toyboot4e小物
仮案
tuple2, tuple3 がかなり便利です。 uncurryした通常の関数に入力を丸ごと渡せることがあります:
getLineIntList :: IO [Int]
getLineIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
tuple2 :: [Int] -> (Int, Int)
tuple2 [!a, !b] = (a, b)
tuple2 _ = error "not a two-item list"
tuple3 :: [Int] -> (Int, Int, Int)
tuple3 [!a, !b, !c] = (a, b, c)
tuple3 _ = error "not a three-item list"
getTuple2 :: IO (Int, Int)
getTuple2 = tuple2 <$> getLineIntList
getTuple3 :: IO (Int, Int, Int)
getTuple3 = tuple3 <$> getLineIntList
catPairs :: [(a, a)] -> [a]
catPairs [] = []
catPairs ((!x, !y) : xys) = x : y : catPairs xys
concatMap2 :: (a -> (b, b)) -> [a] -> [b]
concatMap2 f = catPairs . map f
また concatMap2 と extra パッケージがあれば、グラフ生成をポイントフリースタイルで書けます:
getGraph :: Int -> Int -> IO (Array Int [Int])
getGraph nVerts nEdges = accGraph . toInput <$> replicateM nEdges getLineIntList
where
accGraph = accumArray @Array (flip (:)) [] (1, nVerts)
toInput = concatMap2 $ second swap . dupe . tuple2
重み付きグラフを格好良く書くのははちょっと厳しいかな……
入力処理の汎用性について
関数を分けるより、型クラスを作って getLine' @(Int, Int) みたいに書くほうが良い？
パースの方法 (空行区切り) も明示的に指定したくなってきますね。まぁ Int で空白区切り限定でも良いのではないでしょうか。
toyboot4e基本的な構文や言語機能に関し
合意できる点も増えたのでノートします。
-
if, then, else
キーワードが分かれているおかげで、それぞれの句で $ が使えます。 -
Public item を module キーワードで定義する
- Module キーワード以下は簡易 DB とみなし、エディタのコマンド経由で item を追加・削除すれば良いです。
- Public item をソース上でハイライト表示すれば、 pub キーワードが無くても公開性を一目で見れます。
-
言語拡張が無いと弱い
うーん -
INLINE, define, template haskell
うーん -
モナドを合成すると重くなりがち
うーん -
所有権が無い、遅延評価を使う
うーん。研究が進めば Haskell, Rust の次の言語が出てくれるのでしょうか。
toyboot4e黒魔術 Haskell からの植え替え・枝抜き
ShowBSB (ShowAsBuilder)
ByteString は普段入力にしか使っていないのですが、出力にも使いやすいように easy なコードを追加します。
まず ByteString な print 類に別名を与えます:
putBSB :: BSB.Builder -> IO ()
putBSB = BSB.hPutBuilder stdout
printBSB :: ShowBSB a => a -> IO ()
printBSB = putBSB . showBSB
そして ByteString.Builder への変換を共通のインターフェースで統一します
{-# LANGUAGE DefaultSignatures #-}
-- | Show as a bytestring builder
class ShowBSB a where
showBSB :: a -> BSB.Builder
default showBSB :: (Show a) => a -> BSB.Builder
showBSB = BSB.string8 . show
instance ShowBSB Int where
showBSB = BSB.intDec
instance ShowBSB Integer where
showBSB = BSB.integerDec
instance ShowBSB Float where
showBSB = BSB.floatDec
instance ShowBSB Double where
showBSB = BSB.doubleDec
空行区切りで Vector を print する
WIP. 逐次 print vs ByteStringBuilder 一括出力？
WIP
toyboot4e永年初心者
$ 演算子の謎
コンパイルできない:
countCost v = costs VU.! v + sum $ map (costs VU.!) $ filter (`IS.notMember` visited) $ graph ! v
コンパイルできる:
countCost v = (costs VU.! v +) . sum $ map (costs VU.!) $ filter (`IS.notMember` visited) $ graph ! v
関数適用の優先度が最も高いならコンパイルできそうなものですが、 $ が絡むと謎が多い……
toyboot4e$ の左辺は関数ということでしょうか。未だ基礎的なメンタルモデルに漏れがあります。
unfoldr の step 関数が $ の時もあって謎です。 Haskell のサブセット、自分方言しか扱えません。自分の方言を強くしていこう！
今は vector の stream を使えば foldUntilVG が作れるんじゃないかと食指を伸ばしつつあります。
toyboot4eループ処理
-
(!! n) $ iterate step s0: n 回繰り返す -
foldl' step s0 input: 畳み込み / 入力処理 -
until pred step s0: ループ / early return
foldl' と until の合わせ技が欲しい気もします。
追記
(!! n) $ iterate step s0 は 非常に低速で TLE になった ので止めましょう。
toyboot4eテーブルのサイズと DP の難度
2 要素のみ
fold で解けます。 DP という意識が湧きません。
N 要素のみ (ナップサック問題など)
fold で解けます。到達可能な範囲のみ更新するように気をつけます。そこそこ簡単な印象です。
N * N 要素 (最小共通部分列、区間 DP など)
途端に難しい。
N 要素 + N 要素 (最長増加部分列など)
相当難しい。
toyboot4eF 問題まで解けないと入水は厳しい
恐ろしい世界だ……年単位で時間をかけられるなら話は別ですが……
toyboot4e255 AC, 32 ABC 参加
フハハハハハハハハハ こんなものか自分……！(・ω・)
剽窃
@ユーザ名 を付けてこれをパクろう:
toyboot4e日報
Name shadowing は許可してしまうか
let visited' = IS.insert v visited とやった後に visited を使うことはありません。むしろ name shadowing を許可したほうがスコープが整理されて安全でしょう。やってしまいます:
ghc-options:
-Wno-name-shadowing
ただ思わぬ再帰で無限ループを作らないように気をつけます。
追記: let visited =IS.insert v visited の時点で無限ループになる……？ (悲しみ)
TODO: Stack script に警告抑制に相当するコメントを書き込む？
手続き型 Haskell が辛すぎる
1 問 6 時間かけて 謎に AC できない かろうじて AC するし、無残なコードがどうにもならない。そんなペースです。今、緑問題 streak 週間だから眠れないんだ……
Vec が無いのが辛すぎる
最大流問題の実装で苦しんでいます。 Vector は基本固定長配列なのです。 Capacity と lenght の区別も無いし……
頂点数を事前に数えて MVector を使うか、 IntSet や Sequence で誤魔化すか……。まずは [Int]IntSet で実装してから、後に盆栽します。剪定します？ それともパフォーマンスは追求しなくていいか……
foldM に early return が無いのが辛い
定石がほしい。。ガードで止めてますが、空回りが残るのは気になります、
forM に early return が無いのが辛すぎる
if の多重ネストになっています。 StateT で返値書き込みかなぁ
悩みどころは無限にあります。やはりハイレート Haskeller の盆栽的積み重ねがすごい……
AC した
天才！ まあ酷いコードなので、リファクタリングの手段を探したいと思います。いつ見つけられることやら……
それでも上手く行ったときのことを考えてしまう
時間ができた瞬間に都合の良い想像ばかりしてしまいます。何もかも上手くやり、理想的なプログラミングに近づいたとしたらと思うと、まだまだ離れる気にはなりません。 macOS も Git も Vim も Rust も Evil Emacs もそうやって習得してきたので、脳みそが変質するタイプの博打からは中々撤退できません。
マゾではないですが引き続きやっていきます。今のテーマは『Haskell で妥協の無い手続き型プログラミングがしたい』。今後は難問でこそ黒魔術的解法を調べてたいと思います。
toyboot4e結局
副作用の無いプログラムを分離して (効率を落としつつ) 簡単なプログラムにするのが無難かなぁ。速いプログラムを書くならやっぱり Rust なのか……
toyboot4eテンプレートが 1,000 行を超えた
大半はコメントです。 AtCoder ではコード行数の下三桁しか表示しないことを確認しました (スマホの場合) 。
#include の検討
クソデカテンプレートはコンパイル時間にも悪そうです。特定の問題以外で使用しないコードは include して使うのが良いかもしれません。エディタ上で Import 類も削減できて良さそう……
-
CPPと#includeを使った Stack Script は動きます。 -
HLS は
CPPと#includeを理解します。
#include を展開したい
stach ghc -- -E a/Main.hs の結果は gcc -E っぽいです。謎のコメントが含まれていてうーむ。。
これを動かしてみよう
./script extract problem/Template.hs の結果は #include が展開されている！ これなら AtCoder に提出できます。
gcc -E -P -w -xc -traditional
-
-E: pre process の結果を吐く -
-xc: 標準出力に書き出し -
-P: 出力に linemarkers (# ..) を含めない -
-w: 警告を出さない
-traditional がよく分からないですが、入れておいたほうが良さそうです。
Linux で動かしましたが、リポジトリの作者が macOS ユーザのようなので (pbcopy を使っている) macOS でも動きそうです。
#include のみを展開したい
しかし #include <file-not-on-atcoder> 以外は GHC が理解できるので #include だけ展開したい。ツールを作るか……！
toyboot4e
Deno で #include を展開する
すなわち ^#include な行をファイル内容で置換します。完全に初見なのでやっつけで……。そもそもドキュメントはどこなんだろう
#!/usr/bin/env -S deno run --allow-env --allow-read
// -*- mode: TypeScript; -*-
// Expands `#include` directive (only)
// TODO: Learn TypeScript and write better code
import { readLines } from "https://deno.land/std/io/mod.ts";
let out = "";
let err = "";
for await (let line of readLines(Deno.stdin)) {
if (line.startsWith('#include')) {
let file = line.split('"')[1];
try {
out += await Deno.readTextFile(file);
} catch (e) {
err += "unable to find file: " + file;
err += "\n";
}
} else {
out += line;
out += "\n";
}
}
if (err == "") {
console.log(out);
} else {
console.error(err);
}
あまりにも
foldしたい
というか Haskell でやるか？！
toyboot4e
Haskell で #include を展開する
効率は置いといてできました:
#!/usr/bin/env stack
{- stack script --resolver lts-16.31
--package bytestring --package containers --package extra
-}
module Main (main) where
import Control.Monad
import Data.Char
import Data.Either
import Data.Maybe
import Data.Monoid
import Data.List
import System.IO
{- ORMOLU_DISABLE -}
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Char8 as BS
import Data.Tuple.Extra
{- ORMOLU_ENABLE -}
-- | Taken from latest `extra`:
(!?) :: [a] -> Int -> Maybe a
xs !? n
| n < 0 = Nothing
-- Definition adapted from GHC.List
| otherwise = foldr (\x r k -> case k of
0 -> Just x
_ -> r (k-1)) (const Nothing) xs n
-- | Expands `#include` line with the file content.
translate :: Int -> BS.ByteString -> IO (Either BS.ByteString BS.ByteString)
translate i line
| not $ BS.isPrefixOf (BS.pack "#include \"") line =
return . Right $ line <> (BS.pack "\n")
| otherwise =
case (!? 1) $ BS.split '"' line of
Nothing ->
let err = "Unresovled import in line" ++ show i ++ ": "
in return . Left $ (BS.pack err) <> line
-- TODO: Handle exception
Just file -> Right <$> BS.readFile (BS.unpack file)
main :: IO ()
main = do
lines <- zip [0..] . BS.lines <$> BS.getContents
(errs, lines) <- partitionEithers <$> forM lines (uncurry translate)
BS.hPut stdout $ if null errs
then mconcat lines
else mconcat errs
#include すると HLS の調子が悪い
この辺の警告を消せませんでした:
- The import of 'Data.IORef' is redundant
- Defiend but not used
Package.yaml の ghc-options に -Wno* を追加したり <project>.cabal も更新したのですけれどね。むむむ
toyboot4e時間がある
すなわちエアプの時間が……！
2-3 finger tree
Haskell に特化した記事が Wikipedia にありました。 2 分木、 3 分木の亜種であり、ルートの位置を変えたり複数のルート持つことで、特定種別のアクセスに強くなる。内部実装は追えていないためエアプです。
3 分探索
2 分探索は単調増加する関数に対して有効です。 3 分探索は 2 次関数の極値などを見つけるために使えるようです。
問題によっては与えられた関数を紙の上で微分するだけで済みます
なるほど。区間
エアプだしこれだけでいっか……！ (完)
エアプのコツは
- 分かった気にならないこと (これは簡単のつもり)
- 分かった気になっていると思われないこと (これは難しい)
- 分かっていると思われないこと (これはこれで難しい)
toyboot4e
massive でタプルを格納できる UArray ができそう
内部的には vector や primitive を使っている風ですね。これなら タプルもしまえるしスライスもできる ！ 盆栽項目が増えてきた……！
TODO
生成・インデックス
- どの型クラス？
Manifest?
MArray の代わり
-
write,read,modify,swap, - new: ゼロ値初期化
-
createArray?
runSTUarray の代わり
- createArrayST っぽい
Freeze / thaw
- unsafeFreeze が型クラスの中にある
toyboot4eコンテナを受け取る時は、必ず Bang Pattern を使おう？
Bang Pattern が効く瞬間を初めて見ました。これでスピードが倍になります。 Unbox ばりの高速化ですね:
- let results = VU.create $ do
+ let !results = VU.create $ do
!fw <- newFW_ABC286E (\v -> (1, values VU.! v)) nVerts edges
runFW_ABC286E nVerts fw
return fw
{-# INLINE #-} は効くのだろうか
PrimMonad を使う関数は {-# INLINE #-} するべきのはずですが、今回は影響ありませんでした。
※ 高階関数も使っているので、複雑な状況ではあります
toyboot4eBang pattern で TLE / AC が分かれる他の例
AbC 273 D で出会いました。
こちらが問題のコードです:
- let (rmap, cmap) = VU.foldl' step s0 wallInput
+ let (!rmap, !cmap) = VU.foldl' step s0 wallInput
s0 = (IM.empty, IM.empty)
step (rs, cs) (r, c) =
( IM.insertWith IS.union r (IS.singleton c) rs,
IM.insertWith IS.union c (IS.singleton r) cs
)
少なくとも、 Vector を元にコンテナを作る場合は、絶対に ! を付けたほうが良い ですね。安全のため、 Vector を使う場合は必ず ! を付ける、くらいに考えておきます。
toyboot4e
入力を読み込む部分にも ! を付けたほうが良い
メモ使用量が倍になったりするので、 main 関数内にも ! をつけていきましょう。
StrictData 拡張
一応 ON にしておきますが、上記 TLE は StrictData 拡張だけでは回避できませんでした。
追記: こちらユーザ定義型のフィールドに ! を付けるだけのようです。
Strict 拡張
ほぼ何でも正格に評価してくれるはずですが、 where 句の思わぬ式が評価されて死んだりするのでやめておきます。かなり慣れが必要そう……。
toyboot4eタプルなのか……！
またも ! を付けまくって TLE 突破！ ! 無しだとタプルがサンクになるらしいので、その影響なのでしょう。テンプレートは ! だらけにしておきます。
toyboot4e
何でも ! が効くな……！
今まで ! が効かない例ばかり見つけていたのですが、ここ数時間で ! を付ければつけるほど速くなる例を何度も見ました。如実に影響している……！
toyboot4e
ST モナドの変換子が欲しい？
ST モナドの中にある 2 つの可変配列 (探索済み頂点と計算結果) を扱える文脈を作るには……？
TODO
toyboot4e
Data.Graph の使い方が分からない
Forest, Tree / Node がメシー。。もう topSort 以外使いません。
Buffer のテンプレートがある
爆速 Haskller の方が push_back できる vector のようなデータ型 (Buffer) をお持ちでした。リサイズはできないようですが、一度アロケートしたサイズ内なら追加・削除ができる……！
toyboot4e速くて強い頭脳
このペース (リズム？) 参考になる……！ Haskell を含む各種言語でゴルフできるのも強い。。
toyboot4e
do で () を減らすことができる
便利なときがあるかも？:
- input <- concat <$> replicateM 9 (map (== '#') <$> getLine)
+ input <- concat <$> replicateM 9 do map (== '#') <$> getLine
この例だと () を付けたほうが分かりやすいと思いますが、改行して延々と関数を作ることもできます。
toyboot4eリスト内包表記を List モナドで置き換え
リスト内包表記は builtin 構文 (のはず) なので、なんとなくズルをしている気分になります。一般的な do 記法に置き換えてみます。
コード
リスト内包表記:
let !pos =
[ [a, b]
| a <- range bounds_,
b <- range bounds_,
a /= b
]
リストモナド:
let !pos = do
a <- range bounds_
b <- range bounds_
guard $ a /= b
return [a, b]
guard の正体
Control.Monad#guard を見るに、 MonadPlus 上で定義されていますね:
Conditional failure of Alternative computations. Defined by
guard True = pure ()
guard False = empty
上の例に戻ると、 do 記法の各行はポイントフリースタイルで書かれた関数であり、コード上に現れないリストを文脈のように受け渡ししています。その値が一度 empty ([]) になると、以降の >>=, >> は何もしなくなり、したがって guard 関数は early return を表現できる。ということだったはず。
動作上も early return にしてほしいですが、モナドに関しては実行モデルよりも表現するところを読み取る方が重要かと思います。某 Effects で実行モデルも妥協無い形になると良いのですが、きっとまだまだ研究中ですよね。
do 記法の desugaring
let pos =
range bounds_ >>=
(\a -> range bounds_ >>=
(\b -> (if a /= b then pure () else []) >>=
(\_ -> return [a, b])))
pure () の部分が理解できません。文脈はリストではないのか……？ traceShow してみると、 a とか b はリストの中の単一の値を受け取っていますね。謎。。
あー >>= の中で concatMap している らしいです。 >>= をもう一段階 desugaring するべき ですね。モナド難しいよ！
IO モナドの empty
手続き型プログラミングでも early return 風の構文を、と思うと失敗します:
ghci> import Control.Applicative
ghci> empty :: IO ()
*** Exception: user error (mzero)
System.IO いわく:
Applicative IO
Takes the first non-throwing IO action's result. empty throws an exception.
MonadPlus IO
Takes the first non-throwing IO action's result. mzero throws an exception.
Applicative と Monad の関係を復習
Control.Monad を見るに、今の Haskell では Monad は Applicative の拡張として定義されています。 すごい H 本の説明は (未来予測していたとはいえ) 古い ということですね。
pure と return は同じ、 <*> と >>= の関係は以下:
m1 <*> m2
m1 >>= (\x1 -> m2 >>= (\x2 -> return (x1 x2)))
Applicative スタイルで書くとちょっとプロっぽい。
toyboot4e今こそすごい H 本を周回しよう！
リストモナド
-
concatMapはパタンマッチの失敗を許さない。 -
do記法ならfilterを兼ねることができる。さながらconcatMapFilterか。
toyboot4e
(a, b) -> ((a, b), (b, a))
dupe してしまう
ghci> import Data.Bifunctor
ghci> dupe x = (x, x)
ghci> swap (a, b) = (b, a)
ghci> second swap $ dupe (1, 2)
((1,2),(2,1))
Applicative スタイル
ghci> (,) <$> id <*> swap $ (1, 2)
こちらは汎用性が高く、入力の読み込みに使われている方もいますね:
(,) <$> int <*> int
自作の Union-Find を凍結可能にする
VU.create に相当する createUF 関数を作りたいと思います。
そういえば
読み出し中に木を書き換えないと高速化が望めないので、凍結はできませんでした。
toyboot4e昔解けなかった問題が解けるようになっている
実装能力と腕力向上のおかげです。特に既成ツールを使うだけで解ける問題はヌルっと AC できて良い感じです。 束の間ですが、 1 問 6 時間時代を突破して収穫の時間がやってきています。
toyboot4e当然今も解けない問題がある
6 時間コース、ですら終わらないか……！？ まあぼちぼち……
toyboot4eラムダ式の引数で bang patterns
\(a) のように書くか、 \ の後にスペースを入れます (こっちが推奨かも):
let f1 = \(!x) -> 2 * x
f2 = \ !x -> 2 * x
g1 = \(!x) !y -> x + y
g2 = \ !x !y -> x - y
IxIntMap, IxIntSet を作ってしまってもいいかもしれない
グラフの問題で boxing なデータ型を使用すると死にます。うまく次元を減らすべく考察するか、そもそも IntMap を Ix 越しのインターフェースで使うことで素直に解けるようになるはずです。
IxIntSet
作りかけていましたが、 Data.Ix に (i, i) -> Int -> i が無いので foldlIxIS を作れないことに気づいてしまいました。
また単ファイル内にモジュールを作れないため、関数名は *IxIS となっています。ちょっと使い勝手が悪すぎますね。 IxIS.* ならハイライトも良いのですが。。
さらに Ix では (Bool, Int) のようなキーに対応できないことは代わりありません。お蔵入りとします。
IxIntSet (作りかけ)
-- {{{ `IxIntSet`
-- | `IntSet` with `Ix` access
data IxIntSet i = IxIntSet (i, i) IS.IntSet
emptyIxIS :: Ix i => (i, i) -> IxIntSet i
emptyIxIS bounds_ = IxIntSet bounds_ IS.empty
fromListIxIS :: Ix i => (i, i) -> [i] -> IxIntSet i
fromListIxIS bounds_ is = IxIntSet bounds_ $ IS.fromList (map (index bounds_) is)
singletonIxIS :: Ix i => (i, i) -> i -> IxIntSet i
singletonIxIS bounds_ i = IxIntSet bounds_ (IS.singleton $ index bounds_ i)
insertIxIS :: Ix i => i -> IxIntSet i -> IxIntSet i
insertIxIS i (IxIntSet bounds_ is) = IxIntSet bounds_ $ IS.insert (index bounds_ i) is
deleteIxIS :: Ix i => i -> IxIntSet i -> IxIntSet i
deleteIxIS i (IxIntSet bounds_ is) = IxIntSet bounds_ $ IS.delete (index bounds_ i) is
memberIxIS :: Ix i => i -> IxIntSet i -> Bool
memberIxIS i (IxIntSet bounds_ is) = IS.member (index bounds_ i) is
notMemberIxIS :: Ix i => i -> IxIntSet i -> Bool
notMemberIxIS i (IxIntSet bounds_ is) = IS.notMember (index bounds_ i) is
nullIxIS :: Ix i => IxIntSet i -> Bool
nullIxIS (IxIntSet _ is) = IS.null is
sizeIxIS :: Ix i => IxIntSet i -> Int
sizeIxIS (IxIntSet _ is) = IS.size is
unionIxIS :: (Ix i, Ord i) => IxIntSet i -> IxIntSet i -> IxIntSet i
unionIxIS (IxIntSet bounds_ is1) (IxIntSet _ is2) = IxIntSet bounds_ (IS.union is1 is2)
intersectionIxIS :: (Ix i, Ord i) => IxIntSet i -> IxIntSet i -> IxIntSet i
intersectionIxIS (IxIntSet bounds_ is1) (IxIntSet _ is2) = IxIntSet bounds_ (IS.intersection is1 is2)
filterIxIS :: Ix i => (i -> Bool) -> IxIntSet i -> IxIntSet i
filterIxIS p (IxIntSet bounds_ is) = IxIntSet bounds_ (IS.filter p is)
-- foldlIxIS :: Ix i => (i -> a -> i) -> a -> IxIntSet i -> a
-- }}}
やはり Unbox な Set, Map が欲しいのだけれど
宛がありません。むむむ。。
toyboot4e緑 diff streak 週間を高く評価してくれるグラフ
それが Top player-Equivalent Effort (TEE) グラフ……！
うなぎ昇りじゃ
toyboot4eわしのテンプレートは 1,235 行 あるぞ
ふぉっふぉっふぉ
toyboot4e日報
練習では AtCoder の表示言語を英語にしてみる
本番では英語の誤字が多いので、練習だけの予定ですが英語にしてみます。
グラフの基礎をエアプ
無向グラフ上で連結成分を求めよ
DFS です。
木の直径を求めよ
全経路 DFS 2 回で得た両端の点の間の距離です。これはやったことがあります。
https://algo-logic.info/tree-diameter/
連結成分を求めよ
DFS か
DAG 上で強連結成分を求めよ
これは面白い話ですが、ヒープが必要そうで難しい気がします。 DFS するだけって本当……？？
事前知識:
- 強連結成分を 1 つの頂点に置き換えると DAG (directed asyclic graph) になります。
- 強連結成分の取得はトポロジカルソートと密接に関わります。
手順:
- 全頂点から帰りがけ順 (post order) の DFS を実施してラベリングする
(上流ほど高い値が与えられる) - ラベル値が大きい順に DFS を実施する
(上流の SCC から順に求まる)
https://hkawabata.github.io/technical-note/note/Algorithm/graph/scc.html
https://www.slideshare.net/hcpc_hokudai/study-20150107
トポロジカルソートせよ
cocnat . scc で求まりそうです？
グラフの基礎・典型が広すぎる
鉄則本をやってけんちょん本を読んだところでまだまだ。地道に蟻本を読んでみようと思います。
花粉のダメージを受けておる？
鈍くなっており分からぬ、、涙はあります
toyboot4e実装の目処がつきました
- DAG の topSort は postorder の DFS で求まる (けんちょん本)
- ループありの topSort は scc しか無さそう？
- scc に置ける番号の大きい順の走査とは、スタックから順に pop していくだけで済む
https://kanetai.hatenablog.com/entry/20140209/1391915669
スタックのおかげで簡単になりました。逆グラフは
このスタックの使い方を見るに、 scc の返値は連結成分毎ではないのかもしれません。それぞれの連結グラフの上流の成分から順番に切り出して渡してくれるイテレータのように見える時もあるかも。連結グラフが 1 つだけなら上流から順番に出してくれますが。
なお scc にはループの場合と双方向に繋ぎ合っている場合があり、 Data.Graph には区別する API もあるようなので参考にします。
toyboot4e緑 diff を埋めたが詰めが甘い
緑 diff streak 週間をやっていて、 ABC255 ~ ABC299 までの緑 diff の問題を埋めました。緑色まで上がるために十分な数の問題を解いたつもりです。
AtCoder Problems
しかし AC できるかと言われると 非常に厳しい 。考察成功率 9 割で実装力も足りていたつもりですが、なにかしらハマって AC できないという場合が多かったです。
先日の ABC 292 D もそうでした。なぜ DFS だと AC できないのか……？ 実装を間違えているかコーナーケースを取り零しているはずですが、自力で脱出できないのです。
次にやること
緑 diff を AC できるようになる訓練は、 Haskell 盆栽の趣旨とは異なります。本来やるべきなのは、高度なモナドを使いまくったズル過ぎる解法なのですが、そういうものが存在するのかも怪しく、普通の競プロをやるしかありません。
ならば高度な DP や高度なグラフアルゴリズムを解けるようになるのが、もっとも盆栽的だと思います。それほどの腕力を付けたころには、緑 diff も完投できるはず。高校物理が分からないなら大学物理で整理すればいいじゃないの精神で EDPC などやっていきます。
toyboot4eこういう問題を
十分解けるようになりたいですね (3 枚目が特に面白いです):
toyboot4e未だ Haskell 初心者
Reader モナドすら使ったことが無いのだ……！ 人のコードを数千行読めばレベルアップすると思うのですが、いつものゲーム開発方面で良いコードを探したいですね。
Streak を切らさない程度に例のやつをを読みますか……！
toyboot4eDeepL は僕より圧倒的に技術翻訳が上手い (比喩)
つまりそういうことか……！
toyboot4e関係式を効率的な計算に書き直してくれる
うおおおおおおお！ 遅延評価くん、再雇用するから戻ってきてくれー！！
手直しは必要みたいですが、あと一歩じゃん……！ コード生成には未来がありますね。こんな宣言型プログラミングは予想外でした。
toyboot4e小数の入力をパースするには
ByteString には readDouble が無いので、一旦こちらで:
map (read @Double) . words <$> getLine
ByteString のパース用型クラスを追加してもいいかもしれません。
toyboot4e実戦で E 問題を AC したぞ！
単なる配列のマージだったけれど…… (ナップサック問題をリストで解く方が難しい) 。 Haskeller としては有利な出題でした。 ABC 294 E
GPT くん……
GPT ペアプロは戦術
DSL Python / DSL 遅延評価 Haskell, アセンブリ C++
『実力』の幅が広がった
toyboot4e
水パフォでも +73 かぁ
入水は相当遠いなぁ……
現在のレーティングでは、パフォーマンス 1,400 を 10 連発しないと水色に辿り着きません
toyboot4eマイナ言語提出をざっと見 (ABC 294)
こうして見ると Haskeller は多いです。 Lisp 0 がショックで、 Fortran と OCaml が面白いですね (過疎だけれども……) 。
- CommonLisp: 0. えっ？
- D: つおい
- Erlang / Elixir: 0.
- Fortran: Haskell も使える人がいました。強いし面白い
- Idris: そもそも使用不能。 2023 update で追加してほしいですが……
- Kotlin: つおい
- Nim: つおい
- OCaml: 面白い
- Octave: こたつがめ先生
- Perl: こたつがめ先生
- Prolog: 0
- Racket: 0. えっ？
- Scala: Haskell より少ない
- Schene: 0. えっ？
- Standard ML: 0.
- Swift: Haskell より少ない
- Text: これはなに……？
- TypeScript: Haskell とタメ
- Unlamba: 0
- Vim: 実質 0
- VB: つおい (本当に強い)
- zig: 提出不能
- zsh, bc, dc: 0
toyboot4eARC に参加するべきか
レーティングが茶色以下の場合、 ARC 1 問目が 300 点の場合は出ても良さそうです。緑になったら出ない方が無難かも……
toyboot4e水色、というより水色になるための高度典型が欲しい
日報です。コンテンツのメモを書きます。
Youtube
あーだこーだー 73 回 (PAST 本上級編 の著者陣 + すべての黒幕):
緑色以上の人は PAST 本 (上級編) を買え！ とのこと。今週の ABC で緑色になるぞ！
本 (発売待ち)
3/27 に PAST 本上級編が発売します。難度的には鉄則本 < PAST 上級本 <= 蟻本 といった並びで、良い具合に間が埋まります。
内容としては、主に AtCoder の過去問を解説してくれる (あーだこーだーより) ようなので、ジャッジも利用可能です。これは楽しみです。
I use Kindle Scribe btw.
Podcast
Rebuild が来た！ うおおお！
機械と脳のハード的な違いは並列性にあるはずで、たかだか秒間数十億回の直列計算で人間の思考をエミュレートできてたまるか (TLE だろ JK) と思っていましたが、今何が起こっているのでしょうね？ 機械のアブダクションで Millennium Prize Problems を解きたい……が、解けても 100 年待たないと人には証明が認められないかもしれません。 (取らぬたぬきの (取らぬたぬきの (皮算用)) ……
ところで naoya さんは Dijkstra と遅延評価 DP の人だと思っていましたし、 miyagawa さんは natsumeg さんのキリストという認識でしたが、氷山の一角でした。僕も情報量の多い人間になりたい〜
toyboot4eLang test 2023
まだまだコンパイルエラーが直ってないようですが、次期環境を試すことができます:
-
ghc9.9.4! 僕のテンプレートは無修正で動いてくれました。 - Zig がいる！
- Idris がおらぬ！
- Racket, OCaml, Standard ML がいないんですが、消えるわけではないですよね……？
toyboot4e
区間 DP (O(N^3)
写経して AC. 初の青 diff でした。
解き方はこういう感じですか:
区間長 5 の計算には区間長 2 ~ 4 を用い、区間長 4 の計算には区間長 2 ~ 3 を用い、……。無効な計算を番兵で弾くのですが、オーバーフローしないように値を選ぶ必要があったりと煩雑です。もっと明示的な計算に切り替えたいところです。
あーだこーだーでは、鉄則本は初心者向けに特化しているという見方でしたが、初心者、初心者……？
toyboot4e類題 (EDPC N)
こちらは長さ 1 の区間もアリとして解きました。かなり様子が変わりますね……。汎用の関数を作るのは難しそうです。
toyboot4e類題 (TDPC I)
これは解けませんでした。ステップに工夫が必要です。
バッファ
- 2 次元配列
dpに区間[l, r]から取り除くことができるiwiの数を保存します-
succ (r - l) == 3 * dp ! (l, r)の場合、その区間の文字を削除することができます
-
ステップ
- 遷移 1: 区間
[l, m]と区間[succ m, r]の DP をマージする - 遷移 2:
l,[succ l, pred m],m,[succ m, pred r], rに分けて考える- 区間
[l, r]を完全削除できる場合は、以下を満たします:- 区間
[succ l, pred m]が全削除可能かつ区間[scc m, pred r]が全削除可能- なお長さ 0 の区間は削除可能であるとする
-
l,m,rを繋げるとi,w,iになる
- 区間
- 全削除できない場合は、サブ区間で最大の削除文字数を
dp ! (l, r)に記録します
- 区間
瞬殺されておる……！
この解答、 2ms だと……？！ しかもリストを使った解答です。一体何が起きているのか……！ (読まないけれど圧倒的な差を感じます)
toyboot4e類題 (ABC 285 E)
解説放送 では触れられていませんでしたが、区間 DP として捉え直した方が典型に落とし込めて簡単だと思います。
考え方
長さ n の休日サンドイッチにおける最大の稼ぎ
- 1 = 0 + 1
- 2 = 0 + 2 or 1 + 1
- 3 = 0 + 3 or 1 + 2
- 4 = ..
toyboot4e再帰関数がメンタルモデルにハマらない
平易な問題を解くのにもハックを使っています。まともな Haskell を書けているのか心配です。
例: fold (入力のループ処理)
たとえば foldl' の結果をリストに蓄えた場合、出来上がったリストは FILO となり、 reverse しなければキューのようには扱えません。
foldl' の替わりに再帰関数を使えば、 FIFO なリストを作ることもできます:
f (x:xs) = g x : f xs
でも僕が書きたいのは foldl' なんです！ 今は reverse していますが、何かしっくりくるループの道具が欲しいところです。
foldl' の代替
foldl' が合わない場合は、 mapAccumL とか State + mapM で Maybe を返せば良い気がしてきました。
- そのループは状態を持つことができる
- そのループは入力を map / filter できる
- そのループの出力は FIFO である
- Break はできない
なお break は定数倍の高速化なので、コンテストでは必要ありません。
再帰関数で入力処理
再帰関数では再帰を止めれば処理を打ち切れるので、 break できます。なら普段から再帰を使っておけば良いもののですが、 fold の方が『私はこういう者です』と伝えてくれる気がしていて、中々再帰関数に馴染めません。
toyboot4e昔と環境が変わった？
僕が bit DP と区間 DP を習得したら、この記事で言うところの水色コーダーの条件を満たしてしまう気がするのですが、そんなわけないですよね……？
当時の水色は今の緑後半ぐらいではという気がしてしまいます。 ABC 8 問体制の記事が欲しいところです。
toyboot4e
2 次元配列の traceShow (改良版)
map ではなく foldl' にしないと traceShow が評価されませんでした。わりと汚い……
traceMat2D :: (IArray a e, Ix i, Show e) => a (i, i) e -> ()
traceMat2D !mat =
let !_ = foldl' step () (range ys)
in ()
where
((!y0, !x0), (!yEnd, !xEnd)) = bounds mat
!xs = (y0, yEnd)
!ys = (x0, xEnd)
step !_ !y = traceShow (map (\ !x -> mat ! (y, x)) (range xs)) ()
PAST 上級本メモ
鉄則本より高度な内容で緑以上の人におすすめだとか。まだ茶色ですが、ざっと読んでエアプします。
6 月の PAST も受けてみようかな。
1. 2 分探索 [Done]
2 分探索の良問は解けるようになりたい……！
-
食塩水 (平均濃度の最大化)
- モンスターが魔力袋に見えるか！
- 2 分探索の判定問題を『濃度を X 以上にできるか』と設定する
- 平均の不等式は積の不等式であり、各項からの寄与の和の不等式に変形できる
\sum_i k_i x_i >= X \Leftrightarrow \sum_i (k_i - X x_i) >= 0 - よって判定問題は
O(N) O(N log(N) - 判定問題の中でさらに 2 分探索させられるやつとかもある……！
-
区間長の最小化
- 判定問題を greedy に解くことができる
- Yokan Party と同様のはず？
-
平均値・中央値の最大化
- ABC 236 E は特殊な制約が強い
- まず DP を考え、次元を減らす
- 平均値だけでも十分難しい
2. DP
DP のパタンは実は多くない、とか言いつつ最も分厚い章です。 最近解いた EDPC のおかげで既知の内容が多かった ことにびっくり……！
fold 型 [done]
1 つずつ入力を受け取って状態を進めます。ナップサック問題など。よくテーブルで説明されますが、 fold で解けます (配列 → 配列 を繰り返す) ので僕は fold 型と呼んでいます。
- 全探索が
a^n
先日の ABC295D は例外ですね…… (敗北)
部分問題で工夫が必要な場合
-
区間 DP (1)
dp[r]- 全探索は
O(2^{n-1}) -
dp[i] i -
dp[i] i - 事前処理はセグ木 (区間木) を使ってしまうとチートできる気がします。
- 全探索は
-
2 系列 (編集距離)
- 2 系列の添字を進めていく
- 遷移は左側から 1 文字捨てる、右側から 1 文字捨てる、両文字が一致するの 3 通り
- これは鉄則本のテーブルの説明が一番分かりやすいかな。
-
区間 DP (2)
dp[l][r]-
[l, r] dp[l][r]) - 長さ 1 のサブ区間、長さ 2 のサブ区間、 .. の順で求める
- 新しい区間はサブ区間をマージして埋めるか、左右の要素を足す形で新しい区間を作る
-
O(N^3)
-
-
集合 DP (bit DP)
- 巡回セールスマン問題
部分問題の高速化テクニック
-
部分問題に DP 配列の累積和が必要な問題
- 謎の TLE に見えるので要注意
- ロングジャンプ。なるほど……。和の範囲は尺取り方またはにぶたんで
- EDPC M など入力値が幅を取れるタイプのナップサック問題
- このぐらいなら fold で十分 (テーブル不要)
- 区間 DP + 累積和の場合はメモ化 DP では解けないんですよね
- ABC 183 E 難し過ぎる‥‥という程でもないのが凄い
-
行列累乗
WIP
3. 頻出テクニック
-
変数を固定する
変数を 1 つずつ決めていくと、残りの変数がO(N) O(log N) -
尺取り法
尺取り法も単調性に依存するため、尺取り法で解ける問題は 2 分探索やセグメント木で大体解けるんですよね。なるべく使わないのが競技的には良いかなと思っています。 XOR sum もセグ木の 2 分探索で解けるんじゃないかな……？
4. 頻出データ構造／アルゴリズム
5. ネットワークフロー
6. セグ木
7. セグ木 DP
読まないかも
8. 平面走査
読まないかも
9. チャレンジ
読まないかも
toyboot4e小説の読み上げが良い
競プロに合う Youtube/Podcast を切らしていたのですが、小説読み上げ (n 倍速) が良かったです。「ぐあっ!?」が『ぐ』『あ』『疑問符』になったりしますけれども意外と問題なし！
toyboot4e期待値の DP をどう解こう [DONE]
DP では数え上げが典型ですが、期待値をもとめよと言われたらどう解くか……？
解けぬ……！
コイン (定義に従って)
1/2 の確率で表が出るコインがある。 1 回表を出すまでの試行回数の期待値は？
定義に従って:
解析的には解けましたが、コンテスト向きではありません……
コイン (DP で)
同じ問題を DP で解いてみます。普通に状態遷移を考えるとこうです:
この図の最終遷移先 (表の数 1 ) で同様に状態遷移を考えると、実は DP 的な期待値の捉え方が現れます。
すなわち
これは競プロ外でも普通に使えるじゃん……！ 数学 A でやった記憶もありません。なんでこれで解けるんだ……
不動点？とか、上位の知識があればもっと見通しが良くなるのでしょうが。
Sushi
Sushi に戻ると、遷移先の状態から遷移元の状態へ逆向きに期待値が流れ込むように見て:
等式変形:
よし、これで解いてみます。
参考
この記事が最も助けになりました:
TODO
toyboot4eSushi AC!
2 日かけて AC しました。数学で躓くのは少し悲しい……！
改良
-
添字
-1の場合の番兵 (array の境界を広げる or 引数) -
fixで無名の再帰関数を作る
https://atcoder.jp/contests/dp/submissions/28651129
https://qiita.com/lotz/items/0894079a44e87dc8b73e -
メモ化不要の謎のイテレーション
依存する値よりも先に依存される値を計算する？
https://atcoder.jp/contests/dp/submissions/5890874
toyboot4etoyboot4e類題: ABC 263 E
上の 2 問と同様に、あるいは Nyaan 氏の解説 の通り、遷移先の期待値を元に遷移元の期待値を計算できる謎の技法で AC.. できず TLE しました。
なぜ TLE するのか、対策は
もしや N が大きいとメモ化 DP が通用しない……？ 遅延評価はしていないので大丈夫だと思いたいですが。
ああ部分問題が
AC!
他の問題もメモ化無しで解き直すべき
TODO
toyboot4eたぶん類題: TDPC J
TODO
toyboot4eBit DP (集合を添字とする DP) [DONE]
ゲーム問題から逃げつつ、新たな典型 DP へ。次の ABC で DP 出してくれないかな……！
考察
場合の和だけ数えて DP できんな〜と悩んでいました。色々な解説を読んで閃いたこととしては、ペア確定済みの女性の集合 (Int = bit 列) の集合 (IntMap) を状態に持って、 i 番目の男性を入力とし fold するだけで済みそうです。
TODO: 遷移を詰めて考える。 concatMap しつつ filter するだけで良い？
提出
IntMap を fold して TLE しました。 concatMap を fold に置き換えてもダメ！ なんか sparse な fold は通らないことが多いですね……
Vector でも TLE です。。確かに
状態のループで再挑戦
AC! 全く自力で解けた気がしない 。案外今までの DP で最難関かもしれません。
toyboot4e類題を解けるようになる方法。それは……
類題を解くことではないでしょうか (白目)
1 問解けば他の 5 問も解けるようになる、なんて上手い話は無さそうです (僕のスペックの場合) 。
toyboot4eEarly return が無くても戦えるようになってきた
return, break, continue が無くても構わない。なぜなら 5 段階ぐらいのネストには耐性ができてしまったから……！()
Rust に戻った際は、自分の生み出した { } の山を慌てて修正し勘を戻しました。
toyboot4e新たな弊害
for ループを読む気が無くなっていました……。恐ろしい。。
toyboot4e逆向きの range
[i1 .. i2] の記法は enumFromTo に desugaring されます。enumFromTo はi1 <= i2 の場合のみリストの要素を生成します:
i> [0..3]
[0,1,2,3]
> [3..0]
[]
[i1, i2 .. i3] の記法は enumFromThenTo に desugaring され、ステップ値を考えて配列を生成します:
i> [0, 2 .. 5]
[0,2,4]
> [0, -1 .. -5]
[0,-1,-2,-3,-4,-5]
[0 .. pred n] を逆順にイテレートするなら、 [pred n, pred (pred n), .. 0] と書くことになりそうです。ちょっと使いにくいですね。
toyboot4efold 型 DP でバッファが 2 次元の場合
たとえば ABC 281 D. 類題をサクッと実装できるようにノートしておきます。
昔解けた問題でも考察に時間がかかってヒヤヒヤします。とにかく考察に弱い。 ABC 全問再考察とかやるべきかもしれません……。
Vector で 2 次元のバッファを表す
準備:
let undef = -1 :: Int
input <- getLineIntVec
step 関数の添字を 2 次元にするだけ良くて、たしかこんな感じ:
let bounds = ((0, 0), (pred k, pred d))
let result = VU.foldl' step s0 input
s0 = VU.generate (\case 0 -> 0; _ -> undef) (rangeSize bounds_)
step vec x = VU.generate (\ikid -> f (ikid `quotRem` d)) (rangeSize bounds_)
where
f (ik, id) = undefined
UArray を使うには
Vector の generate に相当するのは listArray かと思います。おそらくこんな感じ:
let result = VU.foldl' step s0 input
s0 = listArray @UArray bounds_ (\case (0, 0) -> 0; _ -> undef)
step arr = listArray bounds_ f
where
f (ik, id) = undefined
未消化の典型メモ
まず視野に入れねば、とメモだけ……
解けたい典型
-
辞書順
- next / prev permutation
- S は辞書順で何番目 (転倒数と似ていて区間木で実装)
- 辞書順で n番目の文字列は何か
-
2 次元グリッドの座標圧縮
さっと解説を読んで理解できないのはやはり頭が悪いのか……？
https://pione.hatenablog.com/entry/2021/03/03/060451 - ☆ 食塩水
-
転倒数
考察ができるかは別の話 - Rolling hash
- 2-SAT
- LCA
-
二部マッチング
- 重み最大化一般マッチング
-
最大流量
- 最小費用流
- 最小カット
- Floor min (格子点の数)
- 主客転倒
- 燃やす埋める ？
- 包除原理 (激ムズ……)
- 中国剰余定理 (CRT)
- 3 分探索
- 拡張ユークリッドの互助法
避けている問題
-
ゲーム
- Nim ゲーム
- Grundy 数
高度典型
直帰の ABC で出たらしいですが影も拝めていない問題たち:
toyboot4etoyboot4eUpsolve
done. D は全探索の範囲絞り込み (
F: 公式解説で理解
書いてある通りだ……！
反転数の偶奇は互換操作(特定の 2 つの要素を選んで入れ替える操作) によって必ず反転します。
高橋君の行う操作では、1 回の操作で A,B に対してちょうど一度ずつ互換操作を行なっているため、A,B の反転数の総和の偶奇は高橋君の操作によって変化しません。
A,B が一致している時、反転数も等しいですから、その和は偶数となります。よって、最初の時点で反転数の総和が奇数である場合は一致させる事ができません。
問題タイトルの同時スワップは、初期状態で偶奇が不一致に場合、永遠に一致しないことを示している、また同じ要素が 2 つある場合、片側のみ反転数の偶奇が変化しない操作が可能と。
初期状態で偶奇が一致している場合は必ず一致させられる証明は一旦飛ばしています。 ABC って意味深だが無意味な制約で惑わしてくることが多いですよね。
E: scc (強連結成分) の手頃な実装が欲しい
ってなんじゃこりゃぁ！ Haskell 好き過ぎじゃ！
toyboot4eD のような数え上げのパターンの命名
何もやる気がしないときにこたつがめ先生を見ると、知性の強度に感化されて元気が出ますよ！ sed 瞬殺は中二的にかっこいいなぁ……
D では 2 つの約数のうち小さい方を列挙する、ということで『小列挙』と呼んでいるのが天才！ この呼び名は検索にも出ないので完全に造語だと思います。
D 問題は『小列挙』で探索の範囲を sqrt サイズにする問題だったと思うことにします。
約数問題、その典型解法とは
小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙昇竜拳小列挙小列挙小列挙小列挙小列挙小列挙小列挙小列挙
toyboot4e商列挙だった
すまんな……
toyboot4e転倒数 (inversion number)
ぐっ……典型！
転倒数とは
バブルソートに必要な swap の回数 (隣接要素の swap 回数)
-
パズルで鍛えるアルゴリズム力 P333
- 配列で見せてくれるのが良い
- 転倒数の偶奇 が問われる
- 2 次元の対象にも適用できるのか……！
- 考察についていけない
-
- 昇順になっていない値の組の数
- これを最後まで読めば実装は分かるな……！
転倒数の偶奇
偶奇が一致しているなら ∞ 回の操作の後に列を一致させられる、みたいな問題が多いようです。応用は類題を解いて身につけるしか……！
Segment tree (区間木) による実装
PrimMonad 実装にしておいて良かったです:
-- | Calculates the inversion number. Input must be in range [0, n - 1]
invNumVU :: VU.Vector Int -> Int
invNumVU xs = runST $ do
let !n = VU.length xs
!stree <- newSTree (+) n (0 :: Int)
-- NOTE: foldM is better for performance
!ss <- VU.forM xs $ \x -> do
-- count pre-inserted numbers bigger than this:
!s <-
if x == pred n
then return 0
else querySTree stree (succ x, pred n)
-- let !_ = traceShow (x, s, (succ x, pred n)) ()
modifySTree stree succ x
return s
return $ VU.sum ss
Binary index tree / Fenwick tree
TODO. 上の区間木実装で十分な気がします。
問題
- ABC 296 F: 証明が難しいか……！
-
Speedrun 001 - J:
invNumVUそのまま - ABC 296 F
- ABC 261 F
- ABC 264 D
- PAST #4 - K
- 典型 66
toyboot4e2 次元の座標圧縮
あまり出ない気はしますが教養として？
考え方
WIP
問題
toyboot4eグラフテンプレート強化
Data.Graph があまりにも使いにくいので、やはり自作する必要があります。
方針
トポロジカルソートや SCC ではグラフの全頂点を訪問します。効率を考えて、探索済み頂点は (IntMap ではなく) MVector に保存します。 MVector の方が実装も簡単になると思います。
実装
-
components (連結成分)
単なる DFS で良い気がしてきました。 -
treeDiameter (木の直径)
2 回のBFS木のため DFS で十分です -
topSort (トポロジカルソート)
けんちょん本曰く postorder な DFS の出力です。 -
scc (強連結成分)
Postorder な DFS の出力、すなわち topSort の出力を逆グラフ上の preorder な DFS に与えます。参考:
SCC からループ成分を抽出する
SCC の結果において、長さ 2 以上の頂点は常にループ (相互に到達可能) です。長さ 1 の頂点は、自己ループもしくはループではないです。
Data.Graph の SCC はその点を考慮して
SCC = AsyclicSCC v | CyclicSCC vとなっていますね。
ループ成分を抽出する関数を sccCycles としました。 これにて ABC 296 E を AC!:
sccCycles :: Array Int [Int] -> [[Int]]
sccCycles graph = filter f $ scc graph
where
-- self-referencial loop only
f [!v] = v `elem` (graph ! v)
f !_ = True
まだまだテストしていきます。
toyboot4e自作のトポロジカルソートが少し速かった
ABC 291 E で試してきました。
- 自作版: 344 ms
- Data.Graph.topSort 版: 449 ms
自作の topSortの方が速い理由としては、憶測ですが、
-
reverseしていない - 探索済み頂点を
Vectorに保存している
toyboot4e
自作 scc のさらなるテスト
最近、半年来の区間木のバグに気付きました。 scc は信頼できるものであってほしい……！
Functional graph
SCC でループを検出できます。 scc に慣れていると Union-Find 以上に簡単になります:
もっと複雑なもの
AtCoder Tags で 探してみました。
-
☆ ABC 245 F
余事象で答えようとして WA. どの問題でも基礎の不足を感じます。 -
2-SAT? (とは)
toyboot4e木のトポロジカルソートが典型？
toyboot4e
org-roam 始めました
org-roam-ui がグラフを表示してくれます:
- ノード = ファイル (
.org) - 辺 = リンク (
[[<file-id>][<title>]]形式のもの)
内容が充実したら公開したいと思います。 公開している人 もいますね。
toyboot4eHaskell は AtCoder ガチ言語だったかもしれない
天下の Common Lisp はスタックのサイズから四苦八苦しているようです。言語アップデートも無し。隣の芝生が枯れて見えますよ……！
ヒューリスティックで使ってみたかったのですが、 Haskell 以上に無謀な気がします。また半年這いつくばる勇気は無いかもです……。
でもこんなの買い始めたらたまらんだろうな〜……
toyboot4eたとえば AtCoder 向きではない言語
最近 AtCoder に上陸した Emacs Lisp とかですかね……！
1 行目の set-buffer が異彩を放っており、周りの言語がネイティブ実行される中、テキストエディタと融合しています。 exit は kill-emacs ですよ。いよっ、 Lisp エイリアン！
僕の知る限り一番難しいプログラミング言語は batch ファイルですが、 Emacs Lisp もなかなかですよね……。
toyboot4eV や Zig もやってくる！
どちらも C の単ファイルにトランスパイルして実行できるはずですが、ネイティブ環境があるのは良さそうです。
toyboot4e基本は変わらない (n 敗)
全探索をベースに、ちょっと効率の良い部分問題の解法を考えられたら、大抵の問題は解けるんじゃないでしょうか (敗北) 。
基本を変えない
一生灰のままコンスタントな成果を出し続けるのも戦略としてはアリだと思います。全然面白くないけれど……
toyboot4e
再帰関数 vs foldr vs reverse $ foldl' ..
リストで FIFO をやる場合、どれが最も効率が良いか。
TODO
map の 3 通りの実装
上記リンクからパクってきます。
- 再帰関数
map' :: (a -> b) -> [a] -> [b]
map' !_ [] = []
map' !f (!x:xs) = f x : map' f xs
foldr
map'' :: (a -> b) -> [a] -> [b]
map'' !f = foldr (\ !x !acc -> f x : acc) []
reverse $ foldl'
map''' :: (a -> b) -> [a] -> [b]
map''' = reverse $ foldl' (\ !acc !x -> f x : acc) []
ModInt p [Done]
繰り返し二乗法で mod を取る処理を自動化したいです。
※ 繰り返し二乗法は相当重いので、繰り返し二情報が不要なアルゴリズムで ModInt を使うと TLE になる危険性があります。たとえば rolling hash.
ModInt p を作ろう
ModInt のフィールドに法 (modulus) を入れるよりは、 ModInt 型自体に法の値を含ませたいです。理由は、
- 異なる法の
ModInt同士を計算できないようにしたい -
NumクラスのfromInteger :: Integer -> ModIntを実装したい
そのため ModInt p 型を作り、 p 型から法の値が得られるようにしたいです。
pを素数に限定できると尚良いですが。
定数を型で渡す (Proxy)
m 型から値を得る関数とは f::<T>() に相当します。 Haskell の関数は第一に引数から多相のパラメータを推論するため、このように引数 0 の多相関数を作ることはできません。替わりに f (Proxy @a) のように関数 f に Proxy a の値を与えることで、間接的に型パラメータ a を渡すことができます。
定数を表す class を作ってみます:
-- | Type level constant `Int` value.
class TypeInt a where
typeInt :: Proxy a -> Int
使い方:
data MyModulus = MyModulus
instance TypeInt MyModulus where
typeInt _ = 1_000_000_007
typeInt (Proxy @MyModulus)
-- => 1000000007
ModInt MyModulus のコンストラクタも追加しておきます:
modInt :: Int -> ModInt MyModulus
modInt = ModInt
TODO: TypeNats
先程の TypeInt ですが、 GHC のモジュールに TypeNats があるので置き換えます。
Show インスタンスの実装
そのまま解答に利用できるよう、 Int の Show に委譲しました:
-- | `Int` where modulus operation is performed automatically.
newtype ModInt p = ModInt { toInt :: Int }
deriving (Eq)
instance Show (ModInt p) where
show = show . toInt
Num クラスの実装 (+, * など)
ModInt p に Num クラスを実装してきます。演算心の実装はスムーズに進むと思います。
Num のメンバはなｍだっけ？ instance Class Type where を書いた時点で、言語サーバのコードアクションにより関数の placeholder を生成可能です。
instance TypeInt p => Num (ModInt p) where
(ModInt !x1) + (ModInt !x2) = ModInt $ (x1 + x2) `mod` typeInt (Proxy @p)
(ModInt !x1) * (ModInt !x2) = ModInt $ (x1 * x2) `mod` typeInt (Proxy @p)
negate (ModInt !v) = ModInt $ (-v) `mod` typeInt (Proxy @p)
abs = id
signum _ = 1
fromInteger = ModInt . fromInteger
Fracitonal クラスの実装 (/ など)
ModInt p に Fractional クラスを実装します。
instance TypeInt m => Fractional (ModInt p) where
-- reciprocal of x (inverse of x)
recip (ModInt !x) = ModInt $ invModF x (typeInt (Proxy @p))
fromRational !r = ModInt n / ModInt d where
n = fromInteger $ Ratio.numerator r
d = fromInteger $ Ratio.denominator r
invModF は繰り返し二乗法と素数 mod (確か Fermet's little theorem) で実装されています。
toyboot4e
Debug-only な traceShow [DONE]
traceShow を使うと stderr 出力で printf デバッグができます。しかし print が長いと TLE を起こすため、提出前に確実にコメントアウトしなければなりません。
CPP 言語拡張
CPP 言語拡張を有効化すると #ifdef が書けます。 #ifdef を使えば、提出時には確実に traceShow を消去できます:
-- {{{ Debug-only utilities
#ifdef DEBUG
dbg :: Show a => a -> ()
dbg !x = let !_ = traceShow x () in ()
#else
dbg :: Show a => a -> ()
dbg = const ()
#endif
-- }}}
DEBUG 属性を有効化する方法ですが、stack の引数に --ghc-options "-D DEBUG" を渡せば有効化できると思います。
Stack script として DEBUG 属性を有効化する
Stack script の場合はコメントで stack への引数が書けるので、 define を追加しました:
#!/usr/bin/env stack
{- stack script --resolver lts-16.31
--package array --package bytestring --package containers --package extra
--ghc-options "-D DEBUG"
-}
ローカルでは stack script として実行されるため DEBUG 属性が有効化され、ジャッジの際は無効になります。
toyboot4eDebug-only な assertion
Haskell にも assert 関数があります:
1. Control.Exception.assert を使う
Assertion に使った式が表示できない、と元の記事にもありました。まあこれで十分だと思います。
- エラー関数表示
- エラー行表示
Haskell のコンパイルコマンドは ghc -o a.out -O2 {dirname}/{filename} なので、 -fignore-asserts は指定されていません。ローカルで有効、ジャッジでは無効な asset を作るには、やはり DEBUG フラグを使おうと思います。
2. CPP 言語拡張でマクロを作って式表示
こちらは assertion に使った式も表示できそうですが、 , を式に含められないなど構文に制限がかかるようです。
3. Template Haskell で assertion
これはやめておきましょう……
toyboot4eRolling Hash [Done]
文字列 → 数値列 → B 進数 (素数 mod) 累積和 → スライス時に桁を調整
データ型の追加
ローリングハッシュは必要なデータ数と計算ステップが多いためバグりやすいです。オブジェクト指向っぽく集約と隠蔽で問題を分解しましょう。
案外実戦でも、データ型を作った方が手戻りが無くて速いかもしれません。盆栽力も実装力の内。そして盆栽は得意のはずなのだ……！
-
ModInt
mod計算を隠して実装を簡単にします。 -
RollingHash b p
B^n -
HashSlice
ハッシュ値と合わせて長さを記憶しておけば、スライス同士の連結ができます。-
consHashSlice -
catHashSlices
-
TLE 対策
繰り返し二乗法を使わない実装にしましょう！！！ (重要)
演習
-
ABC 284 F
繰り返し二乗法の rolling hash で TLE, 位取りの方法を見直して AC!
toyboot4eわしのテンプレートは 1,500 行あるぞ
ふぉっふぉっふぉ (古いやつは消さないと……)
ロードも困難なほど長いソースを提出する人たちもいる
サーバ攻撃かと思いましたが、他コンテストにおける撃墜対策なのかも？ 何にせよ良いものではなさそうです。
toyboot4e
1 次元の MVector に対する 2 次元の view [TODO]
添字が二次元 (Int, Int) なグラフの探索済み頂点を MVector に収納したい！
1 次元の MVector を Vector (MVector Bool) へと変換するコードを見つけました:
vis <- mLinToMat n n <$> VUM.replicate (n*n) False
しかし実装を追うのは難しい…:
IL(mLinToMat) :: (VGM.MVector v a) => Int -> Int -> v s a -> V.Vector (v s a)
mLinToMat h w lvec = vEvalElemsId $ V.generate h (\i -> VGM.slice (i*w) w lvec)
IL(vEvalElemsId) :: (VG.Vector v a) => v a -> v a
vEvalElemsId = vMapFoldl (\ !_ !x -> (x,())) ()
IL(vMapFoldl) :: (VG.Vector v b, VG.Vector v c) =>
(a -> b -> (c,a)) -> a -> v b -> v c
vMapFoldl f a
= VG.unstream . VFB.inplace (streamMapFoldl f a) id . VG.stream
TODO? (Array なら Ix をそのまま使えるしなぁ)
toyboot4eIdris 2 を垣間見るか [WIP]
正格評価がデフォルトな Haskell として Idris2 を C にトランスパイルしてコード提出してみたい！ まずは NixOS で環境構築してみます。
失敗するかもですが。
Idris について
Idris1 の本があります。
I use Kindle Scribe btw.. のコーナーです。
ところで僕は Type-Driven Development with Idris を買って Kindle Scribe で 25% 程度読んでいます。これはマウントポイントです。みなさん Kindle Scribe は持っていない確率が高いですからね。 Remarkable 派は、国内で見たことが無いですが、密かにライバルと認識しています。
idris2 0.6
configuration.nix に idris2 パッケージを追加してインストールできます。ただ idris2 自体 pack (idris2-pack) についてくるようなので、 configuration.nix から入れないほうが良いかもしれません。
idris2-pack
グローバルインストールは NixOS では上手く行かない気がするのですが、やってみます。
$ nix-shell -p gmp
> bash -c "$(curl -fsSL https://raw.githubusercontent.com/stefan-hoeck/idris2-pack/main/install.bash)"
もし成功したらパスを通したりパッケージを追加したり……
Package Collection : nightly-230408
Idris2 URL : https://github.com/idris-lang/Idris2
Idris2 Version : 0.6.0
Idris2 Commit : a75161cb2021136d4c87e65f25a1d4bc50a7279f
Scheme Executable : scheme
Pack Commit : 6ff0f1ac46fd0d8ad13b827cb96ece7187730d8d
Installed Libraries : base
contrib
idris2
linear
network
prelude
test
成功しました。動くかな
エディタサポート
$ pack install-app lsp
Emacs では idris2-mode.. ではなく idris-mode を使った方が良さそうですね。
ひとまず昔の設定を有効化して……
(leaf idris-mode
:mode "\\.l?idr\\'"
:hook lsp-deferred
:custom
(idris-interpreter-path . "idris2")
:after lsp-mode
:config
(add-to-list 'lsp-language-id-configuration '(idris-mode . "idris2"))
;; (with-eval-after-load 'lsp-mode ;; LSP support for tlp-mode
(lsp-register-client
(make-lsp-client
:new-connection (lsp-stdio-connection "idris2-lsp")
:major-modes '(idris-mode)
:server-id 'idris2-lsp)))
ipkg
言語サーバを動かすためには .ipkg ファイルが必要だとか。 チュートリアル や リファレンス を参照しつつ……
$ mkdir try-idris2
$ cd try-idris2
$ git init
$ idris2 --init ✘ 255 main
Package name: try-idris2
Package authors: toyboot4e
Package options:
Source directory: src
$ ls
try-idris2.ipkg
$ cat try-idris2.ipkg
try-idris2.ipkg
package try-idris2
-- version =
authors = "toyboot4e"
-- maintainers =
-- license =
-- brief =
-- readme =
-- homepage =
-- sourceloc =
-- bugtracker =
-- the Idris2 version required (e.g. langversion >= 0.5.1)
-- langversion
-- packages to add to search path
-- depends =
-- modules to install
-- modules =
-- main file (i.e. file to load at REPL)
-- main =
-- name of executable
-- executable =
-- opts =
sourcedir = "src"
-- builddir =
-- outputdir =
-- script to run before building
-- prebuild =
-- script to run after building
-- postbuild =
-- script to run after building, before installing
-- preinstall =
-- script to run after installing
-- postinstall =
-- script to run before cleaning
-- preclean =
-- script to run after cleaning
-- postclean =
$ mkdir src
$ cat <<EOS > src/Main.idr
main :: IO ()
main = "Hallo"
EOS
エディタで開くとあっさりエラー表示が出ました。 main 関数の前に、 Haskell で言う module Main where みたいなパッケージ宣言が必要なのでしょう。幸先良いですね。
実行など試していきます。
toyboot4eWIP
先程のエラーは main :: IO () を main : IO () に修正して解消されました。
REPL から実行する
競プロ勢は言語を問わず REPL からソース実行している気がします。それが基本ということでしょうか。
$ idris2 src/Main.idr
:exec main
"Hello"$
なるほど "Hello" になっていますね。 putS からの C-n で putStrLn に補完……
補完してほしい
してほしかった。設定不足かキーバインド不足か未実装なのか……
プロジェクトの実行ファイルをビルド・実行する
cargo run はどこ…… (Idris 界隈は Make 派が多かったっけ) 。
-
pack -o
C バックエンドを使いたい (1)
使い方を調べたくないチョップ (・ω)))) > > > >
これで一応ビルドできるかな
$ nix-shell -p gmp --command 'idris2 --cg refc src/Main.idr -o c-main'
$ ls build/exec
c-main* c-main.c c-main.o _tmpchez* _tmpchez_app/
Print するだけのプログラムが 570 行。依存が増えたらどうなるか分かりませんが、提出・実行してみましょう。
words 関数が無い……？
分かりました (言ってみたいだけ) 。
module Main
import Data.String
partial
main : IO ()
main = do
[a] <- map cast . words <$> getLine
[b, c] <- map cast . words <$> getLine
print $ a + b + c
getLine >>= print
でトランスパイル結果が外部ファイル (runtime.h や idris_support.h とその実装) に依存しているため実行不能と……。 embed <ファイル名> とか standalone で検索していくしかありません。
C バックエンドを使いたい (2)
使い方を調べたくないチョップ (・ω)))) > > > >
C の単ファイル生成方法を調べるか考えます。
toyboot4eWA から AC までのコード差分を検索するサービス
これは欲しかったやつ！
toyboot4e私の戦闘力は 777 です
ABC 5 完でした。考察成功！ 言語によっては Set に deleteMinFind が無いようなので大変そうです。意外と Haskell の方が死角が無いのかもしれない……
知識が活かされる問題でも無かったけれど、今後も典型盆栽をやっていきます。高度典型で高パフォーマンスを狙いたい。
toyboot4eWIP: 箱詰め問題、主客転倒、包除原理
ABC 297 F を解くぞ！
用語
-
包除原理
- 集合が 2 つの場合
線形な f に対してf(X) = f(A) + f(B) - f(A \cap B) A \cup B = X - 一般の場合
TODO
- 集合が 2 つの場合
-
主客転倒
\sum_i f_i(\{ x_j \}_j) = \sum_j g(x_j)
ABC 290 E
包助原理から逃げて主客転倒をやりました。 TLE の回避も必要な良問です。こういう問題が解けると良いのですけれどね。
ABC 003 D
まずは簡単な類題から。紙の上ですら全然分からん……！
ABC 297 F
toyboot4e
MVector や MArray の累積和を求める\には
fold で済む問題なら scanl' で済む話ですが、どうしても可変配列が必要な場合に備えてモナディックな累積和取得を考えたいです。 forM_ を回すのが意外としんどい……
……と思いきや 1 行で済みそうですね。
VU.foldl' (+) (0 :: Int) <$> VU.mapM (VUM.read dp) (vRange 0 (vLength dp - 1))
基本 MVector を使うべきではない
2 次元の DP でも scanl' で解けることは多く、 immutable な Vector の累積和は簡単に計算できます。まずは MVector を避けられるか考えるべきです。
toyboot4e人のテンプレートを読む
黒魔術 Haskell を避けて通れば、素直で良さそうなコードが目に入ります。
- Vector の stream の使い方
-
unwordsのByteStringBuilder版 - 純粋関数版・モナディック関数版の実装の統一 (2 分探索など)
純粋関数版を runIdentity $ モナディック版 として実装します
Haskell すきー氏のコードから見ていくぞ！
toyboot4eコードリーディング #1
人のコードを貼りまくって権利的に問題無いでしょうか。
Stream
vector の stream は配列に特化していて異常に速いらしいです。生の vector を使っても stream fusion により実行結果は変わらないの かも しれませんが、イテレータのメンタルモデルを強調できて良い気がします。
まずは import:
import qualified Data.Vector.Fusion.Bundle.Monadic as MB
import qualified Data.Vector.Fusion.Bundle.Size as MB
import qualified Data.Vector.Fusion.Stream.Monadic as MS
Stream で範囲を表します:
stream :: (Monad m) => Int -> Int -> MS.Stream m Int
stream !l !r = MS.Stream step l where { step x | x < r = return $ MS.Yield x (x + 1) | otherwise = return MS.Done; {-# INLINE [0] step #-}}
{-# INLINE [1] stream #-}
INLINE [1]の記法は inline pragma の phase 指定らしいです。特に stream を扱う場合は重要そうですが未読です。
逆向きの stream:
-# INLINE [1] stream #-}
streamR :: (Monad m) => Int -> Int -> MS.Stream m Int
streamR !l !r = MS.Stream step (r - 1) where { step x | x >= l = return $ MS.Yield x (x - 1) | otherwise = return MS.Done; {-# INLINE [0] step #-}}
{-# INLINE [1] streamR #-}
Delta 値を指定できる stream:
stream' :: (Monad m) => Int -> Int -> Int -> MS.Stream m Int
stream' !l !r !d = MS.Stream step l where { step x | x < r = return $ MS.Yield x (x + d) | otherwise = return MS.Done; {-# INLINE [0] step #-}}
{-# INLINE [1] stream' #-}
rep :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep n = flip MS.mapM_ (stream 0 n)
{-# INLINE rep #-}
rep1 :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep1 n = flip MS.mapM_ (stream 1 (n + 1))
{-# INLINE rep1 #-}
rev :: (Monad m) => Int -> (Int -> m ()) -> m ()
rev n = flip MS.mapM_ (streamR 0 n)
{-# INLINE rev #-}
rev1 :: (Monad m) => Int -> (Int -> m ()) -> m ()
rev1 n = flip MS.mapM_ (streamR 1 (n + 1))
{-# INLINE rev1 #-}
Shift
これは全く読めない:
infixl 8 `shiftRL`, `unsafeShiftRL`
shiftRL :: Int -> Int -> Int
shiftRL = unsafeShiftRL
{-# INLINE shiftRL #-}
unsafeShiftRL :: Int -> Int -> Int
unsafeShiftRL (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)
{-# INLINE unsafeShiftRL #-}
ByteStringBuilder
改行区切りで vector を出力:
unlinesB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
unlinesB f = G.foldr' ((<>) . (<> endlB) . f) mempty
空白区切りで:
unwordsB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
unwordsB f vec | G.null vec = mempty | otherwise = f (G.head vec) <> G.foldr' ((<>) . (B.char7 ' ' <>) . f) mempty (G.tail vec)
Vector のみならず、
Foldable全般に実装してみたいです。それとも Vector に限定したほうが高速になるのでしょうか。ガバベンチを作りたい。
連結:
concatB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
concatB f = G.foldr ((<>) . f) mempty
mconcatではなく？
特化した BSB (行列 (各行は空白区切り), グリッド (各行は単なる concat), 長さ付き vector):
matrixB :: (G.Vector v a) => Int -> Int -> (a -> B.Builder) -> v a -> B.Builder
matrixB h w f mat = F.foldMap ((<> endlB) . unwordsB f) [G.slice (i * w) w mat | i <- [0 .. h - 1]]
gridB :: (G.Vector v a) => Int -> Int -> (a -> B.Builder) -> v a -> B.Builder
gridB h w f mat = F.foldMap ((<> endlB) . concatB f) [G.slice (i * w) w mat | i <- [0 .. h - 1]]
sizedB :: (G.Vector v a) => (v a -> B.Builder) -> v a -> B.Builder
sizedB f vec = B.intDec (G.length vec) <> endlB <> f vec
Yes / No:
yesnoB :: Bool -> B.Builder
yesnoB = bool (B.string7 "No") (B.string7 "Yes")
Char7 は ASCII, Char8 は UTF-8 らしいです。どうせ ascii 文字しか使わないので
string8よりstring7の方が良さそうです。
uncurry (<>) . bimap 的なもの:
pairB :: (a -> B.Builder) -> (b -> B.Builder) -> (a, b) -> B.Builder
pairB f g (x, y) = f x <> B.char7 ' ' <> g y
String → Builder:
showB :: (Show a) => a -> B.Builder
showB = B.string7 . show
showLnB :: (Show a) => a -> B.Builder
showLnB = B.string7 . flip shows "\n"
shows は知らなかった。
flip show "\n"で\x -> show x ++ "\n"と等価になりそうです。++よりも効率が良かったりするのでしょうか。
改行に名前を付けておくのは良いですね:
endlB :: B.Builder
endlB = B.char7 '\n'
{-# INLINE endlB #-}
出力:
putBuilder :: (MonadIO m) => B.Builder -> m ()
putBuilder = liftIO . B.hPutBuilder stdout
putBuilderLn :: (MonadIO m) => B.Builder -> m ()
putBuilderLn b = putBuilder b *> putBuilder (B.char7 '\n')
MonadIO は
IOまたはその合成のようです。
座標関係？ [TODO]
これは何だろう:
neighbor4 :: (Applicative f) => Int -> Int -> Int -> (Int -> f ()) -> f ()
neighbor4 h w xy f = when (x /= 0) (f $ xy - w) *> when (y /= 0) (f $ xy - 1) *> when (y /= w - 1) (f $ xy + 1) *> when (x /= h - 1) (f $ xy + w) where { (!x, !y) = quotRem xy w}
{-# INLINE neighbor4 #-}
2 分探索
モナディックな 2 分探索。必ず境界の左側の添字を返してるっぽい:
binarySearchM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int
binarySearchM low0 high0 p = go low0 high0 where { go !low !high | high <= low = return high | otherwise = p mid >>= bool (go (mid + 1) high) (go low mid) where { mid = low + unsafeShiftRL (high - low) 1}}
{-# INLINE binarySearchM #-}
なぜ
unsafeShiftRLなのか？ 保留……
これは興奮しましたが純粋関数はモナディック関数の特殊版なんですね:
binarySearch :: Int -> Int -> (Int -> Bool) -> Int
binarySearch low high p = runIdentity $ binarySearchM low high (return . p)
{-# INLINE binarySearch #-}
境界の左側を取るのが lowerBound, 右側を取るのが upperBound ということですね。単調減少の場合は逆になるのかもですが:
lowerBound :: (Ord a, G.Vector v a) => v a -> a -> Int
lowerBound !vec !key = binarySearch 0 (G.length vec) ((key <=) . G.unsafeIndex vec)
{-# INLINE lowerBound #-}
upperBound :: (Ord a, G.Vector v a) => v a -> a -> Int
upperBound !vec !key = binarySearch 0 (G.length vec) ((key <) . G.unsafeIndex vec)
{-# INLINE upperBound #-}
Encode? [TODO]
基数ソートとは？:
radixSort :: U.Vector Int -> U.Vector Int
radixSort v0 = F.foldl' step v0 [0, 16, 32, 48] where { mask k x = unsafeShiftRL x k .&. 65535; step v k = U.create $ do { pos <- UM.unsafeNew 65537; UM.set pos 0; U.forM_ v $ \ x -> do { UM.unsafeModify pos (+ 1) (mask k x + 1)}; rep 65535 $ \ i -> do { fi <- UM.unsafeRead pos i; UM.unsafeModify pos (+ fi) (i + 1)}; res <- UM.unsafeNew $ U.length v; U.forM_ v $ \ x -> do { let { !masked = mask k x}; i <- UM.unsafeRead pos masked; UM.unsafeWrite pos masked $ i + 1; UM.unsafeWrite res i x}; return res}}
{-# INLINE radixSort #-}
何の話だろう:
encode32x2 :: Int -> Int -> Int
encode32x2 x y = unsafeShiftL x 32 .|. y
{-# INLINE encode32x2 #-}
decode32x2 :: Int -> (Int, Int)
decode32x2 xy = let { !x = unsafeShiftRL xy 32; !y = xy .&. 4294967295} in (x, y)
{-# INLINE decode32x2 #-}
パーサ関係？ [TODO]
未読:
uvectorN :: (U.Unbox a) => Int -> PrimParser a -> PrimParser (U.Vector a)
uvectorN = vectorN
{-# INLINE uvectorN #-}
bvectorN :: Int -> PrimParser a -> PrimParser (V.Vector a)
bvectorN = vectorN
{-# INLINE bvectorN #-}
vectorN :: (G.Vector v a) => Int -> PrimParser a -> PrimParser (v a)
vectorN n f = do { (e, o) <- viewPrimParser; pure $ G.unfoldrN n (pure . runPrimParser f e) o}
{-# INLINE vectorN #-}
runSolver :: (a -> IO ()) -> PrimParser a -> IO ()
runSolver = withInputHandle stdin
PrimParser [TODO]
これは何だろう。入出力の最適化は必ず効くためか、気合が入った効率化と抽象化が両立されている予感がします]:
newtype PrimParser a = PrimParser{runPrimParser# :: Addr# -> Addr# -> (# Addr#, a #)}
PrimParser を返す関数
xyz <- (,,) <$> int <*> int <*> int のように、パーサの組み合わせができたはずです。上手い。
int :: PrimParser Int
int = PrimParser $ \ e p -> case runPrimParser# intP e p of { (# p', x #) -> (# plusAddr# p' 1#, x #)}
{-# INLINE int #-}
uint :: PrimParser Int
uint = PrimParser $ \ _ p -> case wordP# p 0## of { (# p', x #) -> (# plusAddr# p' 1#, I# (word2Int# x) #)}
{-# INLINE uint #-}
uint1 :: PrimParser Int
uint1 = PrimParser $ \ _ p -> case wordP# p 0## of { (# p', x #) -> (# plusAddr# p' 1#, I# (word2Int# x -# 1#) #)}
{-# INLINE uint1 #-}
double :: PrimParser Double
double = PrimParser $ \ e p -> case runPrimParser# doubleP e p of { (# p', x #) -> (# plusAddr# p' 1#, x #)}
{-# INLINE double #-}
char :: PrimParser Char
char = PrimParser $ \ _ p -> case indexWord8OffAddr# p 0# of { w8 -> (# plusAddr# p 1#, B.w2c (W8# w8) #)}
{-# INLINE char #-}
など。
IntMod, ガロア域? [TODO]
これは一体どういうことだッ
type IntMod = GF 998244353
何が起きているッ
newtype GF (p :: Nat) = GF{unGF :: Int} deriving (Eq)
deriving newtype (Read, Show)
何だというのだッッッッッッ
instance (KnownNat p) => Num (GF p) where { (GF# x#) + (GF# y#) = case x# +# y# of { xy# -> GF# (xy# -# ((xy# >=# m#) *# m#))} where { !(I# m#) = natValAsInt (Proxy @p)}; {-# INLINE (+) #-}; (GF# x#) - (GF# y#) = case x# -# y# of { xy# -> GF# (xy# +# ((xy# <# 0#) *# m#))} where { !(I# m#) = natValAsInt (Proxy @p)}; {-# INLINE (-) #-}; (GF# x#) * (GF# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of { z# -> case timesWord2# z# im# of { (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of { v# | isTrue# (geWord# v# m#) -> GF# (word2Int# (plusWord# v# m#)) | otherwise -> GF# (word2Int# v#)}}} where { !(W# m#) = natValAsWord (Proxy @p); im# = plusWord# (quotWord# 18446744073709551615## m#) 1##}; {-# INLINE (*) #-}; abs = id; signum = const (GF 1); fromInteger x = GF . fromIntegral $ x `mod` m where { m = natVal (Proxy @p)}}
コードリーディング 1: 感想
とても素直で親切なコードである気がしました。逆に言うと、これほど親切な実装にも黒魔術は憑き物であり、異質な Haskell 筋が必要です。
主な発見
- 純粋関数はモナディック関数の特殊版である
- パーサが上手い
xyc <- (,,) <$> int <*> int <*> int1のように組み合わせられる (この際 1-based index から 0-based index への変換もできてしまう。上手い) - 定形の出力を簡単に出せるようになっている
- 75% ぐらいのコードは表層しか読めない
toyboot4eコードリーディング 2
Haskeller にはレーティング差以上の実力差を感じます。この人も Haskell 縛りじゃなければとっくに入水してそうですね。
スタイルはリストと array の正統派 Haskell という感じです。最小限のテンプレートは常にコードに入れていて、参考にするには理想的な様子です。
ModInt
法はグローバル変数:
newtype ModInt = ModInt { getModInt :: Int }
deriving (Eq, Ord, Show)
modInt :: Int -> ModInt
modInt !x = ModInt (x `mod` modulus)
modulus :: Int
modulus = 998244353
instance Num ModInt where 略
instance Fractional ModInt where 略
Applicative 的な:
liftMod :: (Int -> Int) -> ModInt -> ModInt
liftMod op (ModInt !x) = modInt $ op x
liftMod2 :: (Int -> Int -> Int) -> ModInt -> ModInt -> ModInt
liftMod2 op (ModInt !x) (ModInt !y) = modInt $ op x y
というか僕も applicative を
ModIntに実装すべきか！
Mod 上の逆数
TODO: 拡張ユークリッドの互助法とは:
modInverse :: Int -> Int -> Int
-- the value y which satisfies
-- (x * y) `mod` k == g where g = gcd x k.
-- when k is a prime number and 0 < x && x < k, g == 1.
modInverse k x = (`mod` k) $ fst3 $ extGcd x k
extGcd :: Int -> Int -> (Int, Int, Int)
-- the triple (p, q, g) which satisfies
-- p * x + q * y == g where g = gcd x y.
-- requires x >= 0 && y >= 0.
extGcd x y
| y == 0 = (1, 0, x)
| otherwise = (q, p - q * d, g)
where
(d, m) = divMod x y
(p, q, g) = extGcd y m
Array の tabulate
遅延評価で DP をやるためのテンプレート？ たぶん Richard Bird 先生のアルゴリズム設計本に載っているやつと同種のものだと思います:
tabulate :: (Ix i, A.IArray a e) => (i, i) -> (i -> e) -> a i e
tabulate bnds f = A.listArray bnds $ f <$> range bnds
fixArray :: Ix i => (i, i) -> (A.Array i e -> i -> e) -> A.Array i e
fixArray bnds f = tab
where
g = f tab
tab = tabulate bnds g
入力処理 [TODO]
StateT でパーサを作るパターンを理解していない:
class Readable a where
readBS :: B.ByteString -> Maybe (a, B.ByteString)
readBS = runStateT readBSState
readBSState :: StateT B.ByteString Maybe a
readBSState = StateT readBS
関数ではなく型ベースでパース？:
instance Readable Int where
readBS = B.readInt . dropSpace
instance Readable Char where
readBS = B.uncons . dropSpace
-- など
よくある操作に明示的な名前を:
discardLine :: IO ()
discardLine = void B.getLine
出力 (ByteStringBuilder)
この辺はみんな同じかもしれませんね:
class Renderable a where
renderBS :: a -> BB.Builder
instance Renderable Int where
renderBS = BB.intDec
-- 略
Interactive 問題で必須のやつ:
flush :: IO ()
flush = hFlush stdout
コードリーディング 2: 感想
強い。
- Array の遅延評価で解いてる？！
- 基本 array だとしたら、いつ Vector を抜くのだろう
- 拡張ユークリッドの互助法で mod 世界の逆数が求められるらしい？
- StateT でパーサを作るパターンが優れている気がする
- やはり入力処理が上手い (ちょっとズルいレベル):
[n, a, b, p, q] <- getFromLine
コードリーディング 3
短いので全部貼ります:
{-# LANGUAGE MultiWayIf #-}
import Data.Array.IArray
import Data.Maybe
import Data.Ratio
import qualified Data.ByteString.Char8 as C
main :: IO ()
main = do
[n, a, b, p, q] <- getInts
let dp = fArray ((1,1), (n,n)) f :: Array (Int, Int) MInt
pqinv = 1 / (fromIntegral p * fromIntegral q)
f (i,j) = sum os * pqinv where
os = do
ra <- [1..p]
rb <- [1..q]
let i' = min n (i + ra)
j' = min n (j + rb)
if | i' == n -> pure 1
| j' == n -> pure 0
| otherwise -> pure $ dp!(i',j')
print $ unMInt $ dp!(a,b)
getInts :: IO [Int]
getInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine
----------
mm :: Int
mm = 998244353
newtype MInt = MInt { unMInt :: Int } deriving (Eq, Ord, Show)
instance Num MInt where
MInt a + MInt b = MInt $ let c = a + b in if c >= mm then c - mm else c
MInt a - MInt b = MInt $ let c = a - b in if c < 0 then c + mm else c
MInt a * MInt b = MInt $ a * b `mod` mm
abs = id
signum = MInt . signum . unMInt
fromInteger = MInt . fromInteger . (`mod` fromIntegral mm)
instance Fractional MInt where
recip = (^(mm - 2))
fromRational r = fromIntegral (numerator r) / fromIntegral (denominator r)
----------
fArray :: (IArray a e, Ix i) => (i, i) -> (i -> e) -> a i e
fArray b f = listArray b (f <$> range b)
{-# INLINE fArray #-}
コードリーディング 3: 感想
こちらも遅延評価で解いています。 いやそんな簡単そうな問題だったか ……？？ Richard Bird ルートです。僕の Haskell はこの方向性を目指していません。成績を順当に上げる目的ならば、真似しようとしない方が良いと思っています。強い。
toyboot4eコードリーディング 4
以前挫折したのでさっと見るだけ:
コードリーディング 4: 感想
異常に高速な手続き型 Haskell で優勝しておる……！ ちょっとよくわかんないですね。
toyboot4e高難度解説 AC vs 適正難度演習
ABC 258 B で詰まって実力不足を感じています。水 diff の解説 AC ばかりではなく、茶 ~ 緑の問題を大量に解くべきか……？！
いずれは全問解くのだから、順番は問題ではない気もします。なら盆栽優先で！
toyboot4e環境の危機
nixos-rebuild switch しなければ良かったです (・ω ))
oj
こちらは stable 版を使って問題を回避できます。 Unstable 版も誰かに直してもらわなければ……
lxml が無い？
[INFO] load cookie from: /home/tbm/.local/share/online-judge-tools/cookie.jar
[NETWORK] GET: https://atcoder.jp/contests/agc001/submit
[NETWORK] 200 OK
[ERROR] failed to check the login status: Couldn't find a tree builder with the features you requested: lxml. Do you need to install a parser library?
Traceback (most recent call last):
File "/nix/store/4dsd891ki6p3lg2jq6zhb9c2vanfssrr-python3.10-online-judge-tools-11.5.1/lib/python3.10/site-packages/onlinejudge_command/subcommand/submit.py", line 88, in run
is_logged_in = problem.get_service().is_logged_in(session=sess)
File "/nix/store/z5f20zgfr0b8jx0vy8hccmwzzgdsj1h6-python3.10-online-judge-api-client-10.10.1/lib/python3.10/site-packages/onlinejudge/service/atcoder.py", line 101, in is_logged_in
resp = _request('GET', url, session=session, allow_redirects=False)
File "/nix/store/z5f20zgfr0b8jx0vy8hccmwzzgdsj1h6-python3.10-online-judge-api-client-10.10.1/lib/python3.10/site-packages/onlinejudge/service/atcoder.py", line 56, in _request
_list_alert(resp, print_=True)
File "/nix/store/z5f20zgfr0b8jx0vy8hccmwzzgdsj1h6-python3.10-online-judge-api-client-10.10.1/lib/python3.10/site-packages/onlinejudge/service/atcoder.py", line 38, in _list_alert
soup = bs4.BeautifulSoup(resp.content.decode(resp.encoding), utils.HTML_PARSER)
File "/nix/store/z7lniafa29cg42q8rdbbj1xv48dl9zzd-python3.10-beautifulsoup4-4.11.2/lib/python3.10/site-packages/bs4/__init__.py", line 248, in __init__
raise FeatureNotFound(
bs4.FeatureNotFound: Couldn't find a tree builder with the features you requested: lxml. Do you need to install a parser library?
HLS
HLS が死ぬ
-
わしのテンプレートはデカ過ぎたらしい
フォッフォッフォ (コメントアウトで HLS が動くようになりました) -
どこまでテンプレートを削れば良いのか
伝家の宝刀 † 二分探索 † ですぞ！ -
derivingUnboxで死んでいた
なぜ…… orz
今日限りの対処法
フォーマットだけでも使いたいので、 derivingUnbox がコメントアウトされた状態でエディタを起動することにしました。致し方なし……
toyboot4eUnion-Find を改良すべき？
ABC 264 E の実装が重めだったので、ライブラリの不足を感じています。多少パフォーマンスが落ちても汎用的に改造すべきでしょうか。
欲しい機能
グループに所属する要素の数を覚える
ルートの頂点番号 → グループ内の要素数
僕の union-find にもこの機能がありました。 API を追加しよう……
-- | `MUFChild parent | MUFRoot size`.
data MUFNode = MUFChild {-# UNPACK #-} !Int | MUFRoot {-# UNPACK #-} !Int
API もあった。。記憶が風化していますね。
グループごとに payload を載せる
ルートの頂点番号 → payload
いずれも unite 処理の拡張である
まあ毎回配列を作ってクロージャで unite すれば競技的には十分か……！
toyboot4eTODO: IO のガバベンチ
ByteString で読むと速い？
Vector に読むと速い？
ByteStringBuilder で出すと速い？
-
<>すべきか、都度書き出すべきか
toyboot4ePAST 上級の夢を見た
実際解いてみたら TLE しまくりだよ……！
PAST の配点
序盤移行は 1 問 6 点です。
- 中級 (60 点以上): 6 問まで間違えてよい
- 上級 (80 点以上): 3 問まで間違えてよい
- エキスパート (90 点以上): 1 問のみ間違えてよい
toyboot4e問題です
次のループ処理のうち、 TLE の危機に有るコードはどれですか？
(!! n) $ iterate f s0snd $ until ((== n) . fst) (bimap succ f) (0, s0)foldl' step (\x _ -> f x) [1 .. n]VU.foldl' step (\x _ -> f x) (VU.replicate n False)
解答
-
iterate: TLE -
until: 684 ms -
foldl': 632 ms -
VU.foldl': 626 ms
学び
ループ処理に iterate を使うのは止めよう……
toyboot4eTLE が取れた && WA が取れた
天才かよ……！ 正直茶 diff 感あります。謎のハマり方をするのが僕なんですね？
5 時間あったら本当に上級を狙えそうです。
toyboot4ePAST の難度
このツイートが今も適用できるなら、意外と水色目前なのか……？
まあ 2019 年の話ではあります。今はレーティング 777 が現実ですよ……！
toyboot4e上級の実力は無かった
第八回 PAST を 11 問 AC でギブアップ。 Upsolve していきます。
尺取り法
バグりまくったのでテンプレートを書きました。条件を満たす区間を返します:
twoPointers :: Int -> ((Int, Int) -> Bool) -> [(Int, Int)]
twoPointers !n !check = inner (0, 0)
where
inner (!l, !r) | l >= n = []
inner (!l, !r)
| check (l, r) =
let (l', r') = until (not . peekCheck) (second succ) (l, r)
in (l', r') : inner (succ l', max l' r')
| otherwise = inner (succ l, max (succ l) r)
peekCheck (!l, !r) | r == pred n = False
peekCheck (!l, !r) = check (l, succ r)
大分無駄が多いのですが、今は定数倍の遅延を許容します。シュッとした Haskell は読めないし書けない。。
toyboot4ePascal ユーザの人の記事
おお……。 Pascal ユーザは Basic ユーザより少ない可能性があります。果たしてその実体は？
しかしながらPascalメインで使っている人は皆無に等しく
昨日のコンテストABC287で提出結果を検索してみると自分以外では
セルビアの人が1人だけで参加者約10000人弱中たった2名のみという超不人気言語です。
面白すぎるｗ
AtCoder の UI を作るという手があったか……！
めちゃめちゃ面白い。やはりマイナ言語周辺はコンテンツ価値が高いようですね。
toyboot4eLCA (Lowest Common Ancestor: 最小共通祖先)
最低共通祖先と言ったほうがイメージが湧きやすい。サイテー！
. CA
|
. CA
|
* LCA
/ \
v1' . * v2
/
v1 *
木が非常に深い場合を考えてダブリングによる高速化が必要
概要
- DFS などで depths (頂点 → 深さ), parents (頂点 → 親頂点) を求める
- depths をダブリングする
深さを 1 つ戻る関数は配列で表現できる。配列の出力を配列に繋ぐことでダブリングができる。よって深さ d 戻る処理を (大きな) 定数時間で求められる。 - v1, v2 の深さを揃える (上図で v1 → v1')
この操作は無くても良いが説明が簡単になる - 戻る深さ d に関する 2 分探索で LCA が求まる
深さ d 戻った頂点が共通祖先であるかは d に関して短調 (上図からも一応イメージできそう)
ダブリングの実装に関して
配列の生成と配列の適用に分けました:
newDoubling :: (VG.Vector v a, VG.Vector v Int) => a -> (a -> a) -> v a
newDoubling !x0 !squareF = VG.scanl' step x0 $ VG.enumFromN (0 :: Int) 62
where
step !acc !_ = squareF acc
applyDoubling :: (VG.Vector v a) => v a -> b -> (b -> a -> b) -> Int -> b
applyDoubling !doubling !x0 !f !n = foldl' step x0 [0 .. 62]
where
!_ = dbgAssert $ VG.length doubling == 63
step !acc !nBit =
if testBit n nBit
then f acc (doubling VG.! nBit)
else acc
ダブリングされた関数 (関数適用のための値) のことを
doublingと呼ぶのはセンスが悪い気はしています。choppedとかもう少し良い名前に変えたいところですが……
dbgAssert :: Bool -> a -> a
dbgAssert False !x = error "assertion failed!"
dbgAssert True !x = x
#else
dbgAssert :: Bool -> a -> a
dbgAssert = flip const
#endif
ダブリングの概念に関して
具体例は、
-
繰り返し 2 乗法
かける数をダブリングしておく -
LCA
配列の出力を配列に繋いでダブリングする
イメージとしては、合成関数 (の元になる値) を事前計算できるものがダブリング可能なもの？ もっと的確に捉えたいが……
応用
- 木の上の 2 点間の距離が分かる (LCA からの距離の和)
ただ辺に重みがある場合は LCA では無理そう
演習
toyboot4e木の探索
-
同じ頂点を 2 度訪問しない
隣接頂点の取得時に親のみ除外する (実装が楽) -
2 頂点の距離
- 色分け (偶奇)
- 距離 = LCA からの距離の和
- 根からの距離
toyboot4eTODO: グラフ関連のコードを抽象化したい
グラフ関連のテンプレートが肥大化しています。グラフの特徴を抽出して整理したいところですが、全く目処が立ちません。検討中……
参考にしよう
グラフの特徴
- 有向グラフ、無向グラフ
- 木、 functional graph, 複雑なもの
- 連結か否か
- 重み付きグラフ
- 重みの型
- 負の辺の有無
- 頂点の payload
- 辺の payload
- etc.
個々の操作
- 隣接頂点を取得
- 隣接頂点を取得 (訪問済み頂点を除外する)
探索方法
- 探索済み頂点を
Vectorで管理する - 探索済み頂点を
IntSetで管理する
toyboot4eOCaml が読めない
面白そう！
toyboot4eBrute-force 探索
なんだかんだ全探索が決め手となることが多いです。
最初の一手も最後の一手も全探索だ！
Brute-force 2 分探索
Brute-force 尺取り
他にも色々ありました
全探索を信じよ！
toyboot4eTODO: 最大流の典型、最小費用流
このブログが良さそうです。
最大流に帰着できる問題
最小費用流
toyboot4eMex
集合に含まれない最小の非不整数を求めよ。言い換えれば、非不整数の集合の余集合の最小値を求めよ。〜水 diff の典型のようです。
演習
どっちも解けませんでした。
toyboot4e手続型 Haskell のコツだと思っていること
絶大な効果
- 手続き型を避ける方法を考える。たとえば
- 経路の収集と処理を分離する。収集は純粋関数にできる (maxFlow)
- 候補を IntSet で持っておき、制約との差分を取って絞り込む (ABC 299 E, なるほど)
- など
バグが減る
- undef のような定数を作りマジックナンバーを避ける
- イテレーション時の if よりもイテレーション前の filter (ネストが減る)
より宣言的なコードへ近づいていく不思議
再帰の手段
- 再帰関数をクロージャにして可変配列にアクセスする (と楽)
let で関数定義して <- で実行となる - flip fix で再起関数を作成、即実行
<- flip fix の 1 文で済む (それ以上の利点は無い)
迷っている点
- forM の出力を一時変数に入れて、次の行でリスト処理
- つまり
xs_ <- forM ..の後にmap f xs_などとする - もし
xs <- map f <$> forM ..とするならラムダ式を () で囲む必要がある - () で囲んだ方が良い可能性もある
- そもそもこんな forM を書くよりも純粋なロジックに落とし込んだ方が良い
- つまり
toyboot4eTODO: 考察フローチャート
水 diff までなら機械的に考察できないものか。逆引き辞典をループするだけで得点できるようにしてみたいと思います。
以下ループして計算量を削減します
考察一般
- クエリを逆順に処理する
- グラフで表現する
- トポロジカルソートで依存関係を整理
- 最大流問題に帰結？
- よく分からないクエリを brute-force 2 分探索判定で強行突破
- 主客転倒
- 全体を操作するのではなく、個々からの寄与で全体を求める方法を考える
- 転倒数の偶奇によって完了状態に到達可能かが判定できないか
- 操作前後の不変量を考察する
全探索
- Brute-force 全探索
- 全組み合わせを調べる
- 商列挙 (変数の固定)
- ソートして二分探索
- 座標圧縮の後ソートして 2 分探索
- 累積和をソートして尺取法で条件を満たす組み合わせをカウント
- 境界を 2 分探索
- 尺取法
- 答えで二分探索
- 最も大きな値を求めよ
- 最も小さな値を求めよ
- n 番目の値を求めよ
- 不等式を変形して各項からの寄与の和に関する判定問題に変形
- さらに brute-force 全探索、からの 2 分探索など
- ダブリングしておく (置換操作など)
グラフ考察
- グラフの問題であろうと、単なる入力処理と状態発展 (fold) で解けないか。
- グラフを 2 つに分けて持つ
- 状態を頂点に、遷移を辺としたグラフを考える
- 頂点のタプルを状態とする
- 1 頂点からの距離 (BFS, Dijkstra)
- 1 頂点への距離 (逆グラフで BFS, Dijkstra)
- 全各点間の距離を事前計算
- 木なら LCA
- 重み無しグラフなら全点から BFS
- 正の辺のみなら Dijkstra
- 負の辺があれば Floyd-Warshall?
- 木の 2 点間距離の偶奇
- 木を二部グラフと見て色塗り
- 根からの距離の差の偶奇
- LCA で求めた距離の偶奇
連結成分
-
Union-Find で連結成分を記録・更新する
- 辺削除を避けて辺追加で解答する
-
トポロジカルソートしてみる
-
木 DP (配る DP)
-
木 DP (再帰関数による受け取る DP)
-
強連結成分
- 閉路を集める、閉路を解消する
- 強連結成分で配る DP
DP
- 集合 DP (行列形式グラフ、小さい集合から配る DP)
- 区間 DP (短い区間から順に処理する、区間の和または区間の拡張で最適値を求める)
- 桁 DP (忘れた)
随時更新予定
そんなにパターンは多くないので、詰まった時に発想を補うことができれば AC できる確率が上がります。その程度は既に GPT くんがやってくれそうですが…… (hey GPT, この問題の典型は？ 類題は何？)
toyboot4e絶望がデフォルト
解けない → 解説 AC できない → 誰も俺を愛さない → 寝る → 解ける
今日の自分は明日の自分の贄となることしかできない。。
toyboot4eヒューリスヒック エアプ
連休の自由研究でビームを飛ばすことにしました。ヒューリスヒックもやって行きましょう！
AHC
- 月 1 の開催
- 4 時間のコンテスト
- 提出間隔は 30 分
- レーティングは上昇のみ (マイナスが無い)
提出回数が限定されるので、ローカルでテスト環境を作ってパラメータの調整がしたい気がします。その辺の常識が知りたい……！
基本は 2 つ
ビームサーチと焼きなまし法！ 後は考察やパラメータ調整で戦えそうです。
Psyho 氏
鉄則本
ヒューリスヒックの章を読みました。飛ばした章でしたが 鉄則本の中で一番良かった と思います。分かった感が凄い。複素解析みたく題材が良い説もあります。
複素解析の本が大体傑作に見えるのは、複素解析が傑作だから。
- 局所探索法
現在の解に小さな変更を加え、解が改善されるなら採用する。 - 焼きなめし法
局所探索法の解のスコアが悪化する場合も、特定の確率で採用する。悪化する場合の確率にはexp (- \frac \Delta T) - 貪欲法
次の一手のスコアが最善のものを選ぶ。スコア計算の指標は任意に定める。スコアの計算式が結果に大きく影響する。 - ビームサーチ
それぞれの候補の次の一手を考えて、高スコアの上位 K 本の候補を採用することを繰り返す。貪欲法はビーム幅 1 のビームサーチと言える。 Haskell で言えば foldl による入力処理で表現できる。
何が『探索』なのか？
より良い解を探していくことが探索で、解の候補も探索と呼んで良いのではと捉えています。 Thunder 本は未読のため不明です。
言語の選択
Common Lisp に挑戦するつもりでしたが、実行コマンドがコンパイル実行ではないのが気になっています。 Haskell で時間や乱数を使ってみるのも良いかも知れません。
toyboot4e
range が相当遅い気がする
3 重ループの書き方で実行時間が 5 倍弱変化しました。
-
forM_1 つとfilter,rangeで書いた場合: 2,003 ms, 437 MB - 1 次元の
forM_からrange風に手動で 3 次元添字を復元した場合: 923 ms -
forM_1 つとリスト内包表記で書いた場合: 749 ms, 436MB -
forM_3 つで書いた場合: 438 ms, 217 MB
感想
リスト内包表記が一番無難です。
range の場合 boxing が起こっている気がします。メモリ使用量を見てもたぶんそう。リスト内包表記は中間的な結果で少し謎ですが、 range よりはマシなので使っていけそうです。
雑念
range ぐらい綺麗なコードを高速実行したいです。 stream とか vector 関係に置換すればあるいは……？ 思いつかなければ質問します。
toyboot4e目の端に解答が 5 秒移ると、やがて『自力で』解けてしまう
解説の冒頭だけを読んで撤退 → 再考察 → なぜか解ける → 目に端に映った解説を無意識ちゃんが囁いていた → 誰もお前を愛さない
数学の問題を解いていた時もこの経験がありました。自分の『ユニークな』発想と全く同じものが解答に載っていて、実は解説を元ネタにしていたという。。
答えを見ると自力感が無いですが、しばらく問題を寝かさえておくと、自然とヒントが集まるかもしれません。そうした経験は役立ちそうです。
toyboot4e関数合成
定義域に応じたサイズの配列を作れば良い。なるほど。
置換の合成
置換は単なる配列で表されるため、配列の出力に配列を繋いで合成します。
Bit 演算の合成
まんまこれですが
-
公式解説
Int 値の関数を分解し、 i 番目の bit を取って i 番目の入力に移す関数が 64 本と捉えます。また個々の関数は 0 または 1 を取って 0 または 1 を返すため、長さ 2 の配列 (タプル) で表現できます。 -
ユーザ解説
0b000...0 と 0b111...1 に分けて関数を保持
toyboot4e
concat を fold に置き換えたらギリギリ通った
やはり forM する際のお手軽かつ高速なリスト生成法が必要……！
これで TLE ネタが 7 つ揃ったので記事を書きます。メモ: ABC 246 E
toyboot4e入緑しました
よっしゃ！
主な統計
- 取り組み期間: 11 ヶ月
- 総 AC 数: 397
- E 問題 AC 数: 37
- 水 diff AC 数: 32
AtCoder Problems
