AtCoder個人的な考察典型、解法典型まとめ

AtCoder

Last updated at 2024-12-22Posted at 2024-06-04

はじめに

PCのメモ帳に典型考察をまとめていましたが、内容が多すぎたのでQiitaをお借りして移動しました。ABCのE問題以下なら困った時に役立つ情報があるかもしれません、もしものときに参考にしてくれたらうれしいです。なお、自分の中でよく使用している謎な単語や、ミスしがちな注意点も書いているので典型のみの内容ではないことに注意してください。随時更新しています。精進の内容的にABCのD,E,F問題で抽出したものが多いです。

n敗してるやつ

ΣΣの中にある数字を主軸に見る ABC371-E

LかRを固定するやつ、左右動かす、oxの順を考えたら2^3=8通りあり得る(Lを固定して右か、Rを固定して右か、というのは「まだ見てないやつ」と「既に見たやつ」からもう片方のセーフを求めるという違いがある(どっちも右に動かしてる)) ABC377-D

似たような区間が条件を満たすなら、尺取り法をすれば各LかRを固定したときにもう片方がどこからセーフでどこからアウトなのかが求まればいい ABC377-D

解法がわからなくて困ったとき

使用する計算量がまだ何も定まってないなら、とりあえずの方針として何か決め打ちできる対象がないか考える、「何かの基準となる頂点を決め打ち」「LまたはRを決め打ち」「渡された数字じゃなくて、実際の数字を一種類ずつ見ていく」 ABC75-D ABC177-E

TLE前提の愚直解法を考えてみて高速化できるポイントがないか考えてみる(区間の値を回収してるなら累積和なりセグ木なりが使える)

制約に実はヒントがあるけど、問題文のサンプルが、サンプルの説明も含めて絶妙に解法がバレないように作られてることが多いので解法がわからない状態だからこそサンプルを自分で作って最後まで動かしてみるといい ABC179-E

数式が複雑なときは、1ステップずつ考えて、一個ずつ考えたそれらを組み合わせることでようやく問題の状況が整理できる。焦って考えると数式に対する偏見で負ける ABC179-E

TLE前提の愚直解法を実際にコードにしてみる。コードにしてみることで実は気づいてなかった部分に気づけて高速化ができる可能性がある ABC370-E

考察典型

「ちょうど1回+ちょうど2回...」が難しいとき「1回以上,2回以上...」を求めると「3回以上-2回以上=ちょうど3回」と求められる ABC384-F

・とりあえずソートできるか考えて、ソートして考える、複数要素の比較の場合は全てソートできる場合がある ABC354-C ABC309-F

二種類の要素でもソートして考えてみる、ソートしないとACできないDPに既に出会っている ABC216-F

・何を見ることができるかを解法やTLEはあまり気にせずできる実装を列挙する

・二次元平面、二次元グリッド、リーグ戦の図の3種類に並べて平面走査などができないかを考える ABC354-C ABC351-E ABC276-F
→二次元平面に変換できたなら平面走査またはセグ木がほぼ必ず使える ABC351-F ABC309-F
→平面走査とセグ木で求められるものを考えたら、逆に求められないやつを別で求める、セグ木の配列を減らしたいなら平面走査の軸を変える ABC306-F

→リーグ戦の総当たりの図として表すと、新しく追加されたときにそこだけ求めればよいとなる ABC276-F

・状況を図に整理して、そこから解法が考えやすいように何か変換できないかを考える、図形をずらしたり向きを変えたり、げたをはかせたりなど ABC311-F　ABC323-F
→斜め移動が来たら図形のずらしか45°回転を考える ABC351-F

・どんな入力であろうと、基準のnやmが決まっていたら絶対に貰える値、つまり不変量を求める、それがわかったなら入力によって変わる値だけを別に求めれば答えになる ABC306-F

・不変な値を消すと、操作内容や値の組み合わせによって変化する値だけを考察すればよくなる ABC268-F ABC306-F

文字で式を立てるとき今見てるiにとって管轄外のx[i-1],x[i-2]のような値は、それ関連をまとめて文字に表してしまう ABC240-F
どんな情報の内容だろうとしても、二種類の情報なら二次元にプロッドする ABC231-F
作成したやつを内側から広げていくみたいな実装を考える(メモ化再帰でも本当に内側から広げていくでもどっちの問題もある) ABC363-F ABC290-E
何かを領域とか区間としてとらえて、そのそれぞれの領域には切れ目があって、その切れ目を削除できるみたいな発想 ABC364-F ABC341-E

TLE前提などダメ元から考えるときの典型

TLE前提でガチな愚直解法を考える
問題文で二つ選ぶときは(i,j)を選ぶとして言い換えると式に表せる ABC215-F
TLEになる解法を考えて、今基準としている内容を基準にしている時点でどう考えてもTLEになるなと思ったら、別のものを基準として考えてみる(直感的にはO(T^2)を基準とする解法が思いつくがどう考えても無理なのでO(S^2)を考えて、次にO(S)にする方法を考えてみる) ABC260-F

貪欲法一覧

「日付の終わりor値が小さいやつ」から見て貪欲することで「貪欲していてさっきのを捨てたけどやっぱり後から採用したくなった」や「さっきまでは見られたけど日付が入らないから候補から削除したい」という状況が排除できる ABC137-D ABC160-E

貪欲法の考え方

ぱっと思いつく貪欲法を考えて、それのどの部分が最適解になれないかを考えると正しい解法が考えやすい、ABC137-Dなら前からお金のmaxを選ぶという貪欲を考えたとき、日付が進むにつれ最適解になるはずの仕事が日数オーバーで消えてしまうみたいな

2つの値があって、比較関数的にやるのが難しいとき、どうにかして1つの値だけを見るようにできれば貪欲法ができる、ABC137-Dのとき、後ろから見ることで一度pqに入れればそれが削除されることは一生ないという状況が作れることによって純粋なお金比較ができる

問題の状況を図で整理して、サンプルなどを実際に書いて見ると、動きが内容ごとに独立に見れたり数式として表すと何かに気づけるかもしれない ABC95-D

貪欲が難しいものを貪欲に見れるようにする

順序が大事なので、どういう順序で使用するのがいいかを考えたい。二つ選んだとして、どっちが先がいいか？というのを求めるために、それぞれの順番を不等式で表し、選んだ二つの要素がそれぞれ両辺に独立になるように式変形する ABC366-E

どういう順番で取っていくのが最適か？というのを考えて、下っていくときに貪欲を適応し続けられないけど、左右反転を考えると上りのコードを適応できる ABC167-F

累積和

1つも選ばないという選択肢が許されてるときは、絶対に番兵を入れた方がいい、入れないと事故る ABC95-D

累積和してその累積和した値で累積maxを求めるという問題がある(片方を決めたときにもう片方のどこが一番おいしいのか？を求めるときに使える) ABC95-D

隣合う同士にしか辺が伸びてないグラフのとき、二頂点間の距離は累積和で求められる ABC89-D

累積和の発想だけ借りて、数値自体はメモ化再帰で求めた方が実装が楽な場合がある(累積和の配列に対するインデックスを無視して、ただ数字を投げるだけでいいというのが強い)。f(x)=スタートからxまでの距離。という感じでメモ化再帰の定義として「スタートからの距離」を持たせるという発想がどこかで使えそう ABC89-D

数列の符号が統一されてる単調増加のとき、正なら左から、負なら右から順番に累積和をそれぞれに加算していけば広義単調増加数列が作れる(正の数列のときa[2]がa[1]を超えたいならばa[1]の値をそのまま加算してあげればよくて、a[3]ならa[1]を超えてるa[2]の値を貰えばいいのでそれを順にやっていくと、a[i]にはrui[i-1]を加算すればいいみたいになる) ABC81-D

前後から累積和する(O(N^2)とかのときにO(N)を消せる) ABC181-E

二次元累積和

ある長方形範囲のおいしさの総和みたいなのを求めるとき、二次元累積和じゃなくて、DPっぽくることができる。本質的な発想は二次元累積和と同じで余分な足し算を引き算しているという遷移 ABC005-D(解説pdfのやつがこの内容のやつ)

座標圧縮

座圧したときの面積は、i番目からi+1番目が欲しいなら[i+1]-[i]が答え、[[i],[i+1])という区間に存在する面積(長さ)を求めてくれる。二次元の面積なら横と縦をそれぞれ求めて掛け算する。iからi+5までが欲しいなら同じように[i+5]-[i]を求めれば[[i],[i+5])の範囲が求まる

縦で平面走査して、各縦で使うx座標だけで座圧すると、全体で見た時に生成したいもす法の配列のサイズの総和は「Σ=N220=210^5」となる(全体で使うx座標の座圧サイズを毎回生成すると(N*20)(N *20)でTLEかMLEする)JOI(折り紙)

lowerとかupperとかする系の二分探索

一番近い右と一番近い左を求める(lowerして[it]が右で、[it-1]が左) ABC119-D

[l,r)の形にできれば、r-lがその幅のサイズになる。[l,r]だとr-l+1となる ABC364-D

mapとかvectorに軸ごとに障害物の座標と番兵を入れてソートしておいて、lowerしてLとRになる座標を求める 「x_to_yとy_to_xの変数名で実装した方がいい」 ABC129-D ABC182-E(方向ごとにbfsした方が実装しやすい)

「自分の得点以上の人数がk/12以上か？」ではなくて 「自分の得点より高い(=自分の得点+1以上)の人数がk/12以上か？」 という判定じゃないと正しい答えが求められない。また、自分の変更前だったときの値で自分自身を数えないように注意「IOI(6)」

答えを二分探索

f(x)のxが決まっているということが解法に対して超重要である問題が結構多い、xが決まったからこそできることがたくさんある(ABC370-Fや平均の最大化)

平均の最大化は、答えを二分探索して「f(x)=平均(濃度)をx以上にできるか？」でxの値を決め打ちして、それで式を作って式変形をする。式変形の流れはどの問題も「xと選んだ要素で不等式を作る→分母を掛け算して右辺に移す→右辺を全て移項して右辺を0にする→各要素を独立に見れるようにそれぞれカッコでくくる(Σでも分解したままでも可)」ということをしている(分母の話を忘れがち) ABC236-E ABC34-D(濃度の最大化も、平均の最大化と同じ)

