このスクラップは

競プロ盆栽 (Haskell 盆栽) から進捗表やチートシートを分離したものです。

toyboot4e

ノート

欲しいもの

主なアルゴリズム (鉄則本)
scc, topSort など Data.Graph の替わりの関数
Ix キーや (Bool, Int) キーが使える IntMap, IntSet
Ix キーが使える Vector
Algorithm Design with Haskell の動的計画法の章の情報
fgl の利用経験
妥協の無い手続き型プログラミング (特に early return 周り)

捨てた手

リストへのランダムアクセス
遅延評価で動的計画法 (テーブルサイズが大きいと、 unboxed なコンテナを使った時点で MLE)
flip fix を使った再帰関数でメモ化 DP (DP 配列の累積和で撃沈)
(!! n) $ iterate step s0

典型的な罠

精度不足
- Double を使う
- 可能なら整数で計算する ( $log$ を等式変形で消す、 2 分探索で平方根を求める)
桁溢れ
- Integer を使えば安心
- 定期的に mod を取っても安心
メモリ使用量がデカい
- 座標圧縮するか IntMap を使います

主な定石

入出力

空白区切りの unwords, byte string builder の <>, mconcat, forM_ xs print
Text.printf
replicateM nInput $ do ..

リスト

sortBy (comparing f), group, HT.groupBy

Vector, Array

Vector のソート: VU.modify VAI.sort vec
2 次元の不変配列: V.Vector (VU.Vector a) として保存する、 accumArray で配列を作る
2 次元の可変配列 (row-major): Mutable array を利用 (サイズ (h, w), 添字は (y, x) つまり (row, column)). thaw $ accumArray .. という手もある (unsafeThaw) 。
2 次元リストの縦方向 scan: VU.generate で添字経由のアクセス

accumArray

accumArray や Data.Graph.buildG でグラフ生成
IM.fromListWith で sparse な accumArray からの scan で累積和

入力処理

mapAccumL step s0 input
foldl' step s0 input
再帰関数
until p s0
loop, loopM

その他

Bit で状態を表す (→ 2 つで状態遷移を表す)
foldl' で n 進数変換

典型的な解法

計算量を減らしつつ総当たり
貪欲法 + 2 分探索 (答えで 2 分探索)
mapAccumL で入力処理
foldl' で動的計画法
IntSet で BFS / DFS

アルゴリズム

2 分探索 (ok/ng の境界を求める方式 (めぐる式))

参考記事: AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法│FORCIA CUBE│フォルシア株式会社

-- {{{ Binary search

-- | Binary search for sorted items in an inclusive range (from left to right only)
-- |
-- | It returns an `(ok, ng)` index pair at the boundary.
-- |
-- | # Example
-- |
-- | With an OK predicate `(<= 5)`, list `[0..9]` can be seen as:
-- |
-- | > [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-- | >  <-------------->  <-------->
-- | >         ok             ng
-- |
-- | In this case `bsearch` returns the `(ok, ng)` = `(5, 6)` pair:
-- |
-- | > > let xs = [0..9] in do
-- | > >   print $ bsearch (0, 9) (\i -> xs !! i <= 5)
-- | > (5, 6)
bsearch :: (Int, Int) -> (Int -> Bool) -> (Maybe Int, Maybe Int)
bsearch (!low, !high) !isOk = both wrap (inner (low - 1, high + 1))
  where
    inner :: (Int, Int) -> (Int, Int)
    inner (!ok, !ng)
      | abs (ok - ng) == 1 = (ok, ng)
      | isOk m = inner (m, ng)
      | otherwise = inner (ok, m)
      where
        m = (ok + ng) `div` 2
    wrap :: Int -> Maybe Int
    wrap !x
      | inRange (low, high) x = Just x
      | otherwise = Nothing

-- }}}

尺取り法 (※ 重い)

-- | Returns inclusive ranges that satisfy the given `check`.
-- TODO: cheaper implementation
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)

転倒数

-- {{{ Inveresion number (segment tree)

-- | Calculates the inversion number.
-- |
-- | REMARK: The implementaiton assumes that the input is in range `[0, length - 1]`.
invNumVec :: (VG.Vector v Int) => v Int -> Int
invNumVec xs = runST $ do
  let !n = VG.length xs
  !stree <- newSTree (+) n (0 :: Int)

  -- NOTE: foldM is better for performance
  !ss <- VG.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 $ VG.sum ss

-- }}}

