N個のものうち1個を変更・削除したものを解く
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
左右からの累積和・累積 max を前処理で求めておくのは、よくある典型！！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…
Union-Find 慣れしていれば解きやすい！ 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…
個のものから 個除いたものを考えるのは色々定石がある！ 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、 を除外した 個の整数の最大値を求めよ。 制約 解法 (1)：アドホックに考える まずは素朴な解法を考えてみる。たとえば とかだったと…
「3 つのものの真ん中に着目する」という典型が学べる。面白かった！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…
Greedy を考察して、さらに左右から累積和を求める！結構難しい！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数…
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…
結構難しい！！ 問題へのリンク 問題概要 正の整数 に対して、 := を二進法表現したときの各桁の総和を として を で割ったあまり := を で置き換える操作を繰り返したときに、何回で 0 になるか として定める。たとえば のとき、, より、 となる。 今、二進…
戻す DP シリーズのトレーニング 問題へのリンク 問題概要 (入力形式は多少改変) 正の整数 と、 個の正の整数 が与えられる。これらをランダムシャッフルする。 を満たす最小の を考える。この値の期待値を求めよ (要求精度は )。 制約 考えたこと 各要素 に…
めっちゃいろんな解法がある！ 各 i に対して i 番目を抜いた部分の解を求める系 左右から累積和 戻す DP 単調性を見抜いて二分探索 問題へのリンク 問題概要 個の整数 がある。これらの整数の部分集合のうち、数の総和が 以上になるものをよい集合と呼びま…
戻す DP を履修して行く！！！ 問題へのリンク 問題概要 個の正の整数 と正の整数 が与えられる。以下の 個のクエリに答えよ。 整数 が与えられる 以下の条件を満たす 0 以上の整数の組 () の個数を 1000000007 で割ったあまりを求めよ 制約 考えたこと この…
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…
差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…
嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…
累積和！累積和！累積和！！！ でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…
累積和の典型問題 問題へのリンク 問題概要 WWEWEEWWEE のような文字列が与えられる。 文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。 制約 解法 累積和を用いる。 #include <iostream> #includ</iostream>…
