競技プログラミングの解法

自分なりの競技プログラミングで疑う解法まとめ

とりあえず疑うもの(考察に困ったらこれ)

• これまでの考えを一度捨てる
  • 嘘解法を永遠に考えている可能性がある
  • 一度まっさらにしてこれまでの考えをやめよう、新しい解法が見えることがある。
• 二分探索
  • 基本的にこれは必ず疑おう
  • 計算量が大きい時
  • 一定の単調性があったら使う
  • 絶対疑おう
  • 左からとか右からとか、DPと組み合わせたり、両側からするぞ！！！！！
  • Writerは当然隠そうとしてくるので二分探索の意識は常に持つ
• DP
  • まあDPですよね
  • DPは最後の求めたいものから考えて、分ける状態を決めて、遷移を決める
• 逆から見る・後ろからやる
  • まあ逆ですよね
  • 操作も逆にするあれですよね(追加削除)
  • 後ろからを見るし、逆に反転もあり
• 全探索
  • 意外とある
  • うまいことやると1~Nの全探索だったり枝切りだったり、式変形でなんとかなる
• ビット演算
  • これですよこれ
  • Nが小さい時や、ビットDP
  • N=6~20
  • 14~以上はBitDPになる
• ソート
  • まあとりあえずソートですよ
• Greedy
  • Greedyする、複数のGreedyの可能性
• 複数問題に分ける
  • 問題が複数絡み合っていることがある。
• 高速化
  • 部分累積和
  • いもす法
  • セグ木などなど
• ループ外側に出す
• 最大・最小を変換する
• クエリをまとめる、逆にする
• 式変形
  • 式にするとうまくいくことがある
• グラフ・木にして考える
• トポロジカルソート
• 上界・下界判定
• 包除・余事象
• 一つ、真ん中を固定する
• 木・グラフなら、グラフにできそうならグラフの項目を見る(下にある)
• 等差数列
  • 同じ繰り返し構造があったら使える
  • 初項と次項から公差が求まる˙

用語集

• 全探索
  • 基本中の基本
  • 計算量文回せる時
  • 処理が面倒なとき全探索でごまかせないか考えよう
• 繋げる
• 重ねる
• 割る
• 独立したものに分ける
• まとまりごとに考える
• 圧縮
• 絶対値
• 絶対値は正と負に分ける
• 累積和
• 図を書く
• 場合分け
  • 小さい数
  • 倍数などに注意！
  • 文字にも注意！
• 前処理をする
  • クエリを先計算やクエリの処理をソート
  • 関係ないものをforの外側でやる
• 次元を減らして考える
  • いらない添字を考える
• 後ろからやる
• 逆にする
  • ソートや逆にソートする
• 逆から考える
  • 操作の逆順や状態の逆順
• 操作の逆を考える
  • 追加と削除など
• 最後から考える
• 最大値・最小値
  • 最大値を求めるときは最小値を求めるときでもある
• 大きい方から・小さい方から
  • ソートしてGreedy
• 最大最小変換
  • 最大値を求めるときは最小値を求めるときでもある
• 点の移動
• 型サイズ
  • size()はintではなくunsignedなのでマイナスになると即オーバーフロー
  • LLにしとこう
• ビット演算
• XOR
• LCM/GCD
• EXTGCD
• ループを何とかして減らす
  • 中身を外に出したりする
• 制約条件から減らす
• とりあえずソート
  • 大事
• 広げる
• 性質を列挙する
  • なんでもいいから書く
• 変数を使用した式を使用してforで回して最小値・最大値を取り出す
• 図にして書く->声を出しながら考える
• とりあえず書いてみる
• 小さいほうから全部紙に書いてみる
• 伸ばす
• ソート
• データ構造
• 数式を作って変数をforで回して全探索する
• 数式変形
• 条件の列挙からの圧縮
• 再帰関数
• 変数を一つにする(ゲーム・最大化・最小化)
  • ２つの要素があるとき(L - R)などで最大化最小化は片方からみると同一視できる。
• 二つの差をとるとき、片方を固定する
• 真ん中を固定して左右を動かす
• 真ん中を考える
• 大きいものから小さいものを引く（条件・包除原理）
  • 包除原理
