NoviSteps3Q
今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題!!! 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…
DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…
文字を固定したり、数式処理したりなど、総合力が問われる問題! 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう! 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …
方程式を解くのに二分探索が使えることが多々ある! 問題へのリンク 問題概要 正の整数 が与えられる。 を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。 制約 メモ editorial にとても解法が書いてある。 gith…
カッコ列に関連してシミュレーションしていく問題! 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…
とても色んな解法が考えられそうだ。 問題へのリンク 問題概要 以上 以下の 個の整数から相異なる 個の整数を選んで並べて得られる数列 が与えられる。 今、この数列の中に である要素があるならば、その要素を 1 以上 以下の好きな整数に書き換えてよい。 …
平行移動量の候補を絞る考え方を使う! 問題へのリンク 問題概要 座標平面上に 個の星を表す点 が与えられる(星座を成している)。また、それとは別に座標平面上に 個の点 が与えられる。 点 を一斉にある量だけ平行移動すると、それらすべてが、上に述べた…
きちんとした手続きを経て求めたいところ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。この数列に次の操作を繰り返して、数列の項がすべて相異なるようにしたい。できあがる数列の項数の最大値を求めよ。 【操作】 数列から 3 個の整数を選…
差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…
bit 全探索が意外と思い浮かびづらいかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの整数を A, B の 2 グループに分ける。 の最大値を求めよ。 制約 考えたこと bit 全探索を使うと、 個のものに対して「0」「1」の値を割り当…
日頃から「まずは全探索!」という意識があれば、この手の問題は全探索でできると気づけるはず! 問題へのリンク 問題概要 ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。 ビーカーに g の水を入れる ビーカーに g の水を入れ…
これ実は「アルファベット文字の変換テーブルを愚直に作る」という素朴な方法が解けるけど、意外と盲点になりそうだ! 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の 回の操作を実行後の文字列を出力せよ。 【操作】 文字 …
座標ごとに情報を整理するのは頻出! 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている(各人が左右どちらを向いているかは文字列 で与えられる)。 各人が、その位置から、向いている方向に向かっ…
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題! 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
スタックによるシミュレーション問題! 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…
mod 1000000007 をする問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; // a^n mod m template<class T> T mod_pow(T a, T n, T m) { T </class></bits/stdc++.h>…
グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。 左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、…
一次元 DP で「配る DP」が書きやすい問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 マス目に と記された マスの双六がある。1 からスタートして へ進みたい。 マス からマス () に進むことができて:100pt 獲得 マス からマス () に進むこ…
DP の経路復元を学ぶ問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 あるダンジョンには 個の部屋があり、 と番号がついている。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができる。各通路に…
優先度付きキューを人生で初めて試すのにいい問題。 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。販売システムを模している。 クエリタイプ 1:価格が 円の商品が追加される クエリタイプ 2:今ある商品の…
スタックを用いて、かっこの対応をとる問題! 問題へのリンク 問題概要 対応のとれているカッコ列 が与えられる。対応する左かっこ '(' と右かっこ ')' が、それぞれ の何番目と何番目であるかを順に求めよ。 制約 メモ 詳しい解説はここにあるのでメモ程度…
今の時代だとあまり見かけないタイプの数学ゲー問題。 問題へのリンク 問題概要 人 を一列に並べる方法のうち、次の条件をすべて満たすものの個数を 1000000007 で割った余りを求めよ。 人 について、左側にいる人数と右側にいる人数の差が に等しい 制約 考…
とても教育的で典型的なしゃくとり法の問題! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1):しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…
ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…
ビット全探索の要領で列挙できる。だが、実は、部分集合列挙には専用の書き方も存在する! 問題へのリンク 問題概要 非負整数 が与えられる。次の条件を満たす非負整数 を昇順にすべて出力せよ。 と をともに二進法で表すとき、 において値が 1 である桁につ…
ビット全探索の典型問題! 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…
スタックを活用する系の問題! 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …
部分和問題・ナップサック問題とほとんど同じ DP で解ける! 問題へのリンク 問題概要 数直線上で座標 0 から出発して、 回のジャンプをする。 回目のジャンプでは、正の方向に または の移動をする。 回のジャンプの末に座標 に到達することが可能かどうか…
しゃくとり法の基本! 問題へのリンク 問題概要 個の整数 が与えられる。これらの整数から異なる 2 個を選ぶ方法のうち、2 個の値の差が 以下であるものの個数を求めよ。 制約 解法 (1):しゃくとり法 鉄則本の問題なので、鉄則本を参照 #include <bits/stdc++.h> using nam</bits/stdc++.h>…