ある値を固定して考える
半分全列挙の典型問題！ 問題へのリンク 問題概要 長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。 制約 メモ 「半分全列挙」を用いる。詳細は鉄則本にて。 コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…
「最大値と最小値の差」を最小化せよと言われたら、最大値または最小値を固定すると上手くいくことが多い！ 問題へのリンク 問題概要 サイズが であるような 4 つの数列 が与えられる。 これらの数列から 1 個ずつ要素を選んで とする。 の値の最小値を求め…
実はとても単純な解法に落とし込めるのだけど、発想がちょっと難しい 問題へのリンク 問題概要 AtCoder 王国の 1 週間は 日あり、最初の 日が休日、後半の 日が平日である。 高橋君は 日分の予定があり、それぞれ 日目に予定がある。 これらの予定日がすべて…
「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする！ 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …
少し数学チックな問題！ 問題へのリンク 問題概要 二次元の座標平面上に 個の点がある。点 の座標は である。 これら 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。 制約 考えたこと であるような…
とても色んな解法が考えられそうだ。 問題へのリンク 問題概要 以上 以下の 個の整数から相異なる 個の整数を選んで並べて得られる数列 が与えられる。 今、この数列の中に である要素があるならば、その要素を 1 以上 以下の好きな整数に書き換えてよい。 …
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
めっちゃ面白い問題！！ 実はよく似た類題として次の問題がある！ atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…
面白かった！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 の値を求めよ。 制約 考えたこと まず、 という制約が怪しい！！！ きっと、 として な計算量になるに違いないと思えた。 とりあえず、数列を元のまま考えるのではなく、…
しゃくとり法の練習問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 この数列の連続する区間であって、総和が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 editorial に詳しく書かれている。 github.com コー…
しゃくとり法の基本！ 問題へのリンク 問題概要 個の整数 が与えられる。これらの整数から異なる 2 個を選ぶ方法のうち、2 個の値の差が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 鉄則本の問題なので、鉄則本を参照 #include <bits/stdc++.h> using nam</bits/stdc++.h>…
ものすごく教育的な典型問題！ 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…
次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
文字を固定したり、数式処理したりなど、総合力が問われる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
コンテスト後に解いた。なんとか詰め切った。 問題へのリンク 問題概要 非負整数 と整数 に対して、関数 を次のように定義する。 正整数 が与えられて、次の条件を満たす非負整数列 と正の整数 の組の個数を 998244353 で割った余りを求めよ。 () 制約 考え…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
また一つ、プリューファーコードの練習問題が増えた！ 問題へのリンク 問題概要 正の整数値 が与えられる。 頂点数 の重み付き木であって、以下の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 各辺の重みは 以上 以下の整数値である 2 頂点 …
なんとか通した。結構迷走した。 問題へのリンク 問題概要 0 と 1 と 2 のみからなる の行列が与えられる。これらの行列のある 3 つの行が good であるとは、「どの列についても、それら 3 行の値がすべて等しいか、すべて互いに異なる」という条件を満たす…
色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…
Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
すごく典型的ないい問題！ この手の問題は、大抵、二分探索法でもしゃくとり法でも解ける。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらの数列から 1 つずつの値を選ぶ。選んだ値の差が 以下となるようにすることが可能かどうかを判定し、…
なんかユーザー解説の数がすごいことになっててビビる！ 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…
これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…
「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…
基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける！ 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…
opt さんの得意系って感じだった！ 問題へのリンク 問題概要 一辺の長さが整数 の正 角形がある。 頂点から始めて、周上に距離 1 ごとに黒い石か白い石を置いていく。 石の置き方のうち、各辺上にある白い石の個数が等しくなるようなものの個数を 998244353 …