インデックスに対して答えを二分探索することもあれば、距離などの数字そのものに対して答えを二分探索をすることがある(どっちの実装が楽かは問題によって決まる) ABC364-D

「f(x)=距離xのやつがk個以上か？」ABC364-D

「f(x)=a,b,cのおいしさを組み合わせて作れるおいしさがx以上である組み合わせの通りがk通り以上か？」ABC123-D

組み合わせて作れる数字で大きい方から1,2,...k番目を出力したいとき、ちょうどk番目を求めたら、そのk番目の答えより大きい数字は全て答えに使用されるということになる ABC123-D

「敵一体にAダメージとそれ以外にBダメージ」を「敵一体にA-Bダメージ、全体にBダメージ」としてとらえて、「f(x)=x回で倒しきれるか？」 ABC63-D

「単調性がなくても答えを二分探索を使うことがある、条件を満たす答えが1つ求まればよくて、関数を線のグラフで表せるみたいな連続性(?)が成り立ってるならそのどこかに答えがあるとわかるので答えを二分探索ができる」ABC26-D

「k通り以下」とかで存在しない値が答えになるみたいなやつは、ooxxだったらxxooにしてみるとうまくいく「小さいのからk番目」→「アウト：x以下の数字がk個以下か？ooxx」「AC:x以下の数字がk個以上か？xxoo」リンク

(l,r)の区間系問題まとめ

区間の重なりについて

区間の重なりは、重なってるかを見るより重なってない方を見る方が楽な場合がある(数えあげと包除原理で出会っている) ABC355-D ABC361-B

重なってる条件は、「L1<=L2<=R1」OR「L1<=R2<=L1」OR「L2<=L1<=R2」OR「L2<=R1<=L2」のどれかを満たす(L1<L2とすれば2つだけ判定すればいい)

重なってない条件は「R1<L2」AND「R2<L1」をどっちも満たす

l,r決めて区間の中の何かを求める問題

総和を求めるとき、累積和の形に変形することで、問題の操作を新しい形で表現できる ABC378-E

LかRをどっちか固定する

だいたいlかrを固定して、もう片方の場所で条件を満たすやつとしてあり得るやつを高速に求める問題が多い

既に使用した累積和の値をもっておく ABC105-D

Lを固定したとき、Rとして可能な場所にooxxでもxxooでも単調性があるならrのぎりぎりを答えを二分探索すれば、RとしてOKな場所がわかる ABC98-D

円環で時計回りがどこまで回収するかを決め打ちして、反時計回り側は、時計回りが回収する領域と被らない範囲でのmaxを回収する(前処理で求めておく)

LかRを固定と思いきや、問題の条件自体の性質について考察する問題がある ABC43-D

rep(r,n)でrを一個ずつ見ていって、そのrを絶対に区間の右端にするという前提で、Lになりうるやつを求めると、全ての区間をカバーできる。全ての区間を見るDPと発想は全く同じ、必ず自分自身のa[r]を採用する区間だけを見て、そのときそのときの答えを求めていくというのが大事 ABC365-E

区間への一律の操作は「切れ目」を考える

問題の良い条件を満たしてる部分を「ある条件が連続して満たされている区間」みたいに認識しクエリなどの操作を「区間の切れ目に対して復活や削除」と言い換えることができたら切れ目が使える ABC341-E ABC364-F

尺取り法

Lを0,1,2...と小さい方から増やしていったときのRがここを含めて右にいて欲しい最小の場所を考える ABC247-E

Rを0,1,2...と小さい方から増やしていったときにLがここを含めて左にいて欲しいみたいなのを考える (上のR版が書きたかったので例題なし)

Lを小さい方から固定して一個ずつ右に動かしていくとして、その現時点でのLのときに、条件を満たすためにこの数字以上にRが来ていて欲しいというのを求める ABC260-E

LではなくRを小さい方から動かしていく場合もある、Rをずらしたことによって生まれる区間を見る JOI-白色光2

尺取り法で数えあげをするときは、rep(L,n)をして左端は絶対動かさないものとして、右のRは自由に拡張できるものとしてやると過不足なく数えあげができる ABC130-D

「E - メロンの出荷(7)」尺取り法で求めた内容はグラフ化できる

区間スケジューリング問題

区間スケジューリング問題は大きく分けて2種類に分けられる「(R,L)でソートする問題」と「(L,R)でソートする問題」がある。後者は印字系区間スケジューリング問題と呼んでいる

「Rが小さいやつから見ていったり処理したりがある」という種類がある、Rが小さい順にやっていけばうまくいけそうという考察をすることで正しいことが気づきやすい(各区間内のどこかを削除して欲しいというクエリで破壊回数の最小回数を求める問題に多い)実装するときはだいたい一番右の破壊された場所をもっておけばいい、すごい忘れやすい ABC105-D ABC230-D

「Lが早い順から見ていって、候補内でのRが早い順を見ていく」という印字系の区間スケジューリング問題がある ABC325-D　

二次元平面

[i]のy座標と比較したい頂点のy座標でd以上離れてるやつがあるかを調べたいとき、見ていい頂点の中で一番上のy座標と一番下のy座標を集計しておけばいい ABC215-F

平面走査

x軸を小さい方から大きい方に平面走査して、今見てる頂点から左にd以上離れてるやつを見たいとき、尺取り法をすればいい ABC215-F

[t1,t2]までの間に何かが起こったみたいなのは、t1のときに+1、t2のときに-1というクエリのように見ることで平面走査ができる JOI(typhoon)

決め打ち系

決め打ちするときは小さい順に決め打ちしていくことで値やdp配列が使い回せてそれの続きを書ける ABC216-F

一か所の値を決め打ちすると他のやつも求められると気づいたら、その値を答えを二分探索するんじゃなくてxとして文字で置いて一周してみる ABC133-D

ずらしたときの差分を求める系一覧

i=0のときの答えを求めて、iをずらしたときのその答えの差分を考える ABC318-E ABC348-E

円環系

長さnのやつをもう一個用意して考える=二周を用意することで一直線として見れる ABC347-C JOI-指輪 (Ring)

一か所の値を決め打ちすると他のやつも求められると気づいたら、その値を答えを二分探索するんじゃなくてxとして文字で置いて一周してみる ABC133-D

スタートから時計回りでどこまでか？と反時計回りでどこまでか？はすれ違いさえ起きなければそれぞれ独立に考えていい。スタートから時計回りでどこまで回収するか決めて、もう片方については時計回りがどこまで回収したかがわかってるからその領域に入らない範囲のmaxが貰えればいいので、あらかじめ前処理で求めておくことができる ABC95-D

「頂点1と頂点Nの種類を決め打ちする」頂点1だけ決め打ちすればいいとは限らないので注意(頂点1だけ決め打ちする場合もある、2頂点の関係の決め打ちは円環DPに多い)。例題だと左右の関係が大事だから頂点1にとっての左側を決め打ちすることに重要な意味があるという話ではある ABC55-D

円環を二周用意するやつ

二周用意して、rep(i,n)して、[i,i+n-1]までを見ると各場所をスタートとしたときのn個を見れる ABC347-C

二周の円環上で尺取り法する

何かの操作をしたときの値を求める系

操作後の状態を考えて、操作結果の値を一個ずつ求めるのではなく、各要素があり得る操作での答えへの寄与をまとめて求められないかを考える(各要素の寄与の合計を求めて、その合計が答えということ) ABC224-F ABC008-C
「答えとなる値の合計=期待値*全体の通り」という典型の式がある(上のやつの各要素の寄与の合計を期待値で求める) ABC224-F
スタートからゴールまでの操作ではなく、ゴールからスタートに行くと考えるとさかのぼることになって*2が/2になる ABC188-F

クエリ系

簡単めなクエリ問題の典型は三種類らしい https://blog.hamayanhamayan.com/entry/2020/03/22/235319
・複数種類の操作があるときは、一旦1種類だけでのクエリを考えて、それぞれの種類について結論を出してから組み合わせる ABC321-F

・答えに求めるために「どんなことができて欲しい」や「どんな情報が欲しい」かを考えて、それを実現するための方法を考える →データ構造や値の持ち方などに繋げたり、まとめれるものをまとめる ABC279-F

・複数種類のクエリに答えるときは一旦一種類だけのクエリだけを考えて、他のやつは完全に忘れてそれに答えるためにどうしたらいいかを考える

・絶対離れることがないならufで管理する

・答えがYesになると仮定したときの性質を考える ABC267-F

数列aとbのどっちかに加算するクエリがあったとして、加算されない方は「+0」としてとらえると遅延セグ木の関数が正しく作れる ABC357-F

クエリ逆読み

クエリの順に線を切るみたいなやつは逆から線を復元していくという実装をしていくと「ufの連結を切る」という作業が「連結する」となるので解法につながる ABC264-E

評価関数(?)みたいな式がある問題

・評価関数の式があるときは、実はあるペナルティ回数以降は見る必要がない、のような上界などを見積もる ABC315-F

・絶対値やminなどの式が来たら場合分けする、式の内側から先に対処していく ABC283-F
・(i,j)を使った式で、答えを求めるには二つ決める必要があるとき、場合分けして絶対値などを外して、式を整理してiだけの部分とjだけの部分に分ける ABC283-F

・割り算や掛け算が式にあるとき、調和級数が使える可能性がある ABC356-F

グラフ系

木やDAGなどの「○○の状態」に落とし込めたらこれができるのになーとなったらそれにできないかを考える
→同じ値のせいでDAGにできないのでufを使うとDAGになる。入力の辺から全域木を作り、残りの辺を一本ずつ加えると考えると閉路一周の値のポテンシャルの矛盾がわかる ABC335-E ABC280-F
木のグラフに変換する、木の作り方や掘り方は問題によって違う(trie木、永続データ構造、構文木、マージ過程の木) ABC353-E ABC350-F ABC314-F
辺が出自数1とかパスグラフのときに何か経路関係で答えを求めるとき、メモ化再帰で実装すると楽or正しい解法であることがちょこちょこある ABC89-D AB357-E

パスグラフ

