Skip to content

Latest commit

 

History

History
167 lines (164 loc) · 5.86 KB

SHOULD_OPEN.md

File metadata and controls

167 lines (164 loc) · 5.86 KB
Raw

コンテスト前に開いておくこと

  • flatten.rs
  • arc30b.rs
    • arc32b.rs
  • arc51a.rs
  • arc113d.rs
  • abc14d.rs
  • abc16d.rs
  • abc32a.rs
  • abc73d.rs
  • abc153f.rs
  • abc197d.rs
    • 複素数使って、角度と距離を変えるやつ
    • 複素数のベクトルはかけると長さが積になり、角度が和になる
  • abc214d.rs
  • abc222e.rs
    • 経路復元
    • 辺の利用回数の取得

使いたいコピペ

  • repeat_square

  • gcv

  • lcm

  • LCA // lowest common ancestor

    • 木上の二点間の頂点も求められる
    • 頂点u,vのパスの間にaがあるか判定
      • u-aの距離 + a-vの距離 == u-vの距離の時に存在
    • i個上の頂点を求められる

  • com

    • 10^6くらいまでのnCkが求められるやつ(abc167e.rs)

  • mod_inv

    • directly_using_choose.rs
    • nCkとかでnが変動するケースに使う

  • ModInt (Modの計算を扱う際にコピペすること)

    • abc238c.rs
    • abc162e.rs // ModInt用のrepeat_squareがある

  • Binom(nCk, 組み合わせ。nが大きい時)

    • 単純にMODの割り算がしたい場合はmod_invだけ使う

  • prime_factorization // 素因数分解

    • sieve // エラトステネスのふるいの変形
      • abc172d.rs 約数の個数を求める変形

  • upper_bound, lower_bound

  • Fenwick

  • heap_recursive

  • ベクトル

    • 垂線引くやつ

  • union_find(sizeが使えるやつ)

    • 小さければ自己交差とかも求められる
    • abc279f.rs
      • 逆引きできるようにして集合のマージまでサポートする

  • kruskal(最小全域木)

    • kruskal_problem
    • abc282e.rs
      • ある得点の入る動作を木として表現でき、その動作で得た特典の合計の最大値、最小値を求めたい際などにも使える

  • LazySegmentTree(遅延セグ木)

  • permutation

    • 最初にsortをするのを忘れずに

  • dijkstra

    • 経路復元付き
    • abc252e.rs

  • bellman_ford (ベルマンフォード)

    • dijkstraより遅いが負のループを検出できる

  • Warshall Floyd(ワーシャルフロイド )

    • O(V^3)
    • 全ての点から点への最短距離が検出できる

  • topological_sort

  • create_primes

    • 素数列挙(O(n)注意)

  • compress

    • 座標圧縮(abc217d.rs)
    • 簡単だが書くと面倒、時間がかかる

  • 強連結成分

    • typical90_21.rs

  • オイラーツアー

    • abc202e.rs

  • SegmentTree セグメントツリー

    • 一点更新、区間取得
      • abc245e.rs (min)
    • O(logn) insertの二分探索 (abc217d.rs, abc241d.rs)
    • lower_boundが使いたい + O(log n)でremoveしたい
      • segment_tree_and_lower_bound.rs
      • abc260d.rs

  • LazySegmentTree 遅延セグ木

    • 区間更新、区間取得
    • 区間の最大値(値の更新と値の設定ができる)
      • typical29.rs
    • 区間和用
      • abl_e.rs

  • 三分探索(凸性を持ち極値が1つの場合のみ使える)

    • past202104j.rs
      • 一定の回数やるやり方
    • abc279d.rs
      • leftとrightの差分が一定以下になるまでやるやり方

  • 最大流/最小カット(FordFulkerson)

    • startとgoalを足して、流量を1にすれば二部マッチングもいける
    • abc10d.rs

  • 平方数の約数の数は奇数

    • task356.rs

  • ゲーム

    • dp_k.rs

  • 中央値、平均値を二部探索で求める

    • 各値からmidを引いて最大値 => 平均値の最大
    • 各値がmidより大きい場合1、小さい場合-1で0より大きくなるか => 中央値
    • abc236e.rs

  • 巡回セールスマン問題

    • 全ての点に行く必要があるやつ
    • 多項式時間で解けない
    • abc190e.rs

  • 2次元配列回転 (90°)

    • rotate90

  • しゃくとり法(尺取法、しゃく取り法)

    • syakutori.rs

  • 包除原理

    • 集合A,B,Cの和集合を求めることができるやつ

  • 編集距離(レーベルシュタイン距離)

    • insert、delete、updateで2つの部分文字列を一致させるのに必要な最小回数を求めるやつ
    • task315.rs

  • ローリングハッシュ(rolling hash)

    • O(1)で文字列が一致するかどうかが調べられる
    • rolling_hash_problem.rs
    • abc141e.rs

  • grid ループ 斜め 移動 bfs

    • abc258b.rs

  • 座標。回転。ベクトル

    • abc197d.rs
    • past202107i.rs
      • atan2を使ってradianを座標から求める
      • 任意のABベクトルの回転
      • hypot((x^2+y^2).sqrt())

  • 反時計回りに座標があるか時計回りに座標があるか。ccw, cw (外積)

    • abc266c.rs

  • ベクトルの外積の大きさが平行四辺形の面積になるやつ

    • abc2c.rs

  • 期待値

    • abc263e.rs
    • abc266e.rs

  • ループ検出

    • 無向グラフでも利用できる
    • abc266f2.rs

  • 平面走査

    • 二次元平面上でa <= x && y <= b の値がO(logN)で求められる
    • 具体的には部分配列のユニークな値の数とかが求められる
    • abc174f.rs

  • 二次元いもす

    • tessoku_book_i.rs

  • 永続データ構造、永続スタック

    • 親のindexを所持する配列とmapを作ることで
    • 論理削除のように非破壊的なpushやpopができる配列が作れる
    • abc273e.rs

  • float or doubleの特定の桁で四捨五入+0埋め

    • abc274a.rs

  • monotonic stack(単調stack)

    • 配列Aにおいてある要素a[i]の値よりも前(j<i)にあるより小さい最初の値(a[j])を効率的に見つけられる
      • ある要素a[i]が0<=j<=iの中で最小の場合-1が設定されている
    • monotonic_stack.rs

  • 巨大MOD

    • const MOD:usize = 2305843009213693951;
    • const MOD:usize = 100_000_000_007;

インタラクティブ interactive 問題用のベース

  • abc244c.rs