• パット見包除だが、実は普通の数え上げ
• 符号・絶対値の全探索(-1をかけるか、かけないか)
• 実験的に値を取り出し、法則性を考える
• 計算量から逆算する
• 余事象
• 二部グラフ
• 二分探索
  • 最大・最小にも使える
  • 連続しており、最初と最後がT/Fと必ず異なれば複数解のどれか一つを取ってくる。
• 中央をとる
• どれか一つを固定する
• グラフの問題に変換する
• 区間スケジューリング
• IDは一箇所に保存する
• 丁度の条件判定は無理だが、満たす上界・下界判定は出来る。
• グループ化
• まとまりごとにして考える。
• ボトルネックに着目する。
• 計算領域は実は小さい
  • K-th Substring系
• 計算量が余裕な箇所のみで全探索するときがある。
  • すべては無理だが、X,Yの配列のみなら全探索できるなど
• 両端・片端から考える
• ちょうどKは(K以下)-(K-1以下)
• 共通の素因数は、最大公約数！！
• 線形な計算、例えば、x個連続していて、ボーナスY(x-1)などのとき、分けて考えられないか考える
  • 線形な一次の比例は、小さく分けて計算できることに注意する！
• 問題のある箇所を言い換える
  • もっと分かりやすい形や、違う状態に同じだが違うことを指すように言い換える
• 最後の状態を考えて１手戻す
  • 最後の操作一回を考える
• それぞれは独立している
  • 意外と個々の状態や、操作が独立していることがあり、別々に計算できたりする
• 観察をする

未分類・テクニック

• 部分累積和
• いもす法(部分累積和)
• 括弧問題
• 尺取法
• while構文
  • Dがwhile後になってほしい条件
  • while(not D) then do;
• i = 0, j= 0構文
• 半開区間
• priority_queueでN個の最大値を持ち、最小値を吐き出すことである区間の連続したNの個の最大値を持てる sum変数もいる
• 順列
  • next_permutationのアルゴリズムを使う

貪欲法

• そのとき行える最大限いい手法を取る
• 良い手法のなかでどれがその問題をきちんと解けるか考える
• dpも疑う
• ソート使える
• Greedyのお気持ちにちゃんとなる
• 途中で方針が変わるGreedyに注意する

動的計画法

• DP
  • 最後の求めたいものから考える
  • その後に状態を決める
  • そして遷移を洗い出す
  • DPはDAG
• 逆ナップザック法(データサイズによって重さと価値を逆にする)
• LCS問題
• 桁DP(再帰関数)
• インラインDP
  • MLEするときは、毎回2つの配列のどちらかを初期化するようにすると同時にいっぱいあるわけではないので間に合う
• ビットDP
• ゲーム理論DP
• ビットDP
• 配る・もらうDP
• 高速化は貰うほうがしやすい
• データ構造や累積和で高速化
• 数え上げDP
  • 選択した時点で数は増えない
  • 選択肢が多いから膨大になる。
• DP復元
• トポロジカルソート
• 行列累乗
  • Nが小さい
  • 繰り返し回数が大きい
• 文字列DP
  • 後ろN文字や〜〜A,〜〜ABなどの出現なども使う
  • 多次元になりやすく、添字を工夫する
  • 後ろ一文字が多いけど、複数文字もある
• 初期化チェック
  • それ正しい初期化してる？

データ構造

• プライオリティキュー
• ヒープ(二分木・大小・priority)
• セグ木
• 遅延評価セグ木
  • 結構処理が重いので注意する
• ポテンシャル付き・重み付きUnionFind
• set
• multiset
• multimap
• unordered

木

• 幅優先探索(queue)
• 深さ優先探索(stack)
• 再帰関数
• 最小全域木
• 二分探索木(set・map)
• Union-Find(グループ分け)
• • セグ木
• 遅延評価セグ木
• 根付き木
  • 根を考えることでうまくいったりする
  • 根から考えたり、葉からボトムアップに処理できるようになる
• LCA
• 次数に着目する
• 木の深さに注目する
• 葉からみる
• 根から見る
• 部分木の深さを考える
• 節を考える
• 木の直径
• 橋・関節点
• グラフを木にする
• パスの両端に着目する

グラフ種類