パスグラフの条件は3つを全て満たせばOK 「辺がちょうどN−1本」「全ての頂点の次数が2以下(2頂点だけ次数が1である必要があるけど、辺がn-1本のとこも合わさって2以下であることさえわかればいい)」「グラフが連結」 ABC287-C

隣合う同士にしか辺が伸びてないグラフのとき、二頂点間の距離は累積和で求められる(メモ化再帰で求めた方が実装が楽 ABC89-Dのはまやんさんのやつ) ABC89-D

有向グラフ

functionalグラフはダブリングが使える ABC370-F

逆向きの辺にするといいことがある ABC373-D ABC320-D

グラフ系の公式

「閉路でないグラフのとき、連結成分数=頂点数-辺の数」ABC173-F

bfs

ただの頂点番号だけでなく、2^nの集合を頂点の情報に追加することができて、pairで情報をもってグラフを作ることができる ABC244-F

最短経路に使われない辺を消しても答えは変わらない。最短経路に使わるのはN-1本が最大(有向グラフでも同じ) ABC218-F

プレイヤーだけの座標をもってbfsする ABC339-D

スタートとゴールに駒があると考えてbfsする、スタートからだと解けないけど二つ以上コマを用意すると解ける問題がある ABC197-F

bfsしたいけど辺の数が多いなら辺の数を減らす方法を考える(kマス以下で自由に進めるけどTLEする系は、distの配列に今進んでる方向と既にその方向に何回進んでいるか(残り無料回数でも可能)の要素を追加することで1マスだけの遷移をすればよくなる、各場所からの辺の本数を4本にできる ABC170-F)

「同じ方向に進むなら0コスト」のときは「ここに来るために移動したときの移動方向」というように残りの無料移動回数などをdistの引数に入れるとACできる ABC246-E

連結成分ごとにbfsをするとき、bfsの関数の中で毎回distの配列を作成していると、辺が0本で連結成分がn個あるときに、サイズnのdist配列をn回作成することになってTLEするので注意 ABC87-D

方向を縦か横のどっちかに統一して、一方向の軸だけ見ることによって、光の覆う領域をbfsで見ることができる ABC182-E

ダイクストラ法

上位k個を列挙したいとき、一番大きい値からずらしていくことを考えると枝狩りダイクストラ法をすることでTLEせずにもとめることができる　ABC123-D

頂点そのものに対して重みがあるときは、頂点aとしたとき、頂点aから頂点a`への重みの辺があるとして考えると超頂点として考えてダイクストラ法が使える ABC362-D

有向グラフで各頂点からスタートに戻る最短距離を求めるとき、辺を逆にしてスタートからダイクストラ法をすればいい(各頂点からスタートに戻るということは、スタートから入力と逆向きの辺でその頂点に行くととらえることができる) ABC35-D

ワーシャルフロイド法

「dpの初期化のINF忘れ」と「dp[i][i]=0の初期化忘れ(0にしておくことで負閉路検出に使える、遷移後に負になってたら負閉路でINFだと判定できなくなってしまう)」に注意 ABC73-D

ぱっと見グラフとかに見えなくても、ある場所からある場所に経由して目的地に行くというのはグラフの最短経路になっていて、それぞれの頂点がそれぞれの目的地に行きたいならワーシャルフロイド法 ABC79-D(グラフがパスグラフみたいなときはワーシャルフロイド法だと計算量が過剰になってしまうメモ化再帰や累積和じゃないとACできない ABC89-D)

dpの中身をlonglongじゃなくて、pairにして持つことができる、(最短距離,価値の最大)みたいな感じ、最短距離はminだから価値の最大を求めるときは*-1しておくことに注意 ABC286-E

各辺がどの二頂点間のどの最短経路に使われないか？というのを判定したいとき、各辺を見ていって自分が必須かを求めていく。今見ている辺がi-jを結ぶ辺のとき、なんらかの経路でiとjを利用するとして、「i-jを直接結ぶ辺と、迂回路を使ってi→?→?→jと行く場合のどちらかが近いか？を判定すればいい。迂回路の方が近いなら今見てる辺は絶対に使用されない」(どんな辺もs=i,t=jとしてs-t間の経路を考えるとどんな辺もその辺が使われる可能性について考えることができる)
if (base[i][j] > (dp[i][k] + dp[k][j])を見ればいい(問題によって=が必要)ABC243-E ABC74-D ABC51-D　けんちょんさんの記事

ある頂点を除いてワーシャルフロイド法をしたいときはその頂点を使う辺の情報をDP配列に渡さなければいい ABC22-C

ユニオンファインド

クエリで渡された二頂点間の距離に矛盾がないかを調べるときは重み付きユニオンファインドを使えばいい　ABC87-D ABC328-F

グラフ内の閉路の個数をカウントしたいときはufを使えばいい ABC226-E

01bfs

「コスト0の行動」と「コスト1の行動」があったらだいたい01bfsでできる。01bfsに気づけずに実装しようとすると面倒なことになるので注意 ABC176-D ABC246-E

「同じ方向に進むなら0コスト」のときは「ここに来るために移動したときの移動方向」というのをdistの引数に入れるとACできる ABC246-E

超頂点

①辺の数がnC2などの多すぎてTLEのような場合に使われることが多い典型90-54
②最小全域木のようなグラフ系アルゴリズムに使えることもある ABC270-F
③頂点番号が未定の情報を保持するために使う → 行き先が未定の頂点を超頂点として用意して、行き先が決まったらその行き先を結ぶ辺のコストを0とする ABC257-F
④頂点そのものに重みがついてるとき、頂点1から頂点1`へのコストとして頂点の重みを変換する ABC362-D
⑤dsuとか入力で頂点として存在してはいない内容を超頂点として用意すると実装がとても楽になる ABC363-E

最小全域木

・a-bを結ぶではなく、「空港を決めると他の空港全てと行き来できる」のようなa-bではなく、「a」だけを決める内容のとき、空港同士を結ぶ「空」のような超頂点を作成すると、「a-空」の形にできる。なお、その超頂点を使わない場合があるので使う使わないを決める実装をする必要がある ABC270-F

木

各頂点を軸として、その頂点を含む最長の長さを考えたとき、どの頂点も、木そのものの直径となる両端の頂点を1つ以上必ず含んでいる。つまり適当に1つの頂点から一番遠いやつがその端の頂点で、そこからもう一回またdfsするともう片方の端っこが求まる。木の直径の概念は重み有りでも全く同じように使える(証明はむずいから理解してない、成り立つことが証明できるというのだけ理解している) ABC267-F ABC222-F ABC19-D

その頂点から移動する回数が決まっているとき、行き先をダブリングでO(logN)で求めることができる ABC267-F

根をずらしたときの差分を考える ABC348-E ABC220-F

頂点0から各頂点への距離の総和の求め方は、「行き先の総和(貰った値)+行き先の部分木サイズ*今回の辺のコスト(下の例だと全てコスト1)」で求められる ABC220-F

LCA

ただの木を根つき木としてとらえて、LCAの発想を用いて、二頂点間の距離を求める方法を使うことで考察の道具に使える。XORが累積和みたいに扱えるので、XOR的に使うこともできる(距離の偶奇を求めると考えると、根から最小共通祖先までの距離は*2して引き算するのでそこは必ず偶数になる) ABC126-D

木DP

メモ化再帰みたいに記録しなくても答えが求められるっぽい？ ABC259-F

なもりグラフ

・閉路上の各頂点を根として、他の閉路内の頂点を使わない部分木を考える ABC266-F

閉路

無向グラフの閉路は円環なので、円環DPができる ABC247-F

全ての頂点の次数2以上だと閉路が存在することが確定する ABC247-F

独立系

・縦横独立に求められることに気づく、独立に考えるのが苦手分野 ABC298-F

包除原理(4種類ある)

やってることは「問題文で求められてることと逆のものを求めて全体から引き算」と「ベン図の中身を求める」の二通り？なのかな？不明

①1個だけに対する「全体-求めたくないやつ」か「全体-いらないやつ」

XYX型が欲しいときに、「XXX型-X?X型」で求める ABC318-E

②2つ内容の被りを消す |A⋃B|=|A|+|B|-|A⋂B|

「とりあえず求めた全体の和-被り」これを数式にすると「|A⋃B|=|A|+|B|-|A⋂B|」ABC186-F

③約数包除原理

自分が初めて数えられるならカウントして、違うならカウントしない=小さい方から求めていって被りとか無視して自分でカウントできるやつを求めて、自分の値の約数で求めた通りを引き算する=自分の通りを求めたらエラトステネスの篩で配って引き算させる ABC304-F

約数包除原理をするときにユニークとする条件を決める上での条件は「カウントしちゃいけない値を自分から回収して引き算できる」または「自分専用の値を数えそうなやつにあらかじめ配っておいて引き算してもらう」のどっちかを満たす。エラトステネスの篩でも自分からアウトなのを配っていくときがある(自分が素数でその倍数のやつに配っていくみたいな) ABC361-F

④2^nで行う包除原理

ベン図の基準が「条件を満たす」のもあれば、「条件を満たさない」というのに対する包除原理もある、全体からベン図を引き算する ABC152-F ABC297-F

「bitを立てたやつを絶対に含む他はどうでもいい」ではなく「bitを立てたやつを絶対に含まない他はどうでもいい」というのを軸にしないとできない包除原理がある JOI(banner)

余事象(包除原理)を考える、通りの数え上げ系で一回落ち着いて求めたいやつと求めたくないやつを一旦整理して、求めたくないやつの方が求めやすいならこれが使える ABC355-D
→問題文を見たときに「○○を満たすのを求めてください」と来たら、逆に「○○を満たさないのを求める」という思考を持つのが一番覚えやすい対策になると思う

問題文で求められている答えの内容を「全体」として考えるのが大事で、全体=nC2ではないので内容ごとに全体の求め方は違う ABC261-F

「全体のコスト-払わなくていいお金」みたいな「数えたくない」じゃなくて「コストに含めなくていい」みたいな包除原理がある ABC261-F

現状求められるものを列挙してみると、そこから被りを求めて引くことで答えが求められる ABC186-F

