包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 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 個風船…

「最小値の最大化」には二分探索が有効という典型ですね。 問題へのリンク 解説へのリンク 前提知識 二分探索にまったく経験がない場合は、まずは次の記事を読んでみてください。 qiita.com 問題概要 長さ のようかんがあって、そのうち左端から の位置に切…

面白かった。リハビリになった。 問題へのリンク 問題概要 長さ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。 それぞれの隣り合う 2 文字に対して それらが同じ文字な…