辞書順

-- | Returns 1-based dictionary order for the given array.
-- | WARNING: Use 0-based indices for the input.
dictOrderModuloVec :: (VG.Vector v Int) => v Int -> Int -> Int
dictOrderModuloVec xs modulus = runST $ do
  !stree <- newSTree (+) (VG.length xs + 1) (0 :: Int)

  -- Pre-calculate factorial numbers:
  let !facts = factMods (VG.length xs) modulus

  -- The calculation is very similar to that of inversion number. For example,
  -- ```
  --     2 0 4 3 1
  --     | | | | |
  --     | | | | +-- 0 * 0!
  --     | | | +-- 1 * 1!
  --     | | +-- 2 * 2!
  --     | +-- 0 * 3 !
  --     +-- 2 * 4!
  -- ```
  -- So each expression is given as `(the number of unused numbers smaller than this) * factMod`.
  !counts <- flip VG.imapM xs $ \i x -> do
    !nUsed <- querySTree stree (0, x)
    let !nUnused = x - nUsed
    let !factMod = facts VG.! (VG.length xs - (i + 1))
    let !inc = nUnused * factMod `rem` modulus

    -- mark it as used
    insertSTree stree x 1

    return inc

  return $ succ $ VG.foldl1' (\ !acc x -> (acc + x) `rem` modulus) counts

prevPermutationVec

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

Union-Find 木 (`MVector`)

参考: Union-Find とは | アルゴ式