問題の条件を分解して、その条件を全て満たしていなければならないなら、それぞれ満たさない場合を2^4で包除原理で試す ABC297-F

明らかに小さい制約

・弱点となるような小さい制約を基準に思いつく限りの案を全列挙して、そこから何か解法に繋がらないかを考える。その制約だからこそ考えられる配列や行動の内容をたくさん考える
→弱点となる制約をmとしたとき、2^mの集合、またはサイズmの配列をもって、v[i]=i以下のコストでの○○、みたいなのを考える ABC355^-F

m<=10みたいな2^10とか、2進数にできそうなやつはそれをdpの引数にすることが結構多い ABC237-F
LIS長さがちょうど3みたいな、異常に小さい長さのときは、その長さ一個ずつのときの要素を配列の引数にする ABC237-F

累積和系

・一点だけ更新、使わない、一点から行動を変える、みたいな「一点から○○」は両端それぞれをスタートとしたときの答えを求める ABC291-F ABC325-E
→その一点をrepして決めていく実装をする。またぐならそのrep(i,n)のiをまたぐL,Rを決める、更新系は、dp_L[i-1]とdp_R[i+1]の値を合成する

動的計画法(DP)

・愚直や意図的に欲しい数字を作り出すことができないのなら、全探索をするしかなくてdpをする ABC275-F
・今立ってる場所からの遷移することだけを考えたときに、過去の情報については自分の立ってる場所に関係することしか必要なくて他はいらない、一手だけの遷移を考えたときに必要な情報を考えると、2^2とかめちゃくちゃ軽い情報させあれば十分になる(明らかにdpなのにTLEなときは2^2とかでねじ込めないか考える) ABC264-F

よくあるグリッド系のdpで、右と下だけじゃなくて4近傍に遷移するdpがある。だいたい二次元グリッドの外側にもう一個引数があって回数系が多い ABC358-G
maxが小さい値からDPしていくことで、1つの答えを求めたらそのDP配列をそのまま利用して次の[i]の答えが求められる ABC216-F
modの値を決め打ちしてdpする ABC336-E ABC192-F
dpの引数に「i回操作したとき」はいらない場合がある、小さい値から順番に見ていけばいいのに操作回数を追加したせいでTLEする ABC184-D EDPC-J「sushi」
「直近で決めた内容だけ保持する」というDPがある、今までに決め終わった内容は問題の条件がセーフであるという前提でDPをしたとき、今回決めた内容がセーフかどうかを判定できればOKなのでその今回決めたことによってアウトになる可能性のある内容を引数としてもっておく。数字でもっても文字列でもっても計算量は変わらないので楽な方を使えばいい(vectorからmapだと多少遅くなる、メモ化再帰系だとTLEするけどこういう系なら大丈夫)(既に3^10=59049と4^4=256を保持する問題に遭遇している) ABC122-D ABC359-D
渡された内容から部分列を抜き出して好きに選べる→前から見ていって使う使わないでDPする ABC271-E
問題内容がDAGならDPができる(メモ化再帰が楽) ABC37-D
dpっぽい雰囲気だけどAcできないとき、なんらかの決め打ちなり改良をすることでよくあるdpに落とし込める ABC364-E

要注意点

あり得る値が大きいからmapでDPしたいときの注意点。公差や末項をDPの引数に入れるとき、あり得る通りがめちゃくちゃ多そうだと思っても、おちついて考えるとN通りやnC2通りで実は現実的な量の場合がある ABC362-D(反省を活かせた→ABC200-D)

最後に選んだ実際の数字じゃなくて、最後に選んだ数字のインデックスを持つことができる ABC362-D

個数をmとして2^mだからmapとかにもってもTLEでは？となるけど制約から|S|2の配列サイズを持てばOK(仮に全ての距離が1だとしたら、同じ方向に一生進んでいくと考えると負方向と正方向それぞれ限界まで持てばいいので、mapとかsetだとしても2mで良い) ABC82-D

dpのテクニック

部分集合を選んで、そこからさらに部分集合を選ぶときは、篩に落とされるタイミングから遷移を考える、この場合3通りの遷移としてdpが正しくできる ABC169-F

必須の「oxoxoxoxo」に対して、追加で必須でない「x」を文字の間に挿入すると考えてdpする ABC162-F

貰うDPをするときにdp[i]のiが重要な計算があるなら、遷移の式をiでまとめて、その内容をdp[i]に格納するという解法がある(つまり本来入れる予定のdp[i]から解法のために中身をちょっといじる) ABC353-G

dpの配列に入れたことのある特殊なやつ

部分集合のさらに部分集合は、「1回目で選ばれなかった」「1回目で選ばれて２回目で選ばれなかった」「どっちも選ばれた」という0,1,2の配列を持つことでできる(1回目で選ばれなかった時点で終わりなのでもう1通りはない) ABC169-F

2日連続というのを表すときに「i日目の選んだやつ」さえしっかりとした配列に入れていれば、「i-1日目に選んだやつ」は「i日目と同じか？の0,1」を配列に入れればよくなる JOIナイルドットコム

DPを高速化する

「今見てる魔法を何回でも使える」みたいなやつは、「各jから何回魔法を使うか？」で遷移したくなるけど、真左から値を貰う(配る) という遷移にすることで、それぞれ一回使う場合だけ見ればよくなる(個数制限なしナップサック問題と言うらしい) ABC153-E

配るDPなら配る元、貰うDPなら回収先、というのは「違う店を選ぶ遷移」のときどこを元として値を貰っても良くて、そして商品の金額は連続購入がなくて一意だから、その貰える先の値のminだけ貰えばいいといえる JOIナイルドットコム

ソート的なことをしてDPができるようにする

「優先順位」みたいなのを求める ABC366-F

「期限が早い順にソート」をすることで、前からみるとDPができる(ソートしないと、期限遠いを採用→期限近いを採用できないという現象が起きてWAになる) 典型90-11

愚直DPをとりあえずコードとしてちゃんと書いて見ると高速化できる部分に気づける可能性が高い ABC370-F

mapで通りもっておいて自分から貰いに来てもらう系の貰うDP(貰うDPであることが超重要) O(NlogN)かO(Nlog√N)

√nで平方分割して、√n以下のやつはmapか配列で倍数ごとに通りを保管してrep(i,n)のdp[i]自身に回収してもらう ABC335-F

貰うDPを考えたとき、回収しちゃいけないa[i]のスタートの数字はアウトで、逆に言えばそれ以外は全てOKなので「今見てるiより前まででの通りの総和-回収しちゃいけないa[i]から始まる通り」を貰うDPするとO(N*logN)になる ABC370-F

何かを決め打ちしてその中でDP

ぱっと見のDPだと配列がデカすぎるとか、問題内容的に正しく答えを求めさせてくれないときに、計算量に余裕があってもなくても何かDPをする前に決め打ちする対象を考えて、それによって元のDPにとって状況が変わるか？を考えると解法に気づきやすい

「最後にオーバーする用の一個を決め打ちしてそれ以外でセーフの範囲の収まる最大を求めるDP」 ABC364-D(決め打ちするやつを決めるとTLEする、ans<nなら適当に一個をオーバーするやつに選べばいいので残ってるやつのうち一つを実ははじめから決め打ちしてましたみたいな言い訳をすればいい)

ぱっと思いつくDPだと配列がデカすぎて壊れてしまう、なのでどうにかできないかと考えて、何かを決めうちしてもよさそうな制約なので決め打ちする対象を考えてみる ABC60-D

選ぶ個数を決め打ちしてDP(その決め打ちした個数をきちんと採用してるか？を確認しないといけないので引数忘れに注意) ABC192-F

添え字と中身を逆にするDP

dpの中身の要素がboolなら配列の一個をそれに置き換えることができる(一個ずつもってるとTLEするので、maxやminなど一つの値にまとめられる場合に限る) ABC364-D

一般的なDPを考えて、その引数の制約が10^9くらいだけど中身の値域が狭いならその引数と中身を逆にすればいい EDPC-E ABC32-D

桁DP

「n以下の数字で、決めた数字の中で、ある条件を満たしている個数」みたいなやつは、dpの定義を「dp[i][j][k]=i桁まで決めて、n未満が確定してるかをjに0,1、条件を満たしてる個数がk個であるときの通り」みたいにしないといけない、「dp[i][j]のみで今何個条件を満たしてるのが存在してるか？」みたいなやつは正しい漸化式が作れなくてWAになる ABC29-D ABC356-D

「k未満が確定しているか？」という部分だけのために桁DPすることがある(k以下の数字で1つ選べてそれによる答えのmaxを求めるというのは桁DPでできると覚えておいた方がいいかもしれない) ABC117-D

drep(i,60)みたいな入力をオーバーする桁を見ていたとしても問題なく動くコードの問題にしか出会ったことがないので、もし桁を余分な状態からさらに余分にすると答えがおかしくなる場合は実装が間違っている(XORならどっちも0^0=0になって無意味になるはずなのにコードミスや認識ミスで=1になるような思い違いをしていることがあった) ABC117-D

円環DP

円環DPをするときは頂点nと頂点1の関係を決め打ちする(だいたいnと1の辺か、nに関しての操作を予約しておくことが多い) ABCC229-F ABC247-F

LIS

セグ木版(座圧後の実際の数字を配列の引数にしたセグ木)とlower版(長さを引数にして実際の数字をvectorの中身に入れる)の二種類のLISがあって、セグ木版でしか解けない問題が存在するので注意 ABC360-G

bitDP

bitDPには二種類ある
① 巡回セールスマンみたいに一個ずつ立ってないbitを使っていくbitDP
② 箱ごとに決めていく系で、遷移のときは今回の箱に入れるやつを一気に決めるbitDP(2^nして2^nなので4^nになるけど、部分集合を列挙すると3^nになる) (一気にというのはrep(b,n2)みたいに列挙して使うやつを決めるということ)

dfsで今回の箱に入れるやつを決めていくときは、一気に箱に入れるやつを決めると考えると、②が使える ABC187-F

一番下のグリッドの状態だけを保持するDP

