NoviSteps3Q
これは A07 と大体一緒ですね！ 問題へのリンク 問題概要 あるコンビニは時刻 0 に開店し、時刻 に閉店する。 人の従業員が働いていて、従業員 は時刻 に出勤して、時刻 に退勤する。 について、時刻 に何人の従業員が働いているかを求めよ。 制約 解法 gith…
いもす法！！ 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照！！ コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…
昔ながらの典型考察 Greedy 問題。 問題へのリンク 問題概要 本の刀がある。 刀 を振ると、敵に だけダメージを与える。何度でも振ることができる 刀 を投げると、敵に だけダメージを与える。刀 を失うので、もう投げることも振ることもできなくなる 敵に …
の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう！ 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …
面白かった！ 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…
文字を固定したり、数式処理したりなど、総合力が問われる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
stack を使ってカッコ列判定をする問題の亜種！ 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…
lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…
またまた登場！！ グラフの連結成分の個数を求める問題！ 問題へのリンク 問題概要 下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。 このとき、グリッド内に何個の '#' の塊があるかを…
グラフ探索の問題として、人生で最初に解きたい問題！！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられる。 このグラフの連結成分の個数を求めよ。 制約 解法 まず、単純グラフや連結成分という概念についてはこちら！ algo-method.c…
DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…
Functional グラフのサイクル検出問題！ 問題へのリンク 問題概要 頂点数 のグラフが与えられる。頂点 からは頂点 への辺が接続していて、辺数は全部で 本ある。 このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的に…
今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題！！！ 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…
人生で最初に解きたい BFS の問題！ 問題へのリンク 問題概要 のグリッドが与えられます。各マスは壁 (文字 '#')、通路 (文字 '.') のいずれかです。通路マスに入ることはできますが、壁マスに入ることはできません。 スタートマス (入力で与えられる) から…
とてもいい感じの BFS の練習問題！ 問題へのリンク 問題概要 "atcoder" の並び替えである文字列 が与えられます。 文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。 最小何回の操作で実…
木を探索する練習問題。頭を柔らかくするのが肝心。 問題へのリンク 問題概要 あなたはアメーバの観察記録をつけました。最初 匹のアメーバがおり、番号は です。 観察記録は時系列順に 個あり、 番目の観察記録は 番号 のアメーバが分裂して消滅し、 新たに…
単純な DFS / BFS 系はいよいよ灰色 diff になったのですね。 問題へのリンク 問題概要 二次元平面上に 人がいます。 番目の人は座標 にいます。 今、 番目の人がウィルスに感染しました。ウイルスに感染した人から距離が 以内にいる人にウイルスは次々とう…
すごく典型的ないい問題！ この手の問題は、大抵、二分探索法でもしゃくとり法でも解ける。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらの数列から 1 つずつの値を選ぶ。選んだ値の差が 以下となるようにすることが可能かどうかを判定し、…
「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！ 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…
これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…
結構整理するの大変！ 茶色あっても良さそうだと思ったけど、灰色上位問題だった。 問題へのリンク 問題概要 2 つの長さ の文字列 が与えられる。これらは英小文字または文字 '@' のみからなる。 の各文字 '@' は、"atcoder" に含まれるいずれかの文字に変え…
クエリ形式の問題に慣れたり、クエリに答えるためのデータ構造を考えたりすることに慣れたりするための練習問題！ 問題へのリンク 問題概要 1 から までの番号のついた 個の箱と、何も書かれていない無数のカードがある。今、 個のクエリが与えられるので、…
慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…
Union-Find の最も典型的な練習問題 問題へのリンク 問題概要 頂点 辺の無向グラフに 個のクエリが飛んでくる ：辺 を追加する ： 頂点間 が連結ならば 1、そうでないなら 0 を出力する 制約 解法 Union-Find はグループ分けを管理するデータ構造です。以下…
単純な全探索で解ける！ 累積和で高速化したり DP したりしても OK 問題へのリンク 問題概要 のマス目があり、上から 行目、左から 列目のマスをマス と表すことにする。マス には 個のアメが置かれている。 あなたははじめ、左上のマス にいる。 右方向ま…
実はアルゴ式でもよく似た問題をすでに出していました！ algo-method.com 問題へのリンク 問題概要 がこの順に並んでいます。この数列に対して 回のクエリが投げられました。 各クエリでは、値 が指定されて、次の操作を実行します。 数列中の整数 に対し、…
ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…
一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…
