典型なのか典型じゃないのかよくわからないテクニックっぽいやつをまとめようとした

はじめに

ちょっとTLで話題になったので書きました。
半分自分用のメモみたいな感じで、緑〜青の人が知っていそうな/知っていると役に立ちそうなテクニックみたいなものを列挙していきました。
僕自身赤色つよつよコーダーな訳ではないので、言ってる事にいろいろガバがあったり、文字を打つのが苦手なので日本語が怪しかったりする所があります。(ごめんなさい…)


まだ怒られなさそうなやつ


解を決め打った時に判定できるなら二分探索！

最小となる...を求めよ、みたいな問題で解を決め打った時に達成できるかの判定が簡単な場合とか
D - Widespread
D - 壊れた電車

ゲーム系とかは逆操作を考える！

状態を上書きする系の問題は逆順に見ると1度決めた所が上書きされなくなって楽らしい
終端状態から遡るのはゲーム系の典型でもある
B - Contiguous Repainting
C - Knot Puzzle

絶対値最大化は+-を決め打ち！

正方向に最大化するパターンと負方向に最大化するパターンを決め打って両方のパターンを調べるといい場合がある
D - Patisserie ABC

二次元グリッド左下移動数え上げでHWが1000以下とかはどうせDP！

どうせこれで解けるので
F - 通学経路
E - 通勤経路
F - お土産購入計画 (Gifts)
F - 屋台 (Food stalls)

最適なケースが定数個に収まるなら全部やる！

条件を満たすパターンを考えると数パターン程度に収まる事があって、そういう場合はそれを全部試すといい
D - Lazy Faith
C - Chocolate Bar

ビット演算による最大化は上位から貪欲！

例えばK個選んでand演算した結果を最大化、みたいな問題は上位bitから貪欲にやればいい
B - Sum AND Subarrays

階乗の約数はそれぞれの数ごとに素因数分解！

すごい典型
C - Factors of Factorial
D - 756

括弧列は"("で+1して")"で-1した累積和！

部分列が括弧列になっているかの判定はa[l]とa[r]が一致しているか、[l,r]のminがa[l]より小さくなっていないかでできる
C - 部分文字列と括弧

和が0の区間や和が倍数の区間の個数は累積和+map！

累積和を取って、mapに個数を保持してからN*(N-1)/2をすると解ける
D - Candy Distribution
A - Zero-Sum Ranges

木とグリッドグラフは二部グラフ！

性質として覚えておくと解ける事がある問題がある
C - 広告
E - 木と整数 / Integers on a Tree

制約に40とか30とかあったら多分半分全列挙！20とかは多分bitDP！16とかなら多分3NのbitDP！

制約から決め打つのも戦術なのでやってみると便利
D - 徒競走
C - 部門分け
D - ナップサック問題

辞書順最小は前から貪欲！

すごい典型 辞書順最小と書いてあったら基本的に先頭の文字から決めていけばいい
C - 次のアルファベット / Next Letter

x軸とy軸を独立に考える！

独立に考えられる時はそれをするといい
D - FT Robot
E - CARtesian Coodinate
A - Affiches

ゲーム系はとりあえず小さなケースで実験！

詰まったら実験、というよりも考察の第一段階ですぐ実験するぐらいでいい気がする　特に変数の少ないYes/No問題で全探索が有効
D - ABS
D - Alice&Brown
H - 8^kゲーム
E - Tozan and Gezan

式で表せる場合はとりあえずそれを書いて式変形！

ぼくはこれを使って問題を解けた事がないですが…
D - 井井井 / ###

最小全域木はクラスカル法の気持ちになる！

辺の数を減らしたくなる場合など、クラスカル法について考えると確実に使われない辺がある事がわかる場合がある
C - Gr-idian MST

円環は長さを2倍にするとバグりにくい！

いちいちmod Nをするよりこうやって計算する方がいい
D - Static Sushi

倍数の場合だけ判定する場合などは調和級数を考える！

for(int i = 1; i < N; ++i)for(int j = 0; j < N; j += i)がO(NlogN)になるので、通らないと思ったものが実は通る場合がある
E - Grouping
F - チーム分け
G - Chicks and Cages

ゲーム系は相手の行動の逆操作が最適な場合を考える！

相手の動きをそのまま返して膠着状態にする、みたいな手が有効な場合も多い
A - Taro vs. Jiro

