AtCoder
Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！ 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…
これが ABC の C 問題だったとは...！！！ 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…
グリッドの縦方向の情報と横方向の情報を前処理するのは典型ですね！！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 のグリッドの各マス目に数値が書かれている。 各マス に対して、「そのマスと行または列が等しいマスの数値の総…
とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…
方程式を解くタイプの二分探索の問題ですね。 問題へのリンク 問題概要 正の整数 が与えられます。 秒後のボールの位置 は で表されます。 を満たす実数 の値を十分高い精度で求めてください。 を満たせば正解とみなされます。 制約 解へのアプローチ の解を…
二分探索法の教育的典型問題ですね！！ 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…
包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…
今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…
約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1)：約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…
Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…
いもす法の典型問題 問題へのリンク 問題概要 サイズ 1000001 の配列 v が与えられる (index は、0, 1, ..., 1000000)。 以下の 回の操作を行う。 回目の操作では、 を満たす について、v[x] に 1 を加算する すべての操作を行ったあとの、配列中の値の最大…
木上のパスに関する問題！！ LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…
木の直径の求め方を知っていれば解ける！！ 問題へのリンク 問題概要 頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。 そのために、以下のクエリを 100 回まで投げることがで…
木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …
整合したカッコ列を bit 全探索する問題！！！ 問題へのリンク editorial へのリンク 類題とか drken1215.hatenablog.com drken1215.hatenablog.com 問題概要 長さ の「整合したカッコ列」を辞書順にすべて列挙せよ。 整合したカッコ列の意味については、問…
大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。 問題へのリンク 問題概要 個の風船がそれぞれ初期状態では高度 の位置にあり、1 秒ごとに ずつ上昇する。これらすべての風船を射撃によって割りたい。 競技開始時に 1 個風船…
「最小値の最大化」 (or 「最大値の最小化」) には二分探索が有効という典型ですね。 類題とか (二分探索以外の問題も含むことと、ハイレベルな問題も多いことに注意) drken1215.hatenablog.com 問題へのリンク 解説へのリンク 問題概要 長さ のようかんがあ…
面白かった。リハビリになった。 問題へのリンク 問題概要 長さ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。 それぞれの隣り合う 2 文字に対して それらが同じ文字な…
自明な上界を達成できるパターンだった！ 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…
「決めてから、整合性を確認する」というタイプの問題の典型例ですね！ 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…
これ茶色はさすがにびっくりした！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
いわゆる、 まで調べれば十分というタイプの問題だね。最近そのタイプの問題が流行っている気がする！ 問題へのリンク 問題概要 十進法表記で偶数桁で、かつ、その前半と後半とが文字列として等しいようなものを「良い整数」と呼ぶことにします。 以上 以下…
発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …
むずかしかった！！！ でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！ 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…
lower_bound の練習に！！！ あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…
