問題分類

背景

解いた問題が増えてきて類題をパッと出せなくなってきたのでメモしておきます。解いた範囲でまとめます。

当然ですが解法に触れまくるので自力で解きたい人は要注意。

競プロ典型 90 問

001 - Yokan Party（★4）みんなに分けたときの最小値の最大化貪欲決め打ち二分探索	002 - Encyclopedia of Parentheses（★3）括弧列の種類数全探索	003 - Longest Circular Road（★4）辺を一本足して最大のサイクルを作る木の直径
004 - Cross Sum（★2）あるマスのある行と列の和を出す前処理包除原理	005 - Restricted Digits（★7） K種の数字でN桁の数を作って、Bの倍数になる種類数桁DP 行列累乗ダブリング返し二乗法	006 - Smallest Subsequence（★5）長さNの文字列SのK文字の部分列の辞書順最小貪欲
007 - CP Classes（★3）レーティングAとレーティングBの差の絶対値の和を最小化ソート二分探索	008 - AtCounter（★4） N文字の文字列Sから部分文字列でAtCoderとなる種類数 DP 耳DP	009 - Three Point Angle（★6） XY平面で、もっとも180度に近い角をなす三点を探すソート二分探索
010 - Score Sum Queries（★2）２つのクラスのL ~ R の点数の合計をQ回出す累積和	011 - Gravy Jobs（★6）締め切りがDiで、連続するCi日を使ってSiの報酬をもらう。報酬の合計を最大化。ソート DP	012 - Red Painting（★4） HWのグリッドに対して２つのクエリが与えられるので処理・マスを塗る・2マス間を塗られたマスだけで移動できるか判定する UnionFind
013 - Passing（★5）ある点を経由した最短距離を出す始点と終点からダイクストラ	014 - We Used to Sing a Song Together（★3）始点と終点の距離の和を最小化ソート貪欲	015 - Don't be too close（★6）一定以上離れた数値をピックする方法の種類数調和級数組み合わせ二項係数
016 - Minimum Coins（★3） 3つの基底でNを作るとき、必要な要素の最小化工夫した全探索途中結果から最後を確定	017 - Crossing Segments（★7）交差する弦の数条件整理余事象終点でソート Binary Indexed Tree(BIT)	018 - Statue of Chokudai（★3）時間によって変わる位置から、ある地点を見たときの角度三角関数
019 - Pick Two（★6）連続要素を取り除くコストを２数の差の絶対値、全要素を除去した時のコストの最小化区間DP	020 - Log Inequality（★3）対数の大小の比較誤差整数範囲で計算	021 - Come Back in One Piece（★5） DAGの最大サイクルを探す強連結分解(SCC)
022 - Cubic Cake（★2）直方体を立方体に分割したとき、最大の立方体求める最大公約数(GCD)	023 - Avoid War（★7）周囲8マスに別のコマがない置き方の種類数 bit全探索 bitDP 左上からDP/影響範囲だけ保持存在する状態だけチェック	024 - Select +／- One（★2） 2つの数列をK回の1の加減算の操作で一致させる偶奇の一致(パリティ)
025 - Digit Product Equation（★7）各桁の積と元の数字の関係を条件を満たす数字の種類数工夫した全探索ソート重複組み合わせ	026 - Independent Set on a Tree（★4）木から隣り合わない頂点を取り出す方法二部グラフ	027 - Sign Up Requests （★2）存在管理。あるidが存在しないなら処理をする。 map
028 - Cluttered Paper（★4）紙を敷き詰めて指定枚数重なっている場所の面積２次元imos	029 - Long Bricks（★5）長さの異なるブロックを置いてそれぞれの高さを求める座標圧縮区間最大/区間更新のlazySegTree	030 - K Factors（★5）素因数がk個ある数字の種類数素因数分解約数列挙
031 - VS AtCoder（★6）山から石を取るゲームの必勝判定 Grundy数	032 - AtCoder Ekiden（★3） N人で駅伝。険悪な二人は襷をつなげない。かかる時間の最小化全探索別解 bitDP	033 - Not Too Bright（★2）指定領域に条件を満たすように明かりを配置したとき、置ける最大値 1のコーナーケースに注意
034 - There are few types of elements（★4）連続部分列に登場する要素がK個になる、最長部分列を求める尺取り法	035 - Preserve Connectivity（★7）指定した頂点が連結状態であるのに必要な枝の数を最小化木DP 最近共通祖先(LCA) 木の座標圧縮頂点の距離から枝数を出す	036 - Max Manhattan Distance（★5）マンハッタン距離の最大値を出すマンハッタン距離 45度回転
037 - Don't Leave the Spice（★5） L~Rの間で自由に使えるスパイスをちょうどW使い、作った料理の価値を最大化する DP 区間最大SegTree	038 - Large LCM（★3） AとBの最小公倍数を出すが、大きい場合はlargeと出すかける前に割る	039 - Tree Distance（★5）木の頂点間距離の和主客転倒枝を何回通るかで処理木DP
040 - Get More Money（★7）鍵とお金がある家にW円払って入る。ただし、家に入るには鍵が必要。スコアの最大化燃やす埋める問題最大フロー/最小カット	041 - Piles in AtCoder Farm（★7）多角形を作り、内部の格子点の数を数え上げ凸包割り算の切り上げピックの定理	042 - Multiple of 9（★4） 9の倍数かつ、桁の和がKの数字の種類数倍数判定
043 - Maze Challenge with Lack of Sleep（★4）迷路攻略で曲がる回数を最小化拡張BFS 拡張ダイクストラ 01-BFS 方向ごとのパラメータを持つ	044 - Shift and Swapping（★3）数列のシフトとスワップ処理をしたときに、Aiの値を出すシフト回数を保持オフセットを載せてスワップ見かけ上の変化	045 - Simple Grouping（★6） N個の頂点をK個にグルーピング。距離の最大値を最小化 bitDP 部分集合の部分集合
046 - I Love 46（★3） 3つの数列から数字を取ってきて、和を46の倍数にする種類数 modで分類	047 - Monochromatic Diagonal（★7）一定のルールに従ってRGBでグリッドを塗る。斜線の数を数え上げ数字に置き換えローリングハッシュ Z-Algolithm	048 - I will not drop out（★3）満点がA点、部分点がB点のテストで時間内に取る点を最大化時間あたりにとれる点数でソート貪欲
049 - Flip Digits 2（★6） L~Rのビットを反転させるアイテムを使って文字列を変換。一致可能か判定し、可能ならコストの最小化隣接する2つが一致してるかどうかを管理最小全域木クラスカル法	050 - Stair Jump（★3） 1かL進んでちょうどN進む方法の種類数 DP	051 - Typical Shop（★5） N個の商品からK個選んで、合計をP以下にする種類数半分全列挙
052 - Dice Product（★3）サイコロの出目の積が得点。得点の和を出す和を取ってから積を出す	053 - Discrete Dowsing（★7）極大値を１つ持つ数列の極大値の位置を求める。数値は開くまで不明三分探索二分探索微分黄金分割探索	054 - Takahashi Number（★6）すべての頂点に対してのある頂点からの最短距離完全グラフ中点を追加して辺を減らす
055 - Select 5（★2）数列から5つ選んで乗じたときの余りがQになる種類数多重ループ定数倍	056 - Lucky Bag（★5） Ai円とBi円の福袋から選んで、ちょうどS円になるようにする。可能かどうかと購入方法を出す DP復元	057 - Flip Flap（★6）一部の状態を変更する操作で、目標状態を作る操作の種類数操作の合体/置き換え行列の掃き出し
058 - Original Calculator（★4）元の数字と桁和を足してmodを取り数字を変更。K回操作を行ったときの値周期性	059 - Many Graph Queries（★7） DAGで、aからbに到達できるか判断トポロジカル順 DP bit演算で高速化	060 - Chimera（★5）数列Aから極大値を1つ持つ部分列Bを作る。最長部分列の長さを求める両端から処理最長増加部分列(LIS)
061 - Deck（★2）先頭と最後尾に入れる操作と、x番目の要素を出力する操作 deque 大きな配列の真ん中で操作	062 - Paint All（★6）条件つき操作で、すべての操作を完了する DAG 逆から操作	063 - Monochromatic Subgrid（★4） HWのグリッドのうち、一部の行列を取りだして出現する数字が１つになるようにする小さい制約で全探索
064 - Uplift（★3）区間加算減算の操作と、連続数の差の絶対値の和を求める境界だけ操作階差	065 - RGB Balls 2（★7）制約を満たすボールの選び方の種類数組み合わせ/二項係数式変形下限/上限畳み込み FFT	066 - Various Arrays（★5）ランダムで作られる数列の転倒数の期待値期待値
067 - Base 8 to 9（★2） 8進数を9進数に変換。出た数字を一部変更。K回繰り返した値 N進法オーバーフロー	068 - Paired Information（★5） 2つの項の関係が与えられる。ある数を固定した場合、別の数が一意に定まるか判定 UnionFind クエリ先読み	069 - Colorful Blocks 2（★3）条件を満たすようにする種類数漸化式繰り返し２乗法
070 - Plant Planning（★4）マンハッタン距離の総和の最小化 XYの独立操作変化量の観察中央値で最小値	071 - Fuzzy Priority（★7）条件を満たす順列をK個見つける DAG トポロジカルソート DFS	072 - Loop Railway Plan（★4）入れないマスがあるグリッドで、最大ループを求める全探索 DFS バックトラック
073 - We Need Both a and b（★5）ある木にa・b両方の文字を含むように枝を削除する方法の種類数木DP 特徴ごとにDP	074 - ABC String 2（★6）操作できる最大数を求める観察/実験数字で考える不変量	075 - Magic For Balls（★3）素因数分解した数字を２つ作る。操作回数の最小化素因数分解
076 - Cake Cut（★3）全体の1/10になるように連続部分列を選択する円環の延長累積和二分探索	077 - Planes on a 2D Plane（★7）時間で移動するものを、条件を満たすように配置方向でBIT全探索(N≦6) DAG 二部マッチング	078 - Easy Graph Problem（★2）自身より頂点番号が小さい頂点がただ１つ存在する頂点の個数グラフソート
079 - Two by Two（★3） 2*2のマスに操作を行い、別のグリッドと一致できるか判定前から操作	080 - Let's Share Bit（★6）数列の要素すべてとbitAndをとっても0にならないもの種類数包除原理	081 - Friendly Group（★5）条件を満たすようにグループ分け。グループの要素数の最大値二次元平面にプロット累積和包除原理全探索
082 - Counting Numbers（★3） L~Rの間の数字xをx回書く。文字数を求める桁ごとに繰り返しオーバーフロー	083 - Colorful Graph（★6）グラフの頂点と隣接頂点に色を付ける。色を出力する。スターグラフ/ウニグラフ平方分割	084 - There are two types of characters（★3）084 - There are two types of characters（★3）連続区間に〇と×が含まれる区間の数を求める余事象ランレングス圧縮
085 - Multiplication 085（★4） abC = K となるabcの種類数素因数分解約数列挙工夫した全探索	086 - Snuke's Favorite Arrays（★5） bitORの条件を満たす数列の種類数 bitごとに処理 bit全探索	087 - Chokudai's Demand（★5）経路を結ぶ費用を設定し、条件を満たす費用の最大値を求めるワーシャルフロイド広義単調減少二分探索
088 - Similar but Different Ways（★6）数列Aから条件を満たすようにカードを選ぶ方法を1つ出力鳩ノ巣原理 DFS	089 - Partitions and Inversions（★7）数列Aを分割し、各区間のバブルソートに必要な手数の回数の和がK以下になる分割方法の種類数切る/切らないの累乗(K=0) 全探索転倒数尺取り法 Binary Indexed Tree(BIT) 座標圧縮 DP 累積和のDP	090 - Tenkei90's Last Problem（★7）連続部分列の最小値＊長さがK以下になる連続部分列の種類数 DP 行列累乗全探索掛け算の不等式は割り算でまとめる多項間漸化式 FFT 高速きたまさ法ボストン森法

