Yes/No判定問題
多重 for 文の全探索に慣れよう！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の条件を満たす 3 つ組の整数 が存在するかどうかを判定せよ。 の 文字目は 'I' である の 文字目は 'O' である の 文字目は 'I' である 制約 解法 を満たすような …
ちょっと細かいところミスった人も多いかもしれないね。 問題へのリンク 問題概要 ビ太郎は帰省することにした。 今日から 日後の午前に実家に着き、今日から 日後の午前に実家を去る。 それを聞きつけたビバ子は、今日から 日後の午後にビ太郎の実家を訪れ…
問題文が長めだから、丁寧に整理しよう！ 問題へのリンク 問題概要 人の生徒のうち、 人は赤組で、 人は白組である。 生徒の一人である葵さんは、自分が何組かを知りたい。そこで、自分以外の 人がそれぞれ赤組であるか白組であるかを調べた。その結果は長さ…
JOI は教育的な問題が多いね。 問題へのリンク 問題概要 文字 A, B, C, D, E のいずれかからなる文字列 が与えられる。 に 3 種類以上の文字列が登場するならば Yes、そうでないならば No を出力せよ。 解法 次のような 5 個の変数を用意しましょう！ (変数…
少し数学を頑張ろう！ 問題へのリンク 問題概要 A 地点から B 地点に移動するのに 時間，B 地点から C 地点に移動するのに 時間かかる。 A 地点から B 地点を経由して C 地点に移動するとき、 時間 30 分以内に移動することができるか判定せよ。 制約 解法 …
文字式と、if 文の練習！ 問題へのリンク 問題概要 2022 年 11 月 日の 週間後が 11 月 30 日以前ならば 1 を出力し、そうでなければ 0 を出力せよ。 解法 11 月 日の 週間後は、11 月換算で 日 となる。これが 30 以下であるかどうかを判定すればよい。 コ…
for 文の練習問題！ 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 は偶数である。 が「同じ文字列を 2 回繰り返したもの」であるかどうかを判定せよ。 制約 考えたこと 文字列 を前後で半分に割ると 文字ずつになる。よって、次の…
数値を文字列型で受け取るのが楽だと思われる。 問題へのリンク 問題概要 2 桁の整数 が与えられる。 がゾロ目であるかどうかを判定せよ。 解法 (1)： を文字列型で受け取る 最も楽だと思われる方法は、 の値を文字列型で受け取ることだと思われる。たとえば…
とても教育的な典型問題！ 問題へのリンク 問題概要 長さ の英小文字からなる文字列 が与えられる。 この文字列がすべて同じ文字で構成されているかどうかを判定せよ。 制約 考えたこと すべてが同じ文字だということは、「すべてが先頭の文字と同じ文字であ…
実装問題！ 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…
「2 つの区間の交差している部分の長さ」を求める問題は典型。それが 3 次元になってもやることは一緒。 問題へのリンク 問題概要 3 次元空間内の直方体であって、2 点 を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なもの…
問題文の理解が大変かもしれない。 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。次の条件を満たす 2 角整数 () が存在しるかどうかを判定せよ。 「文字列 を 文字ごとに分割したとき、各分割された文字列の 文字目を連結して得られる文字…
条件をいい感じに整理しよう 問題へのリンク 問題概要 文字 'R'、'M'、'S' を 1 文字ずつ含む長さ 3 の文字列 が与えられる。 この文字列 において、文字 'R' が文字 'M' よりも左側にあるかどうかを判定せよ。 考えたこと 文字 'R' が文字 'M' よりも左側に…
部分和問題・ナップサック問題とほとんど同じ DP で解ける！ 問題へのリンク 問題概要 数直線上で座標 0 から出発して、 回のジャンプをする。 回目のジャンプでは、正の方向に または の移動をする。 回のジャンプの末に座標 に到達することが可能かどうか…
上手に考えることで、実装が複雑になりすぎないようにしたい。 問題へのリンク 問題概要 次の図で 番と 番がつながっているかどうかを判定せよ。 制約 考えたこと という制約を考慮すると、Yes となる場合は、次の 10 通りの場合がある。 これらを順に判定し…
ちゃんと証明しようとすると、数学的帰納法などが必要になるが、推測して答えてもいいと思う。 問題へのリンク 問題概要 正の整数 が与えられる。 が成り立つかどうかを判定せよ。 制約 解法 この手の問題では、小さな で実験してみよう！ そうすれば法則性…
オーバーフローについて学ぶ問題。 問題へのリンク 問題概要 与えられた整数 が 以上 未満であるかどうかを判定せよ。 解法 まず、 以上 未満に収まらないような数は int 型では扱えない。long long 型を使おう。 そして、 は 1LL<<31 と表せる。ここで、念…
上手に考えよう！ 問題へのリンク 問題概要 2 × 2 グリッドが与えられる。各マスは白黒に塗られている。 黒色マスの文字は '#' で与えられ、白色マスの文字は '.' で与えられる。黒色マスがすべて連結しているかどうかを判定せよ。 解法 まず、2 × 2 のグリ…
ザ・6Q という感じの問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から 2 個選んで連結して得られる文字列が回文になることがあり得るかどうかを判定せよ。 解法 この問題は 2 つのパートで成り立っている。 個の文字列から つ…
とても面倒な全探索問題 問題へのリンク 問題概要 サイズが等しいとは限らない 3 つの白黒のグリッド が与えられる。 ある巨大なグリッドに、2 つのグリッド を重ね合わて (黒色部分について OR をとる)、そこから適切に長方形領域を切り出すことで、グリッ…
二次元配列の練習問題！ 問題へのリンク 問題概要 種類の栄養素があり、 番目の栄養素を g 以上摂取したい。 そこで、 個の食品を食べる。 番目の食品を食べると、栄養素 を g 摂取できる。 この 個の食品を食べることで、 種類すべての栄養素を必要量以上に…
ソートの練習！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。なお、これら 個の値はすべて互いに相異なる。 これらをすべて混ぜた 個の値を小さい順に並べたとき、数列 の要素が 2 個以上連続する箇所があるかどうかを判定せよ。 制…
いろんな方法が考えられる！ 問題へのリンク 問題概要 1 以上 以下の整数からなる数列 が与えられます。 この数列が を並び替えられることで得られるかどうかを判定せよ。 制約 考えたこと 問題文は「 を並び替えることで に一致させられるか」を問いかける…
累積和をやって、その次にやる類題として、そりゃこれを出すよね！！ って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…
記念すべき「JOI 一次予選」が最初に行われた年の問題。この頃はまだ A 問題も結構難しかったのですね。 問題へのリンク editorial 問題概要 3 個の整数 が与えられる。これらの整数は 1 か 2 のいずれかである。 1 と 2 のうち、どちらの方が多くあるかを判…
「組」を全探索する問題！ 問題へのリンク 問題概要 個の整数 から 3 個選んで、その和を 1000 にすることが可能かどうかを判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; </int></bits/stdc++.h>…
二重 for 文の練習！ 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう！ コード #include <bits/stdc++.h> using na</bits/stdc++.h>…
整数に対する for 文を用いての全探索です！ 問題へのリンク 問題概要 以上 以下の整数のうち、100 の約数であるものは存在するか、判定せよ。 解法 github.com コード #include <bits/stdc++.h> using namespace std; int main() { int A, B; cin >> A >> B; bool res = fa</bits/stdc++.h>…
線形探索法の基本問題！ 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です！ コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…
算数系の問題！ 問題へのリンク 問題概要 解法 入力の中に が含まれるが、これは結局使わない。こういう変数に惑わされないようにしよう。次の 2 つの場合に分けて考える。 のとき (上りのとき) のとき (下りのとき) 前者の場合は、"Yes" となる条件は と書…