かなり上の行は絶対に条件がOKだからいらなくて、今決めようと思ってるi行目にとって必要な記録は、i-1行目の内容であり、i行目を決めた結果i-1行目の孤立の可能性があるのでi-2行目の情報も持つ。つまり配るDPならdp[i]=i行目とi-1行目のデータの通りを持ち。配る先のi+1行目の情報を決めて矛盾がなければ遷移する ABC283-E

上からDPしていくとして、(i,j)のマスを決めるのに必要なデータは、rep(i,h)rep(j,w)だとしたら下と右は未確定だからいいとして、左と上の二つになる。そのため各列ごとに現在確定している一番下のデータを保持する。3^Wが重いからTLEと思いきや、「mapを用いて遷移が可能な内容にしか存在させない」というのをすることで、2^(w-2)*3^2通りしか存在しなくなる ABC379-G

区間DP

「数えあげ系のDPで、区間DPじゃないけどL,Rを決める系のDPは、毎回自分をLとしたときの初期化の値をDP配列に+1して、各値をLとしたときの遷移を一回のDPの遷移でまとめてやってしまって良い」多項式で表したり直感的に考えても保証される ABC159-F

区間分割DP

dp[i]=iまでアイテムを見て、そこまではなんらかの分割がうまくいっているときの最小コスト(or通り)。みたいなDPをする、配るDPならiをスタートとしてどこまで分割するかを求める。貰うならiがケツになるような分割を見る JOI(A-オレンジの出荷)

番兵がケツだけに入っていて、i)であり、i=0がa[0]の左に仕切りがあるという珍しいやつ。貰うDPで区間分割DPを考えることによって、全体-貰ったいけないやつとして貰うDPを高速化できる ABC370-E(累積和を用いて式を変形をするのが前提)

全ての区間を見るDP(尺取り法的なやつがしたいけどできないときのDP)

あり得る区間を全てみるDP(セクションDP)

「セクションを0,1,2で分けて考える」というDPがある、下の内容よりもわかりやすい ABC365-E(セクションDP)

セクション内で選ばないというのも許される(区間の範囲選択のためにセクションを用意してるだけで合って、選ぶ選ばないみたいなのはセクション内で自由に遷移していい) ABC159-F

今求まっている値を区間の打ち切りとして毎回答えに加算しつつ、やっぱり続けるとして新しいRを現在の値に追加する(DPではないっぽい)

各場所から一番最後まで区間が存在していてそれを見ていくとして、rep(i,n)して各iの場所を終わりとしたときのことを考えると、その各repのときのdpの中身の値を貰ってあげることでその各区間の答えが見れているというDP(直前の区間の値を引き継ぐみたいなことができることが条件なのと、実装は絶対に区間の続きを採用するだけみたいなことに注意、採用しないのは遷移せずに値を回収して終わり) ABC164-D(dp[i][j]=i番目まで見て、スタートは不明だけどi番目で区間が終わるときのmodがjである通り)

とあるLから始まって、新しくRを追加するとしたら、今までの値に10して今回のa[R]を加算すればいい。今までの総和と個数が求まってるとしたら「総和10+a[R]*個数」で「Lは不明だけど今見てるRで終わるときの総和」が求められて、毎回そこで打ち切ったとして答えに加算していけばいい　ABC379-Eのmodあり版

数列をいくつかの連続部分列に分解するDP([0,i)で、dp[i]=iより左に仕切りでそこまで全て完成)

遷移するときにその一回の遷移で、区間を完成させることに注意(セクションDPのように今までの区間に新しく自分を追加する的なdp[i]+=dp[i-1]みたいなDPじゃなくて、一回の遷移で1つの区間を完全に完成させる) ABC370-E

期待値DP

前から期待値を配っていくDPみたいなのは不可能だと思った方がいい、絶対レベルで終わりから順に期待値を求めていかないと話がおかしくなる。「f(x)=状態xでスタートしたとき、ゴールまでの期待値」というのをメモ化再帰で求めて、貰うDPでやっていくのが絶対(解説放送で質問した) (ゲーム系でも各場所からスタートしてゴールに行くまでの結果的なやつをメモ化再帰して貰うDPなので同じ)

操作回数の期待値DP

絶対に貰うDPでなおかつメモ化再帰で実装しないとACできない今回の操作回数の+1を考えたとき、配るDPでは絶対に無理だと思った方がいい、貰うDPじゃないとうまく実装できない(後ろから貰っていくのが重要なのでdrepでもいける) ABC184-D EDPC-J「sushi」

半分全列挙

制約に20,40,80の数字が出て来たら半分全列挙の可能性が高い

n<=80で半分全列挙のさらに半分全列挙ができるのは、半分に分けたやつでお互いを見る必要がないときだけ解法になる可能性がある。しかしそれが解法ではない場合は普通にある (DP配列の要素数を落ち着いて考えれば半分全列挙の必要性がないし半分半分全列挙の実装がむずすぎる) ABC326-F ABC362-E

半分全列挙したときの全体の状態数が10^5や10^6ならセーフで、各dpの場所に10^6個があるわけではない ABC271-F

計算量からメタ読みする

O(N)を頑張ってするしかないとき

尺取り法 ABC377-E

サイズ10,サイズ26などを配列に追加してdpする

貪欲やシミュレーションを考える

とりあえず1つの答えを求めて、そこからの差分を求めていく ABC190-F ABC220-F ABC348-E

O(N * logN)が解法になりそうなとき

セグ木系

調和級数 ABC356-E

◇O(N * √N)が解法になりそうなとき

平方分割 ABC335-F

約数列挙やエラトステネスの篩、素因数分解

O(N^2)ができそうなとき

コマが二つあると考えてbfsする ABC197-F

区間DP

「左から何個取るか、右から何個取るか」や「左からどこまで見て、右からどこまで見るか」みたいな馬鹿正直な貪欲が解法になる場合がある(気づきにくい) ABC128-D

O(N^2)をO(N)にしたいとき

rep(i,n)でiが一個動いたときに、答えを求めるために集計してるやつの変化する量がその動いたやつ関連しか変化がなくて、値の変更部分だけ実装すればいいとなってO(N)になる ABC318-E

制約が16以下で、O(2^16)かO(3^16)ができそうなとき

O(3^16)未満になることからdfsができるという風に、絶対にここを超えないという計算量を見積もる。 ABC196-D

前から累積和と後ろから累積和を求めておくことで、O(N)を消せる ABC181-E

A[i]<=10^6

rrep(i,10^6)で、iを調和級数で見ていくことができるO(N*logN) ABC177-E ABC356-E

%M<=10^6

操作後の数字を毎回%Mしていくのであれば、グラフにしてみると閉路になってて、周期性の問題になっている ABC179-E

計算量をねじ込む系のテクニック

ダブリング ABC370-F

二分探索(lowerや答えを二分探索どっちも含む) 問題例色々 ABC370-D

これしたいけどやるとTLEになる系

2^(H*W)を全探索するとTLEになる

dpを考えて、今いる(i,j)から一手だけ遷移させて、その一手だけの遷移を考えると、dp配列に2^2とか2^4のように全体じゃなくて周辺の2のべき乗の情報さえあれば十分になる ABC264-F

文字列系

「部分文字列」は「連続部分列」と同じなので要注意、「部分列」だけ違うと覚えておけばいい ABC362-G

構築問題の辞書順の文字を作る系は前から小さい文字を入れていく貪欲がだいたい最強典型90-6,ABC009-C
?- 挿入でも抜き出すでも、同じ文字列を1回しかカウントしたくないときは部分列DPの考えを利用して、前から選んでいったやつ(?)の文字列だけをカウント+1とする ABC171-F
?- aaaaのように既に並びが決まってる文字列にbを2つ挿入するとき、b,bを入れる場所の通りは6C2通り O(26)を主軸とするdpがある ABC234-F

回文系

回文を作成するときは、左側を決めたら、右側での内容が絶対に定まる(片方決めたとき、反対側について探索する必要はなく、値をそのまま使うなりreverseすればいい)ABC363-D ABC363-E

カッコ列系

カッコ列は'('を+1、')'を-1として折れ線グラフにするのが超典型。そうしたときの正しいカッコ列になっているかの判定は「一度も高さが負になっていない」「最後の一番右の高さが=0」の二つが独立に成り立っているかを判定してどっちもOKならOK 一番右の高さに関してはただ単に各文字列の総和を求めるだけでいい条件に関してはお互いの条件がお互いを支え合っていると思うとわかりやすいと思う ABC167-F ABC312-D ABC064-D

カッコ列を成り立たせるために追加するとき、足りない分の'('は左端、')'は右端に追加していけばカッコ列が成り立ってなおかつ辞書順最小になる ABC064-D

Aho-Corasick O(Σ(|t|))

「1つの文字列に対して複数の文字列の一致確認に使える」文字列sに対して、複数の文字列tをキーワードやNGワードとしたときにアウトになってる回数を求めることができる。 ABC268-Ex

failurelinkを貼るたびにto→fromにNGワードのカウントを渡すようにすることで、なんか渡されたやつがさらに渡して...みたいな感じでいい感じに伝播されて純粋に今立ってる頂点がNGワードのカウントをもってるかどうかだけを見ればよくなるようになっている(一番最初の文字列を一個ずつ見ていく的なときにもその途中途中のやつがfailurelinkから値を貰えているからアウトだと判定が見れる) ABC268-Ex

Suffix Array O(N)

「1つの文字列に対して複数の文字列の一致確認に使える」文字列sの各場所をスタートとして、そこから一番最後までの文字列をソートする。そして1番目に早い文字列はどこからスタートしたか？2番目に早い文字列はどこからスタートしたか？...というのを求めてくれる。各場所からスタートした連続部分列だけを見るのが重要で、スタートでない中途半端な連続部分列がキーワードに一致しているかは見ない。「各場所をスタートとしたときにキーワードと一致してるか？」ということのためにこのアルゴリズムが使われるのが基本(?)なので、各suffixの文字列の中途半端なやつを見るのは正しくない

キーワードが何個一致してるか？を見たいとき、答えを二分探索すれば[l,r)で求めることができる。f(s)=自分自身も含めて自分より前に、文字列sより辞書順で小さいやつが存在しているか？を行う。rを求めるときは、小文字のzより後ろにある「~」を入れることで、rの場所を求めることができる。「t+'~'」が固定された文字列でそれが存在しているかを求めたくて、元々のtが取れた場所よりも前というか元々trueだった場所には、「~」を追加した文字列が絶対にそこより前に存在しないから絶対falseになっていい感じになっている ABC362-G ABC150-F(解いてすらいない)