N<=40ぐらいで片側半分を決めた時にもう片側がすぐ決まるなら半分全列挙！

片側の集合を決め打って考えた時に、もう片側の最適な選び方や条件を満たすパターン数がO(1)とかO(N)程度で求まる 場合に半分全列挙がすごい有効
G - Mixture Drug

構築はとりあえず2ベキか市松模様かヘビっぽい形を考える！

構築が出た時にとりあえずこの辺は試しておくとよさそう
D - All Your Paths are Different Lengths
D - Grid Coloring

差の絶対値の総和の最小化は中央値！

中央値は気をつけないとバグりやすいので注意する
E - CARtesian Coodinate
C - Linear Approximation

中央値は二分探索！

そのまま適用できる事は少ないけど、中央値に関する問題を言い換えたりする事ができて便利な事がある
D - Median of Medians

最大値の最小化は二分探索！

最大値を決め打った時の判定が楽な事が多いので、最大値の最小化が出た瞬間に二分探索を疑った方がよさそう
B - チーム決め

平均が一定になる組み合わせは先に全要素からそれを引いておく！

これをすると選んだ個数について考えなくてよくなる
E - Meaningful Mean
C - 高橋君とカード / Tak and Cards

英小文字は26字しかないからbit全列挙ができる！

時々使う気がする
D - Yet Another Palindrome Partitioning

数列の区間に関するクエリはセグ木か平方分割を試す！

これすごい怒られそうなんですけど、とりあえずこの2つを使ってできるかどうか考えるのは有効だと思う
C - 倍数クエリ
D - Dangerous Hopscotch
E - Hash Swapping

マンハッタン距離は45度回転をすると軸を分離できて便利！

x'=x+y,y'=x-yとして、マンハッタン距離はmax(abs(x'1-x'2), abs(y'1-y'2))になる
E - Equilateral
D - 博覧会

並び替えて回文にできる場合は各文字毎の出現数のうちの奇数の数が1つ以内！

使いどころが微妙だけど使えると楽しい
D - Yet Another Palindrome Partitioning

Yes/Noの構築は自明なNo以外全部できると仮定して解く！

N<=100とかならフローを使う！

これたぷ〜(ありがとうございます:man-bowing:)



怒られそうなやつ

最悪テクです

Yes/No判定や場合分け問題はassertとかabortつけて投げる！

「Yes/Noで答えて、Yesなら構築せよ」みたいな問題はYesの時だけREを吐かせて、提出時にWAが出なかったら少なくともNo判定をしたものは正しい事が分かる

部分点狙いなら関係ないケースは強制終了する！

これは最悪テクではないですが、これをするとTLE連発をしないのでジャッジへの罪悪感が減ります

証明のない貪欲とか一見嘘解法に見えるやつもとりあえず投げる！

WAを吐いたら嘘、全ケースACだったなら(たとえ実は嘘でも)得点が貰えるので勝ち

同じぐらいのレートの人や得意分野が似ている人の順位や各問題の提出状況を見る！

配点に対して明らかにAC者数が多い問題はやる価値あり。自分の方が順位が高いといい気分になれる

二分探索や三分探索の時はちょっとだけ多めに値を取って試す！

特に三分探索はバグらせやすいので、こういう事をすると役に立つ場合がある

なぜかWAを吐いた場合はintを全部long longに変えて提出する！

一般に広く普及している最悪テクで、これをすると通る事が割とあって精神によい

制約が小さいなら埋め込み！

最悪をすると通る場合がある
D - うほょじご

なんとなく単調性が見えたら二分探索！なんとなく凸に見えたら三分探索！

なんとなくそう見えたらとりあえず書いて投げるとよくて、特にABCだと実は嘘だったとしても割と通る
D - Various Sushi

番兵はたくさん置く！要素数はたくさん余計に持つ！にぶたんの初期値の幅は大きく取る！

定数倍がほんの少し悪くなるとしても誤差の範囲内なので、こういう事をしてしょうもないWAを減らす

bitsetを使って定数倍高速化をすればオーダーがヤバくても通る場合がある！

bitsetとかmap→unordered_mapとかGCC→Clangとかにぶたん→しゃくとり(オーダーレベルの高速化)、数ケースだけTLEする場合は定数倍を頑張って落とすとよい 時々これが想定解になる事がある
D - No Need
C - Median Sum