Top

メモ - ぺんぎんノート

何か書きたくなったらここに書きます。

$f(x)$から$f(x+1)$と$f(2x)$を求めることができれば、$f(x)$は$O(\log x)$で求まる
乗算は、指数に注目すると加算になる。加算では行列累乗が使える
int dx = (i - 2) % 2, dy = (i - 1) % 2;
実装の重い問題では、map<int, map<char, vector<string>>>などを使うことがある。逃げないこと
頂点の次数を数える方法で楽なのは、辺の入力時についでに数えるという方法
重みのないグラフに重みを持たせることで解ける問題がある
「木があって、辺が交わらないように円周上に頂点を配置する方法は何通りあるか」は木DP
メモに残せない系問題が多い（Adhocな思考が要求される）
条件を満たさない状況をひとつずつ丁寧に排除していく系の問題がある。苦手な人が多い印象
$a+b=a \otimes b$を満たす$(a, b)$はビットに注目

グリッド上で4方向に累積和。2方向よりもシンプルになることがある
指数のmodは底のmod-1で取る
添字が難しい二分探索の問題をバグ無しで解く方法はまだ確立できていない
$S$と$T$の両方向からダイクストラをすれば、最短経路が求まる
ダイクストラに数行コードを足すだけで、最短経路は何通りあるかが求まる
「周期性のある数列の$N$番目までを足した合計」などを求めるときは数学を使う
こういった問題は$300$点問題でよく出る印象。$500$点以上では部分部分で使われる。慣れること
優先度付きキューとdequeの存在を忘れないこと
配列の要素を削除して左詰めする操作を、シフト量をBITに保存することで$O(\log N)$で実現
フローは今のところ使わない
通常のfor文を、「[0, 1)〜[N-1, N)の範囲を見る」と考える
座標をベクタ配列に追加してソートすれば、それだけで座標圧縮したことになる
dp配列を作るときは、とりあえず必要そうな状態を全部突っ込む。あとで減らす
公差$d$の等差数列は、要素を$d$で割ることで公差$1$の等差数列になる
期待値を求めるときに、dpを使わずにただ定義通りに実装すればいいことがある
数学の命題を使うと考察が捗ることがある。逆に使わないと、複雑で訳がわからなくなる
行列の単位元を作りたいけど、RustでもHaskellでもうまい方法が見つからない
しゃくとり法は、for文のブロック内のある範囲を「必ず条件を満たす範囲」にするとバグりにくい
しゃくとり法の最後の一行はif (l >= r) r = l, acc = e;とする
グラフ関連の証明を勉強して、グラフに対する感覚を養っていきたい
行列のランクをまだ勉強していない（理解はしているけど、使い所がわからない）
01BFSのときに使うdequeには、高々2つの距離しか保存されない
まだ、遅延セグ木をバグなしで使える気がしない。おそらくまだ何か勘違いしている
累積和の代わりにセグ木を使うのもいいかもしれない
セグ木上の要素の削除を、単位元による更新で行っているのが面白かった
順序を無視できるものについて、ある順序に並び替えることで解ける問題になることがある
↑この解法かなり好き
考察は再帰のようなもの
累積和は方向に気をつけないといけないけど、セグ木だとその必要がなくなる
Trie木の型はvector<map<char, int>>
「個数」という扱いにくいものを、「最大値」という扱いやすいものにする
貰うDPは式で表しやすく、配るDPは式で表しにくい。どちらを使うかが自分の中でまだ決まっていない
グラフに関するアルゴリズムの計算量を明確にしておきたい
数え上げ問題がまだ苦手
高難易度の問題を安定して自力で解けるようになることを目標とする。早解きを目標としないこと
modを取ってdpの状態数を減らす
必要なのが前の状態だけのときは、dp配列のサイズを大幅に減らせる
3つのポインタ。真ん中のポインタを固定して、左右のポインタはしゃくとり法 ← 実装難易度高め
二乗の木DP。葉の状態はすぐに定義できるけど、親がどうマージしていくかについて考えるのが難しい
実装に困ったら他の人のコードを参考にする。写経すれば自然と理解できるので手を動かすこと
全方位木DPが理解できた。最初は普通の木DPで子→親の方向に更新、次は親→子の方向に更新
こちらの実装が理解しやすかった
mapに順序付けしたいときはmap<char, int, greater<char>>という風にする
考察と実装の間に乖離があることを理解する。たとえば、ぷよぷよでぷよが消える条件は「4つ以上繋がっているとき」と一言で言い表せるけど、実装するとなると、再帰や配列外参照について考慮しなければならない。その事実から目を背けないこと
Codeforcesでは、実装が重いだけの問題に対して批判的なコメントをすると、沢山の高評価を貰える傾向にある。Twitterでも、こういう問題に対して批判する人をたまに見る。だからといってそれが、問題を解かない理由になるわけではない。ついこういう問題からは逃げたくなるけど、逃げないこと！！（再三自分に言い聞かせる）
キューから要素を取り出すとき、「今ある分をすべて取り出す」ような実装が必要なことがある
「敵の体力が$N$で、1回の攻撃で体力を$M$減らせるとき、最低何回の攻撃で敵の体力を$0$以下にできるか」という問題は、本当にいたるところで出てくる
区間DPとゲームDPは、DPを書くときの思考パターンが同じ
区間更新や一点取得など色々あり、どれを使えばいいかわからなくなる。マトリックス図でまとめておきたい