よくある priority queue の使い方！ 問題へのリンク 問題概要 個の正の整数 から重複を許して何個か選んだ総和として考えられる値のうち、小さい方から 番目の値を求めよ。 制約 考えたこと この手の priority queue の使い方はよくある。「小さい順に 個を…

順列を題材とした面白い問題。トポロジカルソートの問題でもある。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすもののうち、辞書順最小のものを求めよ。 【 番目の条件】 は よりも先に来る 制約 考えたこと グラフの問題として考えて…

面白かった。priority queue と、「全体に反映させる値を別にもつ」テクニックを学べる問題。 問題へのリンク 問題概要 はじめ、何も入っていない袋がある。次の 回のクエリに答えよ。 クエリタイプ 1：袋に、 と書かれたボールを入れる クエリタイプ 2：袋…

いろんな解法がある。ここでは、ソートで解いてみよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 各数列から要素 を選んだときの差 の最小値を求めよ。 制約 考えたこと 本当にいろいろな解き方がある。その中でも易しいのは、…

いい感じの教育的典型問題。いもす法したあとに累積和する！ 問題へのリンク 問題概要 個のマス がある。 個の区間があって、それぞれマス からマス までを連続して覆っている。 個の区間によって一回以上被覆されるマスの集合を とする。 各区間について、…

集合型を学ぼう！ 問題へのリンク 問題概要 個の文字列 がこの順に与えられる。 初出の文字列に対して、その添字を出力せよ。 制約 解説 0-indexed で考えます。つまり、文字列を とします（出力するときには 1 を足します）。 まずは計算量のことを考えずに…

すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…

グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。 左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、…

LIS。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 長さ の数列 の LIS の長さを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; const int INF = 1 << 29; int main() { int N, res = 0; cin >> N; vector<int> A(N); for (int i = 0; i < N; </int></bits/stdc++.h>…

dp[どこまで見たか][ビット] というタイプのビット DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは 0 または 1 である。いくつかの行を選んで、次の条件を満たすようにしたい。選ぶべき行数の最小値を求め…

すごく面白かった！ 問題へのリンク 問題概要 二次元平面上に点 と という 個の点がある。同一直線上に 3 点が乗ることはない。 の順列 であって、次の条件を満たすものが存在するかどうかを判定し、存在するならば 1 つ示せ。 【条件】 に対して、2 点 , を…

LCS を求める DP の練習。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 2 つの文字列 が与えられる。 の部分列でも の部分列でもあるような文字列の長さの最大値を求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { string S, </bits/stdc++.h>…

部分和問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 個の整数 からいくつか選んで、総和を にすることが可能かどうかを判定せよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { int N, S; cin >> N >> S; vector<int> A(N); for</int></bits/stdc++.h>…

半分全列挙の典型問題！ 問題へのリンク 問題概要 長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。 制約 メモ 「半分全列挙」を用いる。詳細は鉄則本にて。 コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

セグメント木や BIT の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1： が与えられるので、 …

スタックを用いて解決できる典型問題 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、 かつ を満たす最大の を求めよ (存在しない場合は -1)。 制約 メモ スタックを使うと の計算量で解ける。詳細は鉄則本を参照。 コード #include <bits/stdc++.h> usi</bits/stdc++.h>…

差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…

繰り上がりがあるから、ただの「桁 DP」よりは難しい。でも少しの工夫で解ける！ 問題へのリンク 問題概要 1 個の正の整数 が与えられる。次の条件を満たす整数 が存在するような整数の組 の個数を 1000000007 で割った余りを求めよ。 xor = 制約 考えたこと…

「最大値と最小値の差」を最小化せよと言われたら、最大値または最小値を固定すると上手くいくことが多い！ 問題へのリンク 問題概要 サイズが であるような 4 つの数列 が与えられる。 これらの数列から 1 個ずつ要素を選んで とする。 の値の最小値を求め…

平行移動量の候補を絞る考え方を使う！ 問題へのリンク 問題概要 座標平面上に 個の星を表す点 が与えられる（星座を成している）。また、それとは別に座標平面上に 個の点 が与えられる。 点 を一斉にある量だけ平行移動すると、それらすべてが、上に述べた…

全探索の基礎になるような再帰関数の使い方！ 問題へのリンク 問題概要 以下の条件を満たす長さ の整数列を辞書順で小さい方から順に出力せよ。 番目の要素は 以上 以下 総和が の倍数 制約 考えたこと このように、長さ のさまざまな数列を生成する方法につ…

ビット全探索の典型問題！ 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…

木の直径の問題！ 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…

よくある、パズルの最小手数を求める問題！ この手の問題では、まず「あり得る状態」がどれだけあるかを見積もろう！ 問題へのリンク 問題概要 マスがあって、最初、前から マスには白石か黒石のいずれかが置かれている。置かれ方は文字列 で表される。後ろ …

部分和問題・ナップサック問題とほとんど同じ DP で解ける！ 問題へのリンク 問題概要 数直線上で座標 0 から出発して、 回のジャンプをする。 回目のジャンプでは、正の方向に または の移動をする。 回のジャンプの末に座標 に到達することが可能かどうか…

包除原理の基本！ 問題へのリンク 問題概要 1 以上 以下の整数のうち、 のいずれかで割り切れるものの個数を求めよ。 制約 考えたこと 包除原理の超典型問題。たとえば のときは、次のように考えればよい。 (V[0] で割り切れる個数) + (V[1] で割り切れる個…

共通テスト数学 IA にも似た問題が出ていた！ 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…

しゃくとり法の練習問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 editorial に詳しく書かれている。 github.com コー…

ものすごく教育的な典型問題！ 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…

鉄則本 B11 とほぼ同じ問題！ 問題へのリンク 問題概要 身長が であるような 人がいる。以下の 回のクエリに答えよ。 【クエリ】 整数 key が与えられるので、身長が key 以上の人が何人いるかを答えよ。 制約 考えたこと 0-indexed で考えます。 最初に、 …