Z-algorithm O(N)

「文字列sを使って、先頭からの文字列と、rep(i,n)したiからスタートした文字列がそれぞれ何文字まで一致しているかを求める」 ABC141-E

数学系の典型と公式

「0」と「1」は特別扱いする問題に要注意、場合分けミスで沼る実装にn連敗してる。1桁のときだけ0が特別な対応をする場合などに注意。 ABC363-D

「O(12!)」「O(2^29)」「O(3^18)」「O(4^14)」「O(5^12)」までの計算量ならぎりぎりTLEしない(定数倍やlogなどが少しでも入ったら、左の数字だとTLEする、だいたいO(10!)かO(2^16)かO(2^20)くらいが多い)

実際の数字ではなく文字の式で表して式変形や公式を当てはめる ABC254-F

問題文の式からその変数が取りえる数字の範囲を求める ABC300-D

筆算をしたり値でくくると公式が使えると気づきやすいイメージがある ABC357-D

d<=min(a,b)かを調べるとき、中身がどっちもd以上ならOK ABC215-F

スタートの値がsで、そこからkという一定の値が一回ずつ増えていって、その値をMにしたいとき、「s%k=M%k」が成り立っていれば値を作成することができる。一定数増えるときはmodの発想を持つ ABC192-F

偶数か奇数かみたいなのを利用する問題がそれなりに多い

「5個選んで合計が合成数か？→各値の%5が=1になるやつを5個集めればいい」(mの倍数になるように数字を選ぶ→%m=1を集める、として覚えれば良さそう、桁DPと似ている)ABC96-D

問題文の式を式変形していく系

小数が式にあるならどうにかして排除する、小数を消すことによってそこで初めて偶数とか奇数とかの話ができるようになるので超重要 ABC150-D

値を展開しないといけない場合もあるし、くくったまま使わないといけない場合がある(どっちのパターンも試さないともう片方の方が正しい解法に繋がっている場合がある) ABC150-D

問題文が数式じゃなくて、文字で「絶対値」とか「和」とかを表してるのは結構怪しい、式変形が使える可能性が高い ABC166-E

|x-y|のように絶対値が来たら、x>y、x=y、x<yと3通り決め打ちして場合わけをする ABC166-E(被り無しでカウントするので一通りだけ考える)

問題文の内容をΣみたいにとらえると、「Σmax-Σmin」と見れて、maxとminはそれぞれ別々で総和を求めて最後に合わせればいいと気づける ABC151-E

一つの式に入力で渡されておらず、自分で数字を決めていくみたいな、真の意味で変数のやつが1個になると考えやすいので、式をいじくることで真の変数をそれぞれ独立に考えられるようにする ABC366-E

操作を式に表して性質を見つける

2個セットでXORを取ると考えたとき、[0]と[1]を使うと「(a[0]^a[2]^a[3]...a[n-1])^(a[1]^a[2]^a[3]...a[n-1])=a[0]^a[1]」となり、選んだインデックスの答えとなる数字二つをXORしたやつが求まる、それを全体にやっていくと全ての数字でXORした値がわかる ABC171-E

それぞれの式を筆算みたいに並べると何かがわかるかもしれない、だいたい筆算にして下方向になんらかの演算をする(筆算の式と同じ演算or足し算になることが多い？) ABC171-E(けんちょんさんの記事がわかりやすい)

パスカルの三角形(nCr系)

パスカルの三角形の性質として、斜めみたいな線を1をスタートとしてまっすぐ進んでいってある場所で左右逆の下のとこを見ると、そこまでの総和の値が書かれている、これを利用すると「パスカルの三角形の長方形領域の総和」をO(1)で求められる ABC154-F

パスカルの三角形の各場所は、nCrの値と対応している https://examist.jp/mathematics/expression-proof/pascal-triangle/

Σ(シグマ)関係

Σの中に演算があるとき分解できる Σ(a-b)=Σ(a)-Σ(b) ABC173-F

総和が答えで、Σで決めたやつを一個ずつ求めなくてもいいとき、そのΣの答えを別の見方で求められる(各辺が使われる回数を考える ABC173-F)

Σ(|x-x[i]|+|y-y[i]|)は、Σ|x-x[i]|+Σ|y-y[i]|に変換できる、Σの和を分解するのは、一項ずつできるというイメージが強いが、塊ごとに分解しても大丈夫 ABC366-E

絶対値 |x|

式の中にある絶対値を場合分けする(問題例どれだかわからん)

絶対値の形をソートしたり、i>jであると仮定することで、絶対値を外す

絶対値自体の分解せずに、そのままの形で考察を進める(Σの和の分解はする) ABC366-E

等比数列

10進数の数字は筆算のように各桁ごとの足し算として見れる、値でくくったりすると気づきやすいイメージ ABC357-D(本番でわからなかった())

「合計=期待値*全体の通りの数」という公式のようなものがある ABC224-F

階差数列

「A - とてもたのしい家庭菜園(7)」区間に対しての操作は階差数列で考えて、階差数列における操作はどういう操作になるかを考える

「A - フェーン現象(6)」サンプルを書いて考察してみると、[l,r]は階差数列における[l-1]と[r]にしか温度の変化を与えないので、答えの差分の変化だけ求めてあげればいい

確率

一番左のところだけ求めておいて、他のやつは(1-dp[i])/(n-1)で求めることができる。難しいところは求めずに(1-確率)を利用する ABC360-E

複数から複数への遷移は難しいので何か別の方法がないかを考えた方がいい

遷移の確率が1パターンじゃなくて複数パターンあるとき、遷移してはいけないやつの確率を求めて、1から引き算することで楽に遷移ができる。 ABC360-E

期待値

前から期待値を配っていくDPみたいなのは不可能だと思った方がいい、絶対レベルで終わりから順に期待値を求めていかないと話がおかしくなる。「f(x)=状態xでスタートしたとき、ゴールまでの期待値」というのをメモ化再帰で求めて、貰うDPでやっていくのが絶対(解説放送で質問した)(ゲーム系でも各場所からスタートしてゴールに行くまでの結果的なやつをメモ化再帰して貰うDPなので同じ)

期待値DPのやっていることの本質は「絶対的に求まっている期待値を利用して、その期待値の値を貰うDPをしている」。また、スコアなどの期待値において、行った操作回数などが気になるが、少しでも見ようとした時点で、無限に続く操作の可能性が絶対存在するから、操作回数が期待値でない限り、期待値DPで操作回数を見ることはない。じゃあ期待値を求められるのか？となるが、「絶対的に求まっている期待値」というのを貰うことをりようしていくことで求められる。0枚のレアは確定で0枚のパックなのだから、そしたら1枚は0枚の期待値を利用して求められて、そしたら2枚は0,1枚の期待値がわかってるのだから求められて...となる

「値の合計=期待値*全体の通り」という公式のようなものがある ABC224-F

今見てる要素での確率を求めるとき、どう選ぼうと欲しい条件を満たすみたいなところの確率は*1として考えるとわかりやすい ABC224-F ABC008-F

「欲しいやつが出るまで操作を行うときの期待値は、欲しいやつが出る確率の逆数となる」有効なやつの個数をそれぞれ見ないといけないのでだいたいfor文が必要なことに注意(ある状態から次の状態に行くまでの回数を求めて、その状態からさらに次の状態にいくまでの回数...なので各期待値の和を求めていくことになる、積じゃないので注意、回数の総和だと思えばわかりやすい) ABC194-D ABC078-C(この二つは違う期待値の定理的な話だと思ってたけどどっちも同じやつだった、ガチャコンプも欲しい結果になるまで操作を行い続けるのも、どっちも同じといえる)

★操作回数やパック枚数が期待値のとき、期待値DPのresは、res=1になることに注意。説明としては、今立っている期待値を求めるには、今まで求めた期待値を求める必要があって、その期待値を求めるにはどうやっても一回操作なりなんなりして過去？というか貰う先の状態に移動する必要がある。だからその必須な操作の一回を加算している。伝わりにくいのであれば、100%の確率で操作回数が+1される。と思うと良い(毎回+1しないといけないのかと思ってしまうが納得のいく説明がわからない) ABC382-E

gcd

「gcd(gcd(a,b),c)=gcd(a,b,c)」gcdの中にgcdがあるときは、内側のやつを外して、gcd(a,b,c)と表せる、逆も成り立つ→解法というよりgcdの式変形の考察をするうえで使える ABC254-F

「gcd(x,y)のとき、任意の整数をaとして、gcd(x,y)=gcd(x,y-a*x)が成り立つ」(片方の倍数の数字をもう片方で足し引きしても答えは同じ) ABC254-F

2進数系

「2」という数字が出てきた時点で、二進数上で考えると明らかに考察がしやすくなる ABC384-E

桁ごとに考えて、桁ごとに答えを求める(その桁が答えに与える内容を桁ごとに独立に求める) ABC147-D

2進数に対して桁DPする問題もある(これは桁ごとに考えるという発想を問題設定に合わせてDPにしただけ) ABC356-D

XOR系の典型

XORを使う問題の典型は「桁DP」「桁ごとに見る」「XORの演算の性質を頑張って見つける」「累積和のXOR版」の4種類なのかなと思われる。どっかのE問題で見た、各桁ごとに{1,0}のそれぞれの場合でスタートしたときの結果を保持しつつ毎回それをぶつけるみたいな問題もある

a~bの総和と同じように、a~bのXORの答えは、「0からbまでのXOR」^「0からa-1までのXOR」が成り立つ ABC121-D ABC126-D

「nが偶数のとき、n^(n+1)=1」が成り立つ。偶数であることから+1すると一番右のbitが1になるので一番右以外が全て相殺されて0になると考えるとわかりやすい ABC121-D

桁ごとに考えて、桁ごとに答えを求める(その桁が答えに与える内容を桁ごとに独立に求める) ABC147-D ABC365-E