• 無向グラフ
• 有向グラフ
• 連結グラフ
• 森(無連結で閉路なし)
• DAG(有向グラフで閉路なし・順序関係とみなせる)
• トポロジカルソート(DAG→DPに変換)
• 根付き木グラフ(DFSで木にしてしまう)

グラフ

• 幅優先探索(queue)
• 深さ優先探索(stack)
• ベルマンフォード法(始点sから各点への最短距離を求める　エッジが負でも使える)
• ダイクストラ法(始点sから各店への最短距離を求める　エッジが生の場合のみ使える)
• プリム法(最小全域木を計算する)
• ワーシャルフロイド法(三重ループで全点最短経路を求める)
• 経路復元
• 最大流(最大マッチング)
• 連結成分(UnionFind)
• グラフを木に変換する
  • 本質的に木を考えて良い時、処理を単純化するために木を使う
• 二色グラフ
  • 二色に塗れない時、奇数の長さのループが存在する
  • 閉路がない、あっても偶数帳なら二色グラフ
  • UnionFindでも判定できる(動的)
• マイナスのコストの辺を考える。
• 次数に着目する
• オイラー、ハミルトンを考える
• 辺の数を増やして考える(2回同じ辺を通っていいなら2本にする)
• 自己ループ・多重辺などの場合分けに注意する
• トポロジカルソート
  • トポロジカルソートでは、優先順位・強度・強さ・順番などの一方向性がでる。
  • 複数解あるかどうかは、while内でsize()=0を判定するだけで簡単にできる(数え上げはBitDP)
• 頂点または辺のみに着目する
• 葉・根
• LCA
• 条件付き〇〇
• 辺を伸ばす
• BFSのみで辺を伸ばすとは限らない
  • QueueやDequeで二頂点ごとに伸ばしたり、while(Q.size())の間ずっと伸ばすわけではない（伸ばせなくなったら即辞めるなど）

探索

• 二分探索
  • 余分にアホみたいにINFをぶちこんでQOLをあげよう
• 三分探索
  • よくわかってない
  • 二次関数みたいなグラフで使えるらしい
• 線形探索
• 幅優先探索(queue)
  • 先にtrue判定しようね！
  • 一つのキューに複数を最初に入れればそれらの頂点からの距離の最短がでる
• 深さ優先探索(stack)

文字列

• 文字列DP
• 反転
• 先頭
• 末尾
• 貪欲法(Greedy)
• 26文字ごと
• bitDP
• ソート
• 末尾から何文字かのDP
• ローリングハッシュ
• MP
• KMP
• 右から見る
• 二分探索
• 数値に変換する

ソート

• バブルソート
• クイックソート
• マージソート
• 昇順
• 降順
• pairの二価値ソート
• tupleソート

組合せ論

• 組み合わせ
• 重複組み合わせ
• 順列
• 二項定理
• パスカルの三角形

数学

• 確率で割ると期待値となる
• 期待値の線形性
• 期待値は複数の問題が絡む
  • 期待値が別の期待値の確率変数となることがある

構文解析

• 再降下式

---

デバッグ

• 問題文読みミス
  • サンプルもちゃんと読んで考え方あっているか見直そう
• continueとbreakミス
  • return0 もやりがち
• エッジケースミス
• 場合分けミス
• 初期化ミス
• || &&ミス
• 添字ミス
• for文の添字ミス
• そもしもcinしてないミス
• getline系ミス
• long long ミス
• 0-index 1-indexミス
• y, xの順番ミス
• first, secondミス
• bitwiseのxor, or, and見間違えている説
• そもそも答え合ってないよミス
• 大きい、小さいの勘違いミス
• 問題文読み間違えてるミス
• 計算量ミス
• 再帰関数bfs, bfs1など数字間違っているミス
• 変数のp1, t1ミス
  • ありがち
• N, Mなどの変数勘違いミス
• 文字列Sとその長さNなのに、サイズにしてたりNを取ってないミス
• size()はunsignなのでマイナスにオーバーフローミス
• 0のときを考えてないミス
• while抜けて無いミス
• イテレータミス
• long longにオーバーフローミス(二分探索など)
• $N=10^{18}$などのときは、どこかの計算でオーバーフローしてないかチェックする