-- {{{ Union-Find tree

-- | Dense, mutable union-find tree (originally by `@pel`)
newtype MUnionFind s = MUnionFind (VUM.MVector s MUFNode)

type IOUnionFind = MUnionFind RealWorld

type STUnionFind s = MUnionFind s

-- | `MUFChild parent | MUFRoot size`.
data MUFNode = MUFChild {-# UNPACK #-} !Int | MUFRoot {-# UNPACK #-} !Int

derivingUnbox
  "MUFNode"
  [t|MUFNode -> (Bool, Int)|]
  [|\case (MUFChild !x) -> (True, x); (MUFRoot !x) -> (False, x)|]
  [|\case (True, !x) -> MUFChild x; (False, !x) -> MUFRoot x|]

-- | Creates a new Union-Find tree of the given size.
{-# INLINE newMUF #-}
newMUF :: (PrimMonad m) => Int -> m (MUnionFind (PrimState m))
newMUF !n = MUnionFind <$> VUM.replicate n (MUFRoot 1)

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

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

-- | Just an internal helper.
_unwrapMUFRoot :: MUFNode -> Int
_unwrapMUFRoot (MUFRoot !s) = s
_unwrapMUFRoot (MUFChild !_) = undefined

-- | Unites two nodes.
{-# INLINE uniteMUF #-}
uniteMUF :: (PrimMonad m) => MUnionFind (PrimState m) -> Int -> Int -> m ()
uniteMUF uf@(MUnionFind !vec) !x !y = do
  !px <- rootMUF uf x
  !py <- rootMUF uf y
  when (px /= py) $! do
    !sx <- _unwrapMUFRoot <$!> VUM.read vec px
    !sy <- _unwrapMUFRoot <$!> VUM.read vec py
    -- NOTE(perf): union by rank (choose smaller one for root)
    let (!par, !chld) = if sx < sy then (px, py) else (py, px)
    VUM.write vec chld (MUFChild par)
    VUM.write vec par (MUFRoot (sx + sy))

-- | Returns the size of the root node, starting with `1`.
{-# INLINE sizeMUF #-}
sizeMUF :: (PrimMonad m) => MUnionFind (PrimState m) -> Int -> m Int
sizeMUF uf@(MUnionFind !vec) !x = do
  !px <- rootMUF uf x
  _unwrapMUFRoot <$!> VUM.read vec px

-- }}}

Union-find 木 (`IntMap`)

セグメント木

参考: 競技プログラミングの鉄則

-- {{{ Bits

-- | Log base of two or bit floor.
-- | <https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Bits.html#v:countLeadingZeros>
log2 :: (FiniteBits b) => b -> Int
log2 x = finiteBitSize x - 1 - countLeadingZeros x

-- | Ceiling of log base 2 of an `Int`.
-- |
-- | # Example
-- |
-- | ```hs
-- | > log2 3
-- | 1
-- | > log2CeilInt 3
-- | 2
-- | ```
log2CeilInt :: Int -> Int
log2CeilInt x = msb + ceiling
  where
    msb = log2 x
    ceiling = if (clearBit x msb) > 0 then 1 else 0

-- | Calculates the smallest integral power of two that is not smaller than `x`.
-- |
-- | # Example
-- |
-- | ```hs
-- | > bitCeil 3
-- | 4
-- | ```
bitCeil :: Int -> Int
bitCeil = bit . log2CeilInt

-- }}}

-- {{{ Segment tree

-- | A mutable segment tree backed by a complete binary tree.
-- |
-- | # Overview
-- |
-- | A segment tree is a cache of a folding function.
-- | Each node corresponds to a folding range and the node contains the folding result.
-- |
-- | A segment tree has a constant size and never be resized.
-- |
-- | # Operations
-- |
-- | Modification takes $O(log N)$, so creation takes $N(log N)$.
-- | Lookup takes $O(log N)$.
-- |
-- | # (Internal) Indices
-- |
-- | The complete binary tree has `2 ^ depth - 1` elements.
-- |
-- | - Child elements of a parent node `i` has index `2 * i + 1` and `2 * i + 2`.
-- | - The leaf indices start with `length / 2 - 1`.
-- |
-- | Example:
-- |
-- | ```
-- |            0
-- |      1           2
-- |   3     4     5     6
-- | 07 08 09 10 11 12 13 14
-- | ```
data MSegmentTree s a = MSegmentTree (a -> a -> a) (VUM.MVector s a)

-- TODO: Can I UNPACK? the funciton?
-- TODO: Generic queries and immutable segment tree (with `Show` instance)

-- | Creates a new segment tree for `n` leaves.
-- | REMARK: Always give a zero value. It fills all the nodes including parent nodes, and the parent
-- | nodes are not updated.
{-# INLINE newSTree #-}
newSTree :: (VUM.Unbox a, PrimMonad m) => (a -> a -> a) -> Int -> a -> m (MSegmentTree (PrimState m) a)
newSTree !f !n !value = MSegmentTree f <$!> VUM.replicate n' value
  where
    !n' = shiftL (bitCeil n) 1

-- | Updates an `MSegmentTree` leaf value and their parents up to top root.
{-# INLINE insertSTree #-}
insertSTree :: (VU.Unbox a, PrimMonad m) => MSegmentTree (PrimState m) a -> Int -> a -> m ()
insertSTree tree@(MSegmentTree !_ !vec) !i !value = _updateElement tree i' value
  where
    -- length == 2 * (the number of the leaves)
    !offset = VUM.length vec `div` 2 - 1
    -- leaf index
    !i' = i + offset

-- | Updates an `MSegmentTree` leaf value and their parents up to top root.
{-# INLINE modifySTree #-}
modifySTree :: (VU.Unbox a, PrimMonad m) => MSegmentTree (PrimState m) a -> (a -> a) -> Int -> m ()
modifySTree tree@(MSegmentTree !_ !vec) !f !i = do
  !v <- f <$> VUM.read vec i'
  _updateElement tree i' v
  where
    -- length == 2 * (the number of the leaves)
    !offset = VUM.length vec `div` 2 - 1
    -- leaf index
    !i' = i + offset

-- | (Internal) Updates an `MSegmentTree` element (node or leaf) value and their parents up to top root.
{-# INLINE _updateElement #-}
_updateElement :: (VU.Unbox a, PrimMonad m) => MSegmentTree (PrimState m) a -> Int -> a -> m ()
_updateElement (MSegmentTree !_ !vec) 0 !value = do
  VUM.write vec 0 value
_updateElement tree@(MSegmentTree !_ !vec) !i !value = do
  VUM.write vec i value
  _updateParent tree ((i - 1) `div` 2)

-- | (Internal) Recursivelly updates the parent nodes.
{-# INLINE _updateParent #-}
_updateParent :: (VU.Unbox a, PrimMonad m) => MSegmentTree (PrimState m) a -> Int -> m ()
_updateParent _ (-1) = pure () -- REMARK: (-1) `div` 2 == -1
_updateParent tree@(MSegmentTree !f !vec) !iParent = do
  !c1 <- VUM.read vec (iParent * 2 + 1)
  !c2 <- VUM.read vec (iParent * 2 + 2)
  _updateElement tree iParent (f c1 c2)

-- | Retrieves the folding result over the inclusive range `[l, r]` from `MSegmentTree`.
{-# INLINE querySTree #-}
querySTree :: forall a m. (VU.Unbox a, PrimMonad m) => MSegmentTree (PrimState m) a -> (Int, Int) -> m a
querySTree (MSegmentTree !f !vec) (!lo, !hi) = fromJust <$!> inner 0 (0, initialHi)
  where
    !initialHi = VUM.length vec `div` 2 - 1
    inner :: Int -> (Int, Int) -> m (Maybe a)
    inner !i (!l, !h)
      | lo <= l && h <= hi = Just <$> VUM.read vec i
      | h < lo || hi < l = pure Nothing
      | otherwise = do
          let !d = (h - l) `div` 2
          !ansL <- inner (2 * i + 1) (l, l + d)
          !ansH <- inner (2 * i + 2) (l + d + 1, h)
          pure . Just $ case (ansL, ansH) of
            (Just !a, Just !b) -> f a b
            (Just !a, _) -> a
            (_, Just !b) -> b
            (_, _) -> error $ "query error (segment tree): " ++ show (i, (l, h), (lo, hi))

-- }}}

その他 dijkstra, topSort, scc, LCA, ２部グラフ判定・２部グラフ色分け、最大流、 IntMod, RollingHash など

toyboot4e

感想

本の内容に関して

1,000,000 点！　ライブラリが潤いました。

ただテストケースが弱いため、尺取り法の替わりに 2 分探索しても通ったりして注意が必要です (PAST なら、尺取り法 ( $O(N)$ ) が想定解の場合、 N 回の 2 分探索 ( $O(N logN)$ )では通りません) 。

本の使い方に関して

分からなければサクっと解説 AC し、ライブラリを揃えることに専念したら良いと思います。演習問題はいくらでもありますので、取り零しは心配ありません。

B 問題を解くべきかは検討中です。

本の難易度に関して

あーだこーだーによると鉄則本は初心者向けだったそうです。演習問題は相当難しいと感じますけれどね……！

まあ『答えで 2 分探索』とだけ聞いても食塩水問題は普通解けません。類題演習が必要です。鉄則本の効果は、解説 AC の前提条件というラインかもしれません。

鉄則本に無かった内容

以下の典型は、常設コンテストや過去問から学ぶ必要がありました。

座標圧縮 (座標圧縮は鉄則本にあったかもですが)
トポロジカルソート、強連結成分、 2-SAT
二部グラフの判定、色分け
転倒数 (binary index tree あるいはセグメント木による実装)
辞書順 (binary index tree あるいはセグメント木による実装)
LCA (最小共通祖先: ダブリングによる実装)
DP (期待値 DP, 集合 (bit) DP, 桁 DP) (区間 DP は演習にある)

以降は僕も未履修です。俺達の盆栽はこれからだ！

最小費用流
2 次元の座標圧縮
拡張ユークリッドの互助法、包除原理、中国剰余定理
高度典型
など

toyboot4e

典型 90 問 (〜 ★ 3)

未だに鉄則本 a 問題をやっていますが、新規アルゴリズムの盆栽ばかりというのも (非常に好みですが) 疲れが出ます。息抜き程度に典型 90 問もやってみます。

これらの問題は比較的考察が主で、ある程度解けば緑色が狙える程度という認識です。

リンク

Qiita から難度表を転記しました。★ 3 ~ 4 が解ければ水色相当……？

星の数	★1	★2	★3	★4	★5	★6	★7
配点	1 点	2 点	3 点	4 点	5 点	6 点	7 点
Diff.	～149	150～399	400～799	800～1199	1200～1599	1600～1999	2000～

環境構築

典型 90 問を atcoder-cli でダウンロードすると 001/, 002, .. というディレクトリができます。これらの 001/Main.hs, 002/Main.hs, .. に対し、 なぜか LSP でフォーマットできませんでした 。

そこで a001/, a002/ のようにアルファベットから始まるディレクトリ名に変更すると、正常に動作するようになりました。謎……。

$ rename 's/^0/a0/g' *
$ # `contest.acc.json` も直しておきます

実装

所感

灰色でも Haskell では難しい問題が多いです。
茶色の方が簡単な問題が多かったです。

toyboot4e

Educational DP Contest (A ~ E)

EDPC A
- 遅延評価で通ります。これくらいなら心配ありません。
- 今この瞬間も、僕を含めて 8 人くらいが解答を提出しています。人口多いなぁ
EDPC B
- 遅延評価で通りました。制約的に不安でしたが……。
- fold (list + 重複除去) も大体解法を考えました。
- MVector でボトムアップに解く方法も行けます。
EDPC C
- fold で解けます。楽。
EDPC D: ナップサック問題 (V が大きい場合)
- Vector (w -> v) の fold で AC
- リストでもなんとか AC
  - TLE の原因が謎で困ります。テストケース次第では TLE だよな……
  - やはり Vector で fold が安牌、リストは謎
EDPC E: ナップサック問題 (W が大きい場合)
- リストで AC
- Vector (v -> w) の fold

toyboot4e

ABC ノート

ABC 284: 3 完 (29 分) 494 (5255 / 9299)
- C は DFS で。バグっていて躓きました
- D が解けず。。 2 個目の素数は探索しなくて良かったか……
- E は DFS で解こうとして失敗
- F は明らかに B 進数ハッシュだと思いましたが、実装が間に合わず (でも解けそう)
- なんか全体的に解けそうだ……！
ABC 285: 4 完 (86 分) 860 (2380 / 8173)
- A で死亡、 B で死亡、 D で死亡
- A は算数、 B は全探索、 C も算数、 D はループを探すだけ
- E は普通に解けない。。
ABC 286: 4 完 (72 分) 883 (2469 / ?)
- A 問題が難しかったよ。。ブランクが空くとこうなります
  - slice l r = take (r - l + 1) $ drop l を作れば良かったです
- B 問題をオートマタで解こうとしてパタンマッチで十分だった
- C 問題は右端に移動できる文字は左端の文字だけだと読むのに時間がかかりました
- D 問題は fold で解ける簡単な DP なので、これで点をもらうのは申し訳ない気もしました
- E 問題はけんちょん本でみたやつ！　これとか動的計画法の難しいやつはいずれ解けると思います
ABC 287: 4 完 (72:02) 883 (2465 / ?)
- A: For の大文字に気をつけます
- B: IntSet に入れて比較しました
- C: DFS で解いたのですが大変時間がかかりました。グラフに弱いです
- D: 累積和。これでレートが稼げるのは不思議な感じですが……
- E: 地層を積み重ねていくような計算ですが……
  終了後、 [Int] -> [[Int]] を accumArray で表現して AC 。これは精進していれば時間内に解けたかも
- 現レート 667 です。最近は典型的な問題が多かったですが、そろそろ速解や数学が求められてレートが落ちる気がします。精進再開しよう！
ABC 288: 3 完 (89 分) 560 (4365 / 7645)
- A: map します
- B: 0 パディング的なことを考えて死亡　ソートにかけるだけで十分でした
- C: Data.Graph で連結成分を求めて、余分な辺の和は 辺の数 - 頂点の数 - 1 の和
  - 別解: Union-Find で閉路を作る辺の数を数え上げ
- D: 考察で死亡
ABC 289: 4 完 (93:10) 735 (3586 / 7804)
- A: Lambda case (\case -> ..) が便利ですね
- B: Union-Find で group するのが大変でした。どうすれば良かったのか……
  - やはり灰 diff でも相当難しい問題はある……
- C: Bit 全探索ですべての組み合わせを試します
- D: DP として解けなかったので探索として解きました。重複除去が命……！
  - 解答: 1 ~ N までイテレートして $O(N * M)$ . なるほど！
- E: 時間切れです
ABC 290: 3 完 (78:00) (4317 / 6180)
- A: 最速はもらった！
- B: mapAccumL そのもの！
- C: 爆死しました。groupBy が思っていたのと違った……
```
ghci> groupBy (\a b -> a + 1 == b) [0, 1, 2, 3]
[[0,1],[2,3]]
```
- D: 全然解けません。解説を見てなるほど……
ABC291: 4 完 (33:26) (2386 / 6849)
- A: 最速はもらった！
- B: 最速はもらった！
- C: 愚直に foldl' します。
- D: 愚直に foldl' します。余りを取るのは忘れずに……
- E: 木の最も長いパスを通れば良い。が、どうすれば……
  - どうやって根を見つける？　その後の探索は DFS では間に合わないのでは？
  - トポロジカルソートというそうです？
  - 何がソートなのかかまだ分かりませんが、 in_degree に注目します
    - In-degree が最小 (0) の頂点を記録
    - 最小の頂点が 2 つ現れたらエラー
    - 0 の頂点が無いなら閉路がある
    - グラフから頂点と取り除くとき、隣接する頂点の次数を更新する
  - トポロジカルソートは Data.Graph.topSort で再現できるのでしょうか
ABC 292: 3 完 (44:25) (3581 / 7550)
- A: 最遅はもらった……！　Vector 2 本でマップします。ケース変更の関数があるのかな
  - ありました: Data.Char.toUpper, Data.Char.toLower
- B: MVector と forM で。
- C: 素数を列挙して 1 ~ N の約数の数を……と思ったが失敗。。。 定数倍の最適化を考えるのは止めて、既存の関数を使って AC しよう と決めました。
- D: Data.Graph.components の使い方が分からなくて辛かったです。あのライブラリは一見便利そうなのが良くない。。 topSort 以外使わないことに決めました。自作 DFS で AC！　典型はいけるか！
- E: トポロジカルソートの逆順で計算しようとして失敗。上手くやろうとせず、すべて数え上げてしまえば解けるのですね……
- 今回はチャンスでしたが逃しました。。
- この程度の強度なら毎日いけます。最近やっている緑 streak の方がキツイですね。典型的な実装は追いついてきたので、 1 問 6 時間みたいなシーズンが過ぎてくれると良いのですが。
ABC 293: 3 完 (36:13) (3752 / 7935)
- A: 基本に戻って再帰関数でマッチして処理
- B: 手続き型プログラミングが無難です
- C: 全探索
- D: DFS. なんでこれが WA なんだろう………
  - 終了後 Union-Find に変更して AC. うーむ
  - テストケースが公開されたら DFS で通せるようにする
- E: 等差数列の和なのですが、答えが 0 の場合等式変形で詰まってうーむ
ABC 294: 5 完 (47:03) (1383 / 6581)
- A: 最速はもらった！
- B: 最速はもらった！
- C: HT.mergeBy でやると簡単です
  - 後から 2 分探索で番号を振るのも確かにアリですね
- D: クエリ処理 (茶 diff では……？)
- E: 再帰関数 (茶 diff では……？)
- F: 全探索しようにもメモリが足りません。むむ……
ABC 295: 3 完 (20:24) (? / 7737)
- A: 1 行目を捨て忘れてハマりました。
- B: 強引に AC.
- C: Mutliset 的な IntMap で。
- D: マージできなくて考察失敗。。連続部分列？
  - ある種の累積和ですか……
ABC 296: 3 完 (40:25) (4680 / 7617)
- A: 最速はもらった！
- B: 少し混乱しました。
- C: 自前の bsearchは添字を返すんですよね (敗北)
- D: 敗北。 $b = x / a$ で求まるため、片側の整数の探索の範囲を狭めるだけで良かったみたいです。商列挙は $O(M)$ が典型か……！
- E: ゲームは苦手です。もとい、読解力
- F: あと一歩と思いきや全然……
- G: 典型らしい……？
ABC 297: 5 完 (104:49) (1533 / 6692)
- A: OCaml の人と同着です。
- B: 最速はもらった！
- C: 最速はもらった！ (今回 Haskeller は少ないか)
- D: 灰 diff 的失敗でペナルティを負いました orz
- E: よく考えると普通に fold で解けました。ここまで茶 diff の早解き回か。
  - IntSet に deleteMinFind が入っているのは非常に良くできている気がして来ました。
- F: 解析的には標準偏差の積だと思うのですが、 DP 的解法を思いつかず。グリッドがループしていれば固定できるのだけれど……
- G: ゲームも解けるようにならないと

以降は Twitter で

toyboot4e

茶 diff, 灰 diff も十分難しい件

ABC 275 C
- 次元を落として全探索
ABC 292 C
- 大胆に素因数分解 (定数倍の高速化は止めよう)

toyboot4e

解き直し

緑 diff streak 週間ですが、余力があるときに消化していきます。

典型 001
- 好きな問題なのでもう 1 周やりました。
- 何段階も罠があって良問です。最終的には「答えで 2 分探索。
- もうあの頃の私とは違うのだ……！ (1,235 行のテンプレートをひっさげて AC)
ABC 286 E
- コスト値が 2 次元な Dijkstra
ABC 281 D
ABC 277 E

toyboot4e

TDPC

EDPC は 2019 年、 TDPC は 2013 年。類題の補充に利用します。

☆ TDPC I
- 区間 DP という事前情報があっても区間 DP に見えない……！
- いやーむずいっす
- たぶんアキバ氏のハンドルネームが iwi だったのか

toyboot4e

ABC 過去問

メモしなければ……

☆ ABC285E
- 解説を観ましたが大分難しい……。解いても実力にならないかもしれません。
- 部分問題を区間 DP にすると分かりやすくなりました。 AC 。
- 問題全体を区間 DP として捉え直した方が簡単ですね。

toyboot4e

PAST 過去問

PAST 2020-04

K
() のバランスというシンプルな DP. ( と ) の数が揃えば良いわけではなく、 )( などは禁止ですね……

PAST 2021-09 (第 8 回)

11/15 まで自力で解けました。尺取り法は AC したかったな……

☆ H 最短経路
木の上で長さ K の経路が存在するか。 DFS しつつ、累積和の中に K - len が含まれるかを調べます。全頂点から (もしくはすべての葉から) DFS して答えが求まります。
I /2 and *3
やるだけ。
J 数列の反転
まあセグ木ですよね。
☆ L 数列の反転
考察はできたんですが実装がダメでした。尺取り法。
M バランス
PAST 本に解説は載っていますが相当難しくないか……
N ジグサグな数列
楽勝！
O 色分けトーナメント
これは全然わからない。

toyboot4e

典型 90 問 (★ 4 〜)

☆ 066
- 考察失敗。実装も場合分けがそこそこ大変でした。算数力……
- 部分問題は全探索で良かったか……！

toyboot4e

精選 100 問

典型 90 問とは別に分野別で演習できるのは良いですね。

TODO

toyboot4e

Atcoder Library Practical Contest

最近 Chokudai Speedrun の転倒数が出たので、典型収集の重要性を認識しています。問題は、出るのか以上に習得が間に合うか……！

C: 原点と一次関数に挟まれた格子点の数に相当するそうです。

toyboot4e

典型アルゴリズム問題集

PAST 中級本の練習問題集らしいです。躓いたら中級本も買っていいかもしれません。が、鉄則本 + EDPC の経験でサクッと解けそうな気がしています。

toyboot4e

締め

日報に移動します

このスクラップは

ノート

アルゴリズム

鉄則本 基礎問題 (a 問題) の進捗

問題の種類

1. 全探索 [DONE]

2. 累積和 [DONE]

3. 2 分探索 [DONE]

4. 動的計画法 [DONE]

5. 数学的問題

6. 考察テクニック [DONE]

7. ヒューリスティック

8. データ構造とクエリ処理 [DONE]

9. グラフアルゴリズム [DONE]

10. 総合問題

感想

もう一度解きたい／類題を解きたい問題

感想

本の内容に関して

本の使い方に関して

本の難易度に関して

鉄則本に無かった内容

典型 90 問 (〜 ★ 3)

リンク

環境構築

実装

所感

〜緑 diff 50 問 [挫折]

予定

12/27

12/28

12/29

12/30

12/31

01/01

01/02

01/03

01/04

Educational DP Contest (A ~ E)

ABC ノート

鉄則本 C 問題

前半

後半

Chokudai Speerun

S001 [Done]

S002

緑 diff streak [完了]

茶 diff, 灰 diff も十分難しい件

解き直し

EDPC (F ~ Z)

TDPC

ABC 過去問

PAST 過去問

PAST 2020-04

PAST 2021-09 (第 8 回)

典型 90 問 (★ 4 〜)

水 diff streak

AC streak

AC streak (再開)

重い

精選 100 問

TODO

Atcoder Library Practical Contest

典型アルゴリズム問題集

締め

鉄則本基礎問題 (a 問題) の進捗