XORの結果が0になるのは、「偶奇が同じ」ときで、二頂点間の距離の偶奇を求めるときにこの発想を利用できる問題がある(LCAの二頂点間の距離を求めるやつと同じように、削除したい経路で相殺みたいなのができる) ABC126-D

偶数回同じ数字をXORすると相殺できる、逆に奇数回同じ数字をXORするとその数字は一回分残るつまり値をa、回数をcntとすると「a*(cnt%2)」と表せる。 ABC171-E (XORしたときに2進数の各桁が答えに加算されるか？も各桁の1が立ってる個数の偶奇から求められる ABC365-E)

XORの演算関連

10進数の2つの数字の足し算をXORで表すとき、2進数の各桁をx,yとして「x+y = (2 * xANDy)+(x^y)」となる。2*なのは1AND1=1のときに繰り上がりを表すため(DかE問題のどっかで数式にこれを使って変形する問題を見たんだけど忘れた)

10進数の2つの数字の足し算とXORの結果を比べたとき、「XOR算の結果<=足し算の結果」が成り立つ。理由はXORではどこかの桁で1と1が来たときにその繰り上がりができず、足し算では繰り上がりができるため。一度でも「XOR算の結果<足し算の結果」でイコールが崩れてしまったら、どのような数字を使ってもイコールの関係を戻すことはできない(どんな数字を入れても、XOR側で消えてしまった1と1が取り戻せることは不可能だから(?)。なのでそれが起きないように数字を選ぶ必要がある) ABC98-D

「累積XORのとき、rui[i]と対応している数字の今見ている桁が1ならば、rui[i-1]^rui[i]=1に必ずなる。rui[i]=rui[i-1]^1なのだから{0,1}か{1,0}の並びしかありえない。つまり幅1が存在する(今見ている桁が0ならばrui[i]=rui[i-1]^0だから、rui[i]=rui[i-1]で、{0,0}か{1,1}しかない) ABC365-E

算数的な思考がメインの問題

算数系っぽいなと思ったら思いつく限りの場合分けを全て列挙する「n%k=0とn%k!=0」や「k=1のとき、k=2のとき、k=3のとき...」などしらみつぶしになってでも解法を追求する ABC161-F ABC166-F

割り算が基準になることが多いイメージ「/」と「%」でなんかやっていく系が多いと思う、場合分けなり答えを求めていく上での答えの求め方とか

modの典型

「n%k」と「(n-k)%k」は同じ値になる、足し算と引き算は何回行ったとしても絶対に元のmodと一致する。しかしかけ算と割り算は一致しなくなる ABC161-F

「n%k=1」を移項して「(n-1)%k=0」という式に変えることができる最近初めて知った... ABC161-F

10^1000000みたいなデカい数字のmodを求めるとき、一個ずつ桁を見ていって、*10して今回のを足して%modをしていけばいい(桁DPにも使える)、周期性の閉路に入るまでを引き算してmodを取ってから足し算するというのもいい感じにやればできる(多倍長を使った方が楽だけど) ABC30-D

幾何

内積は「二つの線分の角度が90°か、90°未満か、90°より大きいか」がわかる

外積は「三角形または平行四辺形の面積」と「三頂点が時計周りか反時計回りか、一直線か」を求めることができる

複素数の概念(?)を使うことで、線分の長さはそのままで角度だけ変えることができる(円の中心から生えてる辺の角度を変更したときの座標が、円の中心から軸ごとに離れてる距離がわかる) ABC197-D

進数の問題のように、各軸ごとに考えるという発想が幾何にある。「l,rを各軸ごとに決め打ちする」「各軸ごとに重なってるか判定する」 ABC005-D ABC361-B

図形を切ったとき、「切った回数+1個の図形になる」、切った回数を求めるために、「二つの線分の交差判定をする方法」がある ABC016-D

長方形

長方形の形を決めるときは、「x_l,x_r,y_l,y_r」の長方形の各軸ごとにそれぞれ端の頂点の座標が決まればいい、それぞれの候補をsetとかにもって全探索すればいい(左上と右下に端となる頂点があっても長方形の形さえわかればいいから座標の軸をそれぞれ分解してしまっていい、基準となる頂点座標じゃなくて、長方形を構成する4辺がそれぞれどの座標にあるか？というのが欲しい)二頂点決めればOKではないことに注意(三角形みたいな配置の頂点を包含するときに二頂点だけ見ると長方形を見れない) ABC75-D

長方形の形が既に決まっているとき、入れたい頂点を全て含む最小の長方形がその決められてる形か？というのは4方向でそれぞれ端っこにある頂点が、その長方形の四隅の座標とぴったり重なってるみたいな感じであればいい ABC297-F

数えあげ

包除原理を使う問題がそれなりにある、「全体-満たさない通り」 (例題は忘れた())

最小構成を先に作ってしまって、残ったボールをどう追加するかの配置を仕切りのnCrで求めていく。その両端に対して余分に入れるか入れないかの4通りに場合分けしても正しい答えが求められる。最小構成は考察の道具としても解法としても使える ABC132-D

nCr

n個あるやつをkグループに分けたくて、各グループに一個以上入っていて欲しいときは、先にn=n-kとして、各グループに一個ずつ入れておく ABC132-D

周期性

「%k」が来たら、「n=p*r+q」みたいなのを考えて、その完全な塊を一個ずつ見たときに周期性がないかを考える、そしてその一個分の塊の答えを求められないかを考える。それができたら余りの方もだいたい求められる

「k回移動したらどこの頂点にいるか？」はダブリングをすればできる、なお移動コスト的なのも求めることができる(cost[i][j]=頂点jからスタートして2^i移動したときに得られるスコア) ABC179-E ABC167-D

移動先が1,2,...nの順列だからといって、閉路のサイズがどのケースでもちょうどサイズnになるわけではないので要注意あくまで並び替えただけで閉路のサイズはバラバラ ABC175-D

始点と終点を決めて、その移動を確定したとしたときに、その内部の移動で何回閉路を完全に回れるか？という解法が存在する ABC175-D

移動回数が「1以上k以下」のように好きに決められるときに、閉路をまとめて計算してしまうと、実は閉路を一周する最後の一歩を進まずに、そのぎりぎりのときが最大のスコアとなるときがあるので、閉路スキップできる回数は全てスキップせずに、最後の完全な一周を残しておいて、それとn%kの余りの回数をシミュレーションしないといけない場合がある ABC175-D

ぱっと見で周期性に見えなくても、「%M<=10^6」 という時点で周期性の可能性が高い ABC179-E

コマみたいな周期性じゃなくて、実際の数字を頂点として周期性を使う問題があるので要注意 ABC179-E