ABC

ABC419	A - AtCoder Language 単語を別の単語で出力分岐	B - Get Min 袋に入れる操作と最小値を取り出す操作 PriorityQueue	C - King's Summit 縦横斜めに移動するものを一か所に集める XY独立最大値と最小値の平均
	D - Substr Swap SとTのL~Rを入れ替える。Q回後の状態を出力 imos法偶奇判定	E - Subarray Sum Divisibility すべてのL個の連続部分列の和がMの倍数になる操作の最小回数 modで分類 dp	F - All Included 与えられたN個の文字列をすべて含むL文字の種類数 Aho-Corasick法 dp
	G - Count Simple Paths 2 未着手

作成日	2025/08/19
最終更新日	2025/08/19

001 - Yokan Party（★4）みんなに分けたときの最小値の最大化貪欲決め打ち二分探索	002 - Encyclopedia of Parentheses（★3）括弧列の種類数全探索	003 - Longest Circular Road（★4）辺を一本足して最大のサイクルを作る木の直径
004 - Cross Sum（★2）あるマスのある行と列の和を出す前処理包除原理	005 - Restricted Digits（★7） K種の数字でN桁の数を作って、Bの倍数になる種類数桁DP 行列累乗ダブリング返し二乗法	006 - Smallest Subsequence（★5）長さNの文字列SのK文字の部分列の辞書順最小貪欲
007 - CP Classes（★3）レーティングAとレーティングBの差の絶対値の和を最小化ソート二分探索	008 - AtCounter（★4） N文字の文字列Sから部分文字列でAtCoderとなる種類数 DP 耳DP	009 - Three Point Angle（★6） XY平面で、もっとも180度に近い角をなす三点を探すソート二分探索
010 - Score Sum Queries（★2）２つのクラスのL ~ R の点数の合計をQ回出す累積和	011 - Gravy Jobs（★6）締め切りがDiで、連続するCi日を使ってSiの報酬をもらう。報酬の合計を最大化。ソート DP	012 - Red Painting（★4） HWのグリッドに対して２つのクエリが与えられるので処理・マスを塗る・2マス間を塗られたマスだけで移動できるか判定する UnionFind
013 - Passing（★5）ある点を経由した最短距離を出す始点と終点からダイクストラ	014 - We Used to Sing a Song Together（★3）始点と終点の距離の和を最小化ソート貪欲	015 - Don't be too close（★6）一定以上離れた数値をピックする方法の種類数調和級数組み合わせ二項係数
016 - Minimum Coins（★3） 3つの基底でNを作るとき、必要な要素の最小化工夫した全探索途中結果から最後を確定	017 - Crossing Segments（★7）交差する弦の数条件整理余事象終点でソート Binary Indexed Tree(BIT)	018 - Statue of Chokudai（★3）時間によって変わる位置から、ある地点を見たときの角度三角関数
019 - Pick Two（★6）連続要素を取り除くコストを２数の差の絶対値、全要素を除去した時のコストの最小化区間DP	020 - Log Inequality（★3）対数の大小の比較誤差整数範囲で計算	021 - Come Back in One Piece（★5） DAGの最大サイクルを探す強連結分解(SCC)
022 - Cubic Cake（★2）直方体を立方体に分割したとき、最大の立方体求める最大公約数(GCD)	023 - Avoid War（★7）周囲8マスに別のコマがない置き方の種類数 bit全探索 bitDP 左上からDP/影響範囲だけ保持存在する状態だけチェック	024 - Select +／- One（★2） 2つの数列をK回の1の加減算の操作で一致させる偶奇の一致(パリティ)
025 - Digit Product Equation（★7）各桁の積と元の数字の関係を条件を満たす数字の種類数工夫した全探索ソート重複組み合わせ	026 - Independent Set on a Tree（★4）木から隣り合わない頂点を取り出す方法二部グラフ	027 - Sign Up Requests （★2）存在管理。あるidが存在しないなら処理をする。 map
028 - Cluttered Paper（★4）紙を敷き詰めて指定枚数重なっている場所の面積２次元imos	029 - Long Bricks（★5）長さの異なるブロックを置いてそれぞれの高さを求める座標圧縮区間最大/区間更新のlazySegTree	030 - K Factors（★5）素因数がk個ある数字の種類数素因数分解約数列挙
031 - VS AtCoder（★6）山から石を取るゲームの必勝判定 Grundy数	032 - AtCoder Ekiden（★3） N人で駅伝。険悪な二人は襷をつなげない。かかる時間の最小化全探索別解 bitDP	033 - Not Too Bright（★2）指定領域に条件を満たすように明かりを配置したとき、置ける最大値 1のコーナーケースに注意
034 - There are few types of elements（★4）連続部分列に登場する要素がK個になる、最長部分列を求める尺取り法	035 - Preserve Connectivity（★7）指定した頂点が連結状態であるのに必要な枝の数を最小化木DP 最近共通祖先(LCA) 木の座標圧縮頂点の距離から枝数を出す	036 - Max Manhattan Distance（★5）マンハッタン距離の最大値を出すマンハッタン距離 45度回転
037 - Don't Leave the Spice（★5） L~Rの間で自由に使えるスパイスをちょうどW使い、作った料理の価値を最大化する DP 区間最大SegTree	038 - Large LCM（★3） AとBの最小公倍数を出すが、大きい場合はlargeと出すかける前に割る	039 - Tree Distance（★5）木の頂点間距離の和主客転倒枝を何回通るかで処理木DP
040 - Get More Money（★7）鍵とお金がある家にW円払って入る。ただし、家に入るには鍵が必要。スコアの最大化燃やす埋める問題最大フロー/最小カット	041 - Piles in AtCoder Farm（★7）多角形を作り、内部の格子点の数を数え上げ凸包割り算の切り上げピックの定理	042 - Multiple of 9（★4） 9の倍数かつ、桁の和がKの数字の種類数倍数判定
043 - Maze Challenge with Lack of Sleep（★4）迷路攻略で曲がる回数を最小化拡張BFS 拡張ダイクストラ 01-BFS 方向ごとのパラメータを持つ	044 - Shift and Swapping（★3）数列のシフトとスワップ処理をしたときに、Aiの値を出すシフト回数を保持オフセットを載せてスワップ見かけ上の変化	045 - Simple Grouping（★6） N個の頂点をK個にグルーピング。距離の最大値を最小化 bitDP 部分集合の部分集合
046 - I Love 46（★3） 3つの数列から数字を取ってきて、和を46の倍数にする種類数 modで分類	047 - Monochromatic Diagonal（★7）一定のルールに従ってRGBでグリッドを塗る。斜線の数を数え上げ数字に置き換えローリングハッシュ Z-Algolithm	048 - I will not drop out（★3）満点がA点、部分点がB点のテストで時間内に取る点を最大化時間あたりにとれる点数でソート貪欲
049 - Flip Digits 2（★6） L~Rのビットを反転させるアイテムを使って文字列を変換。一致可能か判定し、可能ならコストの最小化隣接する2つが一致してるかどうかを管理最小全域木クラスカル法	050 - Stair Jump（★3） 1かL進んでちょうどN進む方法の種類数 DP	051 - Typical Shop（★5） N個の商品からK個選んで、合計をP以下にする種類数半分全列挙
052 - Dice Product（★3）サイコロの出目の積が得点。得点の和を出す和を取ってから積を出す	053 - Discrete Dowsing（★7）極大値を１つ持つ数列の極大値の位置を求める。数値は開くまで不明三分探索二分探索微分黄金分割探索	054 - Takahashi Number（★6）すべての頂点に対してのある頂点からの最短距離完全グラフ中点を追加して辺を減らす
055 - Select 5（★2）数列から5つ選んで乗じたときの余りがQになる種類数多重ループ定数倍	056 - Lucky Bag（★5） Ai円とBi円の福袋から選んで、ちょうどS円になるようにする。可能かどうかと購入方法を出す DP復元	057 - Flip Flap（★6）一部の状態を変更する操作で、目標状態を作る操作の種類数操作の合体/置き換え行列の掃き出し
058 - Original Calculator（★4）元の数字と桁和を足してmodを取り数字を変更。K回操作を行ったときの値周期性	059 - Many Graph Queries（★7） DAGで、aからbに到達できるか判断トポロジカル順 DP bit演算で高速化	060 - Chimera（★5）数列Aから極大値を1つ持つ部分列Bを作る。最長部分列の長さを求める両端から処理最長増加部分列(LIS)
061 - Deck（★2）先頭と最後尾に入れる操作と、x番目の要素を出力する操作 deque 大きな配列の真ん中で操作	062 - Paint All（★6）条件つき操作で、すべての操作を完了する DAG 逆から操作	063 - Monochromatic Subgrid（★4） HWのグリッドのうち、一部の行列を取りだして出現する数字が１つになるようにする小さい制約で全探索
064 - Uplift（★3）区間加算減算の操作と、連続数の差の絶対値の和を求める境界だけ操作階差	065 - RGB Balls 2（★7）制約を満たすボールの選び方の種類数組み合わせ/二項係数式変形下限/上限畳み込み FFT	066 - Various Arrays（★5）ランダムで作られる数列の転倒数の期待値期待値
067 - Base 8 to 9（★2） 8進数を9進数に変換。出た数字を一部変更。K回繰り返した値 N進法オーバーフロー	068 - Paired Information（★5） 2つの項の関係が与えられる。ある数を固定した場合、別の数が一意に定まるか判定 UnionFind クエリ先読み	069 - Colorful Blocks 2（★3）条件を満たすようにする種類数漸化式繰り返し２乗法
070 - Plant Planning（★4）マンハッタン距離の総和の最小化 XYの独立操作変化量の観察中央値で最小値	071 - Fuzzy Priority（★7）条件を満たす順列をK個見つける DAG トポロジカルソート DFS	072 - Loop Railway Plan（★4）入れないマスがあるグリッドで、最大ループを求める全探索 DFS バックトラック
073 - We Need Both a and b（★5）ある木にa・b両方の文字を含むように枝を削除する方法の種類数木DP 特徴ごとにDP	074 - ABC String 2（★6）操作できる最大数を求める観察/実験数字で考える不変量	075 - Magic For Balls（★3）素因数分解した数字を２つ作る。操作回数の最小化素因数分解
076 - Cake Cut（★3）全体の1/10になるように連続部分列を選択する円環の延長累積和二分探索	077 - Planes on a 2D Plane（★7）時間で移動するものを、条件を満たすように配置方向でBIT全探索(N≦6) DAG 二部マッチング	078 - Easy Graph Problem（★2）自身より頂点番号が小さい頂点がただ１つ存在する頂点の個数グラフソート
079 - Two by Two（★3） 2*2のマスに操作を行い、別のグリッドと一致できるか判定前から操作	080 - Let's Share Bit（★6）数列の要素すべてとbitAndをとっても0にならないもの種類数包除原理	081 - Friendly Group（★5）条件を満たすようにグループ分け。グループの要素数の最大値二次元平面にプロット累積和包除原理全探索
082 - Counting Numbers（★3） L~Rの間の数字xをx回書く。文字数を求める桁ごとに繰り返しオーバーフロー	083 - Colorful Graph（★6）グラフの頂点と隣接頂点に色を付ける。色を出力する。スターグラフ/ウニグラフ平方分割	084 - There are two types of characters（★3）084 - There are two types of characters（★3）連続区間に〇と×が含まれる区間の数を求める余事象ランレングス圧縮
085 - Multiplication 085（★4） abC = K となるabcの種類数素因数分解約数列挙工夫した全探索	086 - Snuke's Favorite Arrays（★5） bitORの条件を満たす数列の種類数 bitごとに処理 bit全探索	087 - Chokudai's Demand（★5）経路を結ぶ費用を設定し、条件を満たす費用の最大値を求めるワーシャルフロイド広義単調減少二分探索
088 - Similar but Different Ways（★6）数列Aから条件を満たすようにカードを選ぶ方法を1つ出力鳩ノ巣原理 DFS	089 - Partitions and Inversions（★7）数列Aを分割し、各区間のバブルソートに必要な手数の回数の和がK以下になる分割方法の種類数切る/切らないの累乗(K=0) 全探索転倒数尺取り法 Binary Indexed Tree(BIT) 座標圧縮 DP 累積和のDP	090 - Tenkei90's Last Problem（★7）連続部分列の最小値＊長さがK以下になる連続部分列の種類数 DP 行列累乗全探索掛け算の不等式は割り算でまとめる多項間漸化式 FFT 高速きたまさ法ボストン森法