「変数を固定する考え方」と「set の活用」を組み合わせる練習問題！ 問題へのリンク 問題概要 整数 と、 個の整数 が与えられる。 を満たす [tex i, j] ( でもよい) が存在するかを判定せよ。 制約 考えたこと この問題のように、 という 2 つの変数を考え…

set の練習問題！ 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 について、 の中に と一致するものがあるかどうかを判定せよ。 制約 各文字列の長さは 10 以下 考えたこと set 型のよい練習問題。 を格納する集合（C++ であれば set<string> </string>…

整数値の各桁の値の和を求める方法を確認しておこう！ 問題へのリンク 問題概要 整数 を十進法で表したときの各桁の数字の和が、 を割り切るとき、 をハーシャッド数という。 与えられた整数 がハーシャッド数であるかどうかを判定せよ。 解法 整数 の各桁の…

全探索しよう！ こういう問題で、ただちに「全探索しよう」と思えるかどうかがすごく大事！ 問題へのリンク 問題概要 長さの等しい文字列 が与えられる。 に対して、次の操作を高々 1 回実行することで、 に一致させられるかどうかを判定せよ。 (操作) の隣…

A 問題としては、少し難しめな感じ。 問題へのリンク 問題概要 1, 2, 3, 4, 5 を並び替えて得られる数列 が与えられる。この数列に対して 「隣接する様子を swap する」 という操作をちょうど 1 回だけ行って、単調増加にできるかどうかを判定せよ。 考えた…

いろんな解法が考えられる。 問題へのリンク 問題概要 4 枚のカードがあって、それぞれのカードには整数 が書かれている。 ここに 1 枚カードを加え、フルハウスとできるか判定せよ。 制約 考えたこと 色んな解法が考えられるが、この手のものは「ソート」が…

これ系の問題、最近あまり見かけなくなった気がする。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。 この数列の項を適切に並び替えることによって、「どの隣接する 2 項の積も 4 の倍数」となるようにできるかどうかを判定せよ。 制約 …

すごく面白い問題だった！ 二重頂点連結成分分解からの Block-Cut 木ライブラリを試す目的で解いてみた。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点について、次の問に答えよ。 その点を除去した上で、各点に対応する頂点数 のグラフを考…

とても教育的な易しい問題！ 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。 の文字がすべて互いに相異なるかどうかを判定せよ。 解法 (1)：多重 for 文 最も素朴な方法は、 から 2 文字を選ぶ方法をすべて試して、「それらが異なっている…

場合分けを頑張ろう！ 問題へのリンク 問題概要 3 つの整数 をいくつかのグループに分けて、各グループに含まれる整数の総和を等しくできるかを判定せよ。 考えたこと 次の 2 つの場合が考えられる。 2 つのグループに分けて、総和を等しくする 3 つのグルー…

ちゃんと整理するのは大変だ。落ち着いて整理しよう。 問題へのリンク 問題概要 長さ の文字列 が与えられる。 が "11/22 文字列" であるかどうかを判定せよ。 11/22 文字列であるとは、文字 1, /, 2 がこの順に並んでいて、1 と 2 の個数が等しいものをいう…

for 文の練習問題 問題へのリンク 問題概要 長さの等しい 2 つの文字列 が与えられる。 に含まれる各文字 '@' について、'a', 't', 'c', 'o', 'd', 'e', 'r' のいずれかに置き変えることで、 が一致するようにできるかを判定せよ。 制約 [tex 1 \le |S| = |T…

素朴な map の練習問題 問題へのリンク 問題概要 りんごさんは 個の問題案を持っており、 個目の問題案の難易度は である。 ここから、配点が であるような 問からなる問題セットを作ることは可能か？ 制約 考えたこと 連想配列 (C++ ならば map) の練習問題…

ソートが使えるなら、それが楽だと思う 問題へのリンク 問題概要 6 桁の正の整数 が与えられる。 が次の条件を満たすかどうかを判定せよ。 1 をちょうど 1 個含む 2 をちょうど 2 個含む 3 をちょうど 3 個含む 解法 (1)：1, 2, 3 の個数を数える方法 for 文…

久しぶりに高難易度問題を解いてみた！ 問題へのリンク 問題概要 各マスの値が 0 または 1 である グリッドを考える。 グリッド のマス が「固定されている」とは、次の条件を満たすすべての グリッドについて、マス の値が一意に決まることをいう。 すべて…

座標ごとに情報を整理するのは頻出！ 問題へのリンク 問題概要 x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている（各人が左右どちらを向いているかは文字列 で与えられる）。 各人が、その位置から、向いている方向に向かっ…

set の練習！ 問題へのリンク 問題概要 二次元平面上に高橋君がいる。高橋君は原点から移動を 回行った。 回の移動は長さ の文字列で表される。各文字は L（左へ移動）、R（右へ移動）、U（上へ移動）、D（下へ移動）のいずれかである。 高橋君が同じ座標に…

面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…

弦が交わるかどうかを判定するという、スタックの典型問題！ 問題へのリンク 問題概要 次の図のように、円周上に 個の点 があり、 本の弦がある（図は のとき）。 弦に交差があるかどうかを判定せよ。 制約 考えたこと この問題は stack で解けることで有名…

昔の ABC A 問題はこういうのよくあった！ 問題へのリンク 問題概要 3 文字の文字列 が与えられる。これを並び替えることで "ABC" に一致させることができるかどうかを判定せよ。 考えたこと 並び替えて "ABC" に一致する文字列は "ABC" "ACB" "BAC" "BCA" "…

ちょっとした算数・数学の問題！ 問題へのリンク 問題概要 考えたこと A, B, C, D, E をそれぞれ 0, 1, 2, 3, 4 と対応させよう（0 始まりにするのがコツ）。このとき、対角線の長さは、対角線の両端に対応する数値の差で表すことができる。 たとえば、線分 …

スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…

探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…

面白かった！！ 実験で思いつけるかもしれないし、気づいたら証明したい系。 問題へのリンク 問題概要 先手と後手が石取りゲームをする。2 個の山があって、最初それぞれ石が 個積まれている。交互に次の操作をする。 2 個以上の石が積まれている山を 1 つ選…

関数 substr() の練習！ 問題へのリンク 問題概要 4 文字以上 30 文字以下の文字列 が与えられる。 の末尾 3 文字が "san" であるかどうかを判定せよ。 考えたこと 文字列 の末尾 3 文字は S.substr(S.size() - 3) で取得できる。 これが "san" かどうかを判…

すごく面白かった！ 問題へのリンク 問題概要 二次元平面上に点 と という 個の点がある。同一直線上に 3 点が乗ることはない。 の順列 であって、次の条件を満たすものが存在するかどうかを判定し、存在するならば 1 つ示せ。 【条件】 に対して、2 点 , を…

部分和問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 個の整数 からいくつか選んで、総和を にすることが可能かどうかを判定せよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { int N, S; cin >> N >> S; vector<int> A(N); for</int></bits/stdc++.h>…

半分全列挙の典型問題！ 問題へのリンク 問題概要 長さが の 4 つの数列が与えられる。これらから要素を 1 個ずつとってきて、総和を にすることが可能か判定せよ。 制約 メモ 「半分全列挙」を用いる。詳細は鉄則本にて。 コード #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

少し実装が重たい全探索問題！ 問題へのリンク 問題概要 の白黒グリッド と、 の白黒グリッド が与えられる ()。 グリッド のパターンがグリッド の中に含まれるかどうかを判定せよ。 制約 考えたこと グリッド のすべてのマス について、次の判定をしていけ…

バケットを活用する練習問題！ 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は （'M' または 'F'）であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…