発想パターンメモ

コンテストで見かけた発想のパターンをメモ

左上と右下の関係の場合、DPでよい

右上と左下の場合、関数化した上で盤面を回転させるのが良い

実は行列の90°回転でなく、配列の行リバースで十分

vector<vector<int>> Aに対して、reverse(all(A))でおｋ

mod Mで割れるとは限らない→割り算をせずに計算する

構造に着目してダブリング

漸化式の行列で表せると行列累乗で求まる

順位表を見ると緑含めてかなり通してる

ライブラリかデータ構造で殴れる？殴れなそう

中国既出？惜しい。中国典型のMo's

あえて3つ組ということは、2つ組なら簡単な解法がある？

差の偶奇は変わらない

+0, +2, +4としても一般性を失わない

sum(mod6)は不変

A<B<Cに(+4, +2, +0)することでA=B<=C or A<B=Cになるので場合分け

今回は-2, 0, +2の方が良い（合計が変わらないので）

解候補を絞り込んで全探索

符号ごとに大小3つずつだけ考えればいいという雑エスパー

真面目に実験するなら、既にi, jが決まってる時の最適なkを考える

A=xi + xj, B=xi * xjを代入すると見通しが立ちやすい

k回繰り上がりが起こるならf(a+b)=f(a)+f(b)-9k

10^kで起こる繰り上がりの回数は、mod 10^kをソートして二分探索

ソート済み配列のマージは組み込みのstd:merge（不要）

「K番目の値」も判定問題＋二分探索

「砂糖水が濃度xになるために砂糖がどれだけ足りないか」でソートすると二分探索できる（蟻本p132）

「2^30>10^9だから30回でよい」はdouble型の値の保持の仕組みを考えると誤りで、100回くらい回すと安全

doubleを使わざるを得ないとしても、できるだけ誤差が出にくい式にした方が良い

Stern-Brocot Tree を探索することで誤差のない値を得られるらしい（未履修）

ちょうど2回出現するのでS.rfind('B') - S.find('B')でよい

priority_queueで解くのが簡単

最短経路問題をダイクストラ法で解いてると見なすことができる

包除はちゃんと図を書きましょう

解くだけなら実験してエスパーで良い

相手がL個取ったらR個取れると思うと、L+R周期なことが分かりやすい

10^xは前計算すると高速

実はdequeを持たなくても先頭のindexを管理すればよい

言われてみるとこれはロリハ

実は同時に投げたと考えてもいい（同時にゴールしたら先手の勝ち）

最大 - 最小の最小化は、最小値を固定して最大値の最小化

小数点入力は文字列で受け取るテク

ダブリングを知っています

みんな知ってるらしい

ライブラリ化する、練習するなど頭を壊さないのが大事

多重集合のZobrist Hashはxorでなく総和

適当に「長さ、総和、総積、min、max、偶数の数」などのセグ木で判定するウソも簡単

675点は人類滅亡する難しさ典型