そのまま覚えたいシンプル設定の中堅以上の典型問題
面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
包除原理した！ 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか？ 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
方針を決めるのが大変な問題。 問題へのリンク 問題概要 二次元平面上の 個の格子点に碁石が置かれている。 このとき、碁石によって囲われている格子点の個数を求めよ。より正確には、「その空き格子点から上下左右の空き格子点への移動を繰り返して点 (-1, …
平面走査の典型問題だけど、とにかく重くて辛かったのと、コーナーケースになかなか気づけなかった。 問題へのリンク 問題概要 数直線上に 個の区間がある。区間 は である ()。 = 区間 が、与えられた 個の区間のうち何個と交差するか としたときに、 の範…
これはもう、editorial にある図がすべてなので備忘録程度に！ 問題へのリンク 問題概要 のグリッドがある。 個の石があり、石 は、 かつ を満たすようなマス に置くことができる。 ただし、どの行・どの列についても、2 個以上の石が置かれないようにする。…
全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…
平均算！ 問題へのリンク 問題概要 整数 が与えられる。 と の平均が になるような整数 を求めよ。 解法 平均の定義から、 となる。これを について解くと、 となる。このような式変形は中2「式の計算」で学ぶ。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…
が等差数列かどうかを判定する問題 問題へのリンク 問題概要 3 つの整数 が等差数列かを判定せよ。 すなわち、 であるかどうかを判定せよ。 解法 問題文の通りに、b - a == c - b かどうかを判定すれば OK。 #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
ランレングス圧縮の典型題！ なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…
タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ()：数列の区間 内の各要素の値につい…
遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…
次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…
最小カットの練習問題。問題設定がとても面白い！ 問題へのリンク 問題概要 のグリッドがある。いくつかのマスにはヤギがいる。具体的な入力では、ヤギのいるマスは文字 'X' で表される。 6 6 ...... ...... ..X... .X..X. ..X... ...... グリッドの外周は外…
「与えられたグラフを強連結成分分解すると DAG になるので、DAG 上で DP する」というのが想定解だが、フローでも解けると話題になった問題！ 問題へのリンク 問題概要 頂点数 の有向グラフがある。最初、すべての頂点は白色である。以下の操作を 2 回行う…
最大流アルゴリズムを実装したときの verify に 問題へのリンク 問題概要 頂点数 、辺数 のフローネットワークが与えられる。 番目の辺は頂点 から頂点 へ張られていて、容量は である。 頂点 を始点、頂点 を終点とした最大流値を求めよ。 制約 考えたこと …
セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない！ 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…
文字列の標準入力と、先頭の文字がわかっていれば解ける系 問題へのリンク 問題概要 "AtCoder s Contest" という形の文字列 が与えられる (s の部分は任意)。 たとえば、"AtCoder Beginner Contest" のような文字列が与えられる。これを "ABC" のように略し…
遅延評価セグメント木の練習問題！ 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R)：文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R)：文字列 …
プリューファーコードが使える問題！ 今でこそ高度典型となったが、当時は知られていなかった気がする。 問題へのリンク 問題概要 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 …
面白い最適化問題！ 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…
これは学びの深い DP 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
整数の入門にいい感じの問題！ 問題へのリンク 問題概要 正の整数 と非負整数 が与えられる。次の条件を満たす正の整数 の個数を求めよ。 を で割った余りが である 制約 解法 を で割ったときの商を とおくと、 と表せる。これを式変形すると となる。この…
2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…
ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索！ 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