ダブリングだと実装できない周期性の問題が存在する。各サイクルごとに答えを求めていい(全体の周期をLCMで求める必要はない ABC377-E

周期性の実装

スタートの頂点に戻ってくるまでの閉路のサイズとかその閉路一周の総和を求めたいときは、while(true)で書いて、その内部の一番下に、if(ps==i)breakと書くと実装がすごい楽になる https://atcoder.jp/contests/abc175/submissions/55899335

鳩ノ巣原理

%200みたいな異常にmodの値が小さいやつがきたら鳩ノ巣原理が使える。%200の場合、2^8=256であることから前から8個取って2^8を見れば答えが必ず見つかる ABC200-D

二次元配列で既に存在しているやつを用意する配列を用意したとき、必ず二次元配列のサイズ+1以下で答えが求まるという鳩ノ巣原理。鳩ノ巣原理を利用して最大の被り無し回数がT*Tであることから配列を受け皿とする ABC260-F

「過半数以上が同じアルファベッド」ということについて考察すると、「必ず長さ2以上の部分文字列が同じアルファベッドである」という風に考察できて、どれだけ長さが大きいアンバランスな文字列だったとしても、その長さ2以上の隣り合うやつを部分文字列として含んでいるとして条件を言い換えられる(なお長さ2だけだと不足していて、x?xという長さ3のやつも見ないといけない)ABC43-D

答えが見つかったら探索を打ち切ることによって計算量を軽くする(鳩ノ巣原理に含まれるのかは不明だけど似てる内容ではある)

「ダメと判定される回数がM回以下」であることを利用して、O(M^2)で座標を全て見ていくんだけど、セーフと言われた時点で探索を打ち切ることでO(M)になってACできる ABC176-E

素因数分解

「ある数字nを素因数分解したときの結果を素数をp、乗数をeとして、 p1^e1 * p2^e2 * p3^e3... と表せるとき、この数字の約数の個数は (e1+1)(e2+1)(e3+1)...と表せる。選ばないのを表すための+1で全て選ばないときは1が約数であることを表す、n=1のときe1=0、e2=0...となる」という知識自体を利用する問題がある(e1+e2+e3...ek=75となるように素因数を用意する) ABC114-D

ルジャンドルの定理 O(logN)

「N!に各素数が何個入っているかを求めることができる」という定理?道具？ ABC114-D ABC280-D

N!という前提であれば、任意の素数の肩が1以上であるやつを一個ずつ降ろすことができる。2^iがあったして一個落としたいなら2を使わないとすればよくて、2個落としたいなら4を使わないとすればいい...的な話で、良い説明ができないけどなんかいい感じに好きに降ろせる。約数としての数字の話 ABC114-D

「N!!に素因数pが何個含まれてるか？」というのも求めることができる。 N!とN!!の違いは数字が一個飛ばしになっててそれだとn!みたいに見れないことが原因なんだけど、あらかじめn/=2をしておけば、n!の形に帰着できる。欲しい素因数が2の場合はその/2をした回数が答えに加算しないといけなくて、2じゃないなら素因数2を一個消しただけで欲しい素因数に影響はないから気にしなくていいということに注意 ABC148-E

約数列挙 O(√N)

「xを、xの約数の数字に変更する」という操作は、xの素因数のボールから任意のボールを捨てるといえる ABC368-F

調和級数

「n/1+n/2+n/3+n/4...n/n=logN」になるという定理?のような数式、logNになることを利用して、計算量がTLEしないとい見積もる問題がD,E,Fで結構見かける(ありすぎて書ききれないレベル) ABC280-D ABC356-D

「素数を列挙→素数を一個ずつ見て調和級数」という解法がある。A[i]<=10^7くらいなら可能(素数列挙的に10^8は微妙、atcoderだとPythonだと無理そうだから10^7か10^6が最大のはず) ABC177-E

mex

「数字の個数がN個だったとき、mexとなる数字は必ず0~Nのどれか」という当然のような典型がある(Nより大きい数字はmex候補から無視していいという話が重要) ABC330-E

mexとなる候補をsetとかで集計しておく ABC194-E ABC330-E

「今見てる値がmexになりえる区間が存在するか？」というのを小さい数字から試していくという方法がある(各数字分布を集計して、その各数字の距離が、区間の幅mより離れてるならその数字がmexになりえる) ABC194-E

上位k個を保持する、上位k個を全列挙する系まとめ

最小の値をk個保持する(内容が新しく追加されていく)

multisetやpqなどで、上位k個を保持しておく、毎回突っ込まれるのは1個だけなんだから、そのデータ構造に追加してしまって、サイズがk個をはみ出してるならそのtopを捨てればいい(保持できるkの値が減っていっても問題ない) ABC249-F ABC306-E

3つの配列の数字を組み合わせて上位k個を全て出力する(O(K)はTLEしないのを前提)

2つの山での数字の組み合わせを作ってそこでの順位を求めたとき、残り1個の山の数字を組み合わせたとしても、自分の順位はそのままか順位が落ちるかのどちらかしかありえないので、2つの山での上位k個から落ちたやつは全て捨てて良い(自分がk+1位だったとして残り1つの山から一番大きい数字を選んでのし上がろうとしても、自分より上のやつらも同じく一番大きい数字を選ぶので平行線になってしまう)(典型的な内容として表すなら「入賞があり得ないやつは削除する」という感じだと思う) ABC123-D

絶対的な一位は求められるとき、二位候補はそこで使用した内容を一段階小さくしたやつであり、二位として確定したやつから三位候補になるのを考えると、さっき選ばれなかったやつor二位から一段階下げたやつのどちらかに含まれていて、そういうのを考えるとダイクストラ法で求められると考えることができる(枝狩りダイクストラ法と呼ぶのがよいかもしれない) ABC123-D

グリッド系

水たまり系でない問題にdfsすると、バックトラックだろうとなんだろうと絶対TLEする、連結成分を求めるならできるが、経路を一旦消して新しい道を経路を求めるのは絶対に指数時間かかる(4^(H*W)) 数え上げお姉さんと全く同じことをdfsでしていると思えば覚えやすい、道順を変えて新しい道を進もうとした時点でアウト ABC358-F
パリティを考えるときは、数字の偶奇を考えるだけでなくグリッド自体に白と黒、または赤と青で色を塗らないとパリティだと気づけずに大事故が起きてしまう ABC358-F

セグ木系

サイズn+1みたいな保険で+1するのはやめた方がいい、r-1のし忘れなどで大事故が起きる ABC223-F

通常のセグ木

遅延セグ木

-遅延セグ木の関数の実装で、元からある関数と新しい関数の二つで、その型と型の中身の値の意味は全て完全に同じでなければならない。関数を集計しておくみたいなものは存在しない、あくまで複数クエリをひとまとめにしても正しい答えが求められるから遅延セグ木が使えるだけ ABC357-F

セグ木系に乗せる内容一覧

区間の両端の情報を載せる ABC322-F

区間の長さを乗せる(よく出る) ABC357-F

存在しているかの0,1や、存在している個数 ABC351のEとF

残ってるやつの個数を持つ ABC223-F

元からある値をx,クエリの値をa,bとして、ax+bの式で表してa,bを関数に持つ ABC332-F

「>」のような区間に存在してほしくないやつがあるときは、嫌なやつを1として変換して区間の総和が0ならOK　ABC285-F

アルファベッド26文字の情報をセグ木にもつとき、1つのセグ木でarrayでもつとopなどの計算量がやばいので、サイズ26のvectorにセグ木を26個入れるといい(そうしないとくっそ重くなる) ABC285-F

表と裏の内容をセグ木に持つ、フリップが来たらその二つをswapするだけでACできる ABC322-F

数列aとbのどっちかに加算するクエリを関数で投げるとして、applyするときの中身は加算しない方を「+0」として考える ABC357-F

折れ線グラフとして考えて、その一番右の値と、minの値をもっておく(ちゃんと理解できていない) ABC223-F

種類数を求めるために、部分列DPみたいな自分は前に同じのがあるから数えないみたいなのを矢印としてその座標を二次元座標として二次元プロッドして平面走査 ABC174-F

h,wが自分より低い箱があるか？を求めるとき、seg[j]=x軸がjであるやつの縦幅のmin。をもたせるようにすると今見てるのをh,wとしたら、[0,w)をセグ木から貰ってその値が自分より低いならOK ABC309-F

(スコア,番号)のPairでセグ木をもってmaxを求めると、そのmaxのスコアを貰ったのがどこの番号だったか？を求めることができる、経路復元に使える、自分自身の番号を書き込むことに注意、prevが欲しいなら回収して今の数字とそのprodの番号を見る。 ABC369-F

inplaceでなおかつまとめて値を貰うDPしたいからセグ木に乗せて、DP本来の値を入れたいけど、dp[i]のiを使ったスコアの計算があるから、計算式でiの内容をまとめてその内容をdpに入れる ABC353-G

完全マッチング系

ホールの定理を完全マッチングが可能か？の判定に使える、Noじゃないなら必ず完全マッチングができる？ ABC174-F

ゲーム系

前から期待値を配っていくDPみたいなのは不可能だと思った方がいい、絶対レベルで終わりから順に期待値を求めていかないと話がおかしくなる。「f(x)=状態xでスタートしたとき、ゴールまでの期待値」というのをメモ化再帰で求めて、貰うDPでやっていくのが絶対(解説放送で質問した)(ゲーム系でも各場所からスタートしてゴールに行くまでの結果的なやつをメモ化再帰して貰うDPなので同じ)

★メモ化再帰するときは、配列でできるなら配列の方が良い、mapで既に掘ったかを確認するとき、countしてtrueならその値を返すので、log^2の計算量がかかるのでTLEする ABC201-D

「最適に動いたときにどっちが勝つか？」系はゴールからさかのぼっていくのが解法として強い(後退解析)。bool値で勝敗を表せる場合、終わりから見ていったときにもし自分が勝てる未来があるなら、どう考えてもそれを選ばない理由はないので勝てるなら勝ちの道に進んでいき無理なら負け...というメモ化再帰を掘っていく ABC349-E ABC354-E ABC201-D EDPC-K

DPの実装をするとき、無駄な情報を入れようとしてTLEすることに注意、実は「残りの山札とどっちのターンか？」の二つさえわかってればプレイヤーの具体的な数字がいらないみたいな問題がある ABC78-D(片方のプレイヤーは引数の残り枚数から分かる、もう片方はこれから決める)

ミニマックス法

「ミニマックス法」は片方のターンでは得点の差を最大化して、片方のターンでは得点の差を最小化させる。実装が知ってないとむずいけど自分のターンでは「自分-相手」の差を最大化すればどっちのターンだろうとうまくできる ABC201-D EDPC-L

問題によっては毎回貰った値を*-1することで毎ターン最大を求めることができるものがあるけど、それが絶対にできない問題も存在する ABC78-D ABC25-C

grundy数(Nim)

grundy数というのは「掘った先の操作回数でmexを求めた的な数字」だと思ってたけど、ゲームの完全な終わりみたいなのを0として設定し、その状態で各数字から再帰関数で掘ってmexを求めているという感じっぽい？だから操作回数とかじゃなくてなんかよくわからん数字のmexという感じなのかな？ ABC368-Fでの疑問

仕切りとして考える

各クエリが確保している領域や、誰も確保してない領域をそれぞれ仕切りで分けられていると考えて、辺を選ぶ操作をその仕切りを1つ消すと考えることができる ABC364-F

正しい並びとして繋がっていない区間が仕切りで分かれているとしたとき、反転させるという行動はL,Rについてそれぞれに対して「仕切りがあるなら消す、仕切りがないなら仕切りを追加する」と考えることができる ABC341-E

存在している数字を区間としてとらえると、mexとなる数字は区間を繋げていない場所の数字、つまり区間同士の仕切りといえて、その仕切りのminの場所がmexとなる(mexの候補をもってその最小が答えと気づくための解法の道具という感じがメイン) ABC194-E

発想系(数学の発想を含む)の問題

どの問題もグリッドのサイズとか、数列の長さを固定してしまっていい(最大サイズにすることが多い) ABC92-D ABC68-D

白と黒を上下でそれぞれ分けてベースとして領域を用意してあげて、自分の必要な分だけ相手の領域を隣合わないように一個ずつ借りて格納していく(隣合わない=ベースとなっている色は十字路を保ち続けるということで連結成分が必ず保ち続けられる) ABC92-D

要素一個ずつに操作したらどうなるかを考える ABC68-D

n%k回の操作をベースとして用意しておいて、そこにn/k周できるように必要な量を加算していく ABC68-D

同じ領域？の数字を一律にしないといけないことがある ABC68-D

簡単な問題を考える一覧

「入力の値は正と負もどっちもありえるとき、正のみと負のみのそれぞれの場合について考えてみる」 ABC86-D(正のみと負のみの答えの求め方がわかったとき、入力の数列の符号を統一できるように操作すればいい)

分類できない細かい知識

「上下左右の4方向に移動できて、今向いてる方向から90°回転、つまり今向いてる方向の右か左のどっちかに向くことができる」みたいな問題は、今が上下のどちらかを向いていて回転するなら左右のどっちかに必ずなる、今が左右なら上下のどっちかに必ずなる。ということから回転するたびに上下なのか左右なのかが毎回切り替わって、またその軸ならばどっちの方向にも向くことができる。なので今回の回転の何番目なのかを求めてその偶奇さえわかれば、その偶奇に対応してる軸において正か負で好きな方向に進めるよって偶奇で集計しておけば軸ごとに独立にみることができるので、各軸ごとにdpを行ってそこの軸だけを見たときに、そこの軸だけでいいからその軸は目的地にいけるか？をそれぞれ求めることができるという話 ABC82-D ABC326-F

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up