この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…

制約が小さいので for 文だけでも解けるし、map などを使うともっと楽になる。 問題へのリンク 問題概要 個の文字列 が与えられる。 登場回数の最も多い文字列を答えよ（タイがある場合はどれを答えても良い）。 制約 考えたこと 次の連想配列を用いて解いた…

ちょっと整理が大変な複雑な問題。 問題へのリンク 問題概要 ルーレットによって 0 から 36 までのいずれかの整数が出される。 人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。 実際に出た整数は であった。 に賭けていた人のうち、賭けた整…

サンプルを見れば上限が分かる系の問題！ 問題へのリンク 問題概要 各桁の値が 1 である数をレプユニット数という。 レプユニット数 3 個の和として考えられる数のうち、 番目に小さい数を求めよ。 制約 考えたこと まず、問題文の条件を満たす数をトリレプ…

多重 for 文の練習問題！ 問題へのリンク 問題概要 二次元平面上に 人の学生と、 個のチェックポイントがある。学生 は座標 にいて、チェックポイント は座標 にいる。 各学生について、その学生からマンハッタン距離が最も近いチェックポイントを求めよ (タ…

ちょっと重たい全探索問題 問題へのリンク 問題概要 の形に配列された二次元文字列 が与えられる。 に対して、次の操作を繰り返すことで に一致させたい。 反時計回りに 90 度回転する (コスト 1) 時計回りに 90 度回転する (コスト 1) 1 マス選んで文字を変…

多重 for 文の練習！ 問題へのリンク 問題概要 2 つの数列 、 が与えられる。数列 からそれぞれ 1 個ずつ選んでできる 個のペアについて 「その和」と「その最大値」の積 を求めて、それらの総和を求めよ。 制約 考えたこと 2 つの数列からそれぞれ要素をと…

とても教育的な問題！ ちゃんと解くには、計算量の理解が必要となる問題である。 問題へのリンク 問題概要 3 つの数列 が与えられる。これらの数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、 からそれぞれ 1 個ずつ選んで和を…

これも色んな解法がある！ 問題へのリンク 問題概要 英小文字からなる 3 文字以上 100 文字以下の文字列 が与えられる。 はある 1 文字を除いて全て同じ文字で構成されています。その異なる文字があるのは何文字目か？ 制約 解法 (1)：全探索 大抵の問題は、…

意外と頭がこんがらがる 問題へのリンク 問題概要 人の人 がいて、人 の名字は 、名前は である。 各人にニックネームをつけたい。人 のニックネーム は または である かつ である任意の に対して、 かつ である という条件を満たす必要がある。このような…

ペアを全探索する問題！ 問題へのリンク 問題概要 人がいて、人 の名字は 、名前は である。 同姓同名であるような人の組が存在するかを求めよ。 制約 考えたこと 0-indexed で考える。 を満たす であって、 かつ を満たすものが存在するかどうかを求めれば…

二次元配列を見ていく問題 問題へのリンク 問題概要 次のような のグリッドが与えられる。各マスの文字は '.' や '#' である。 文字が '#' であるようなマスの個数を求めよ。 制約 考えたこと 今回のような入力は「長さ の文字列を 個格納した vector<string> 型の配</string>…

集計処理系の良問！ 問題へのリンク 問題概要 英小文字からなる文字列 について、どの英小文字も登場回数が偶数回であるかどうかを判定せよ。 制約 解法 (1)：各文字について登場回数を見ていく まずは愚直な解法を考えよう。文字 = 'a', 'b', ..., 'z' につ…

多重 for 文に慣れよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 を満たす整数の組 の個数を求めよ。 制約 解法 多重 for 文に慣れましょう！ 数列 の 番目と、数列 の 番目をすべて調べるのは、次のような 2 重の for 文で記…

多重 for 文の全探索に慣れよう！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の条件を満たす 3 つ組の整数 が存在するかどうかを判定せよ。 の 文字目は 'I' である の 文字目は 'O' である の 文字目は 'I' である 制約 解法 を満たすような …

一見難しく見えるけど、実は単純な問題！ 問題へのリンク 問題概要 整数 の書かれた 個の宝箱と、整数 の書かれた 個の鍵がある。 宝箱 は整数 が書かれた鍵を使うことで解錠できる。同じ鍵を使って複数の宝箱を解錠してもよい。 解錠できる宝箱の個数の最大…

愚直に数えるのが簡単だと思う。 問題へのリンク 問題概要 人の生徒のマラソン大会のタイム が与えられる。 各生徒の順位を求めよ。具体的には各生徒 について、( 未満のタイムの個数) + 1 を求めよ。 制約 解法 各 に対して、具体的に「( 未満のタイムの個…

二次元配列の練習問題 問題へのリンク 問題概要 の形状に並べられた行列が与えられる。行列の各要素は 0 以上 26 以下の整数値である。 今、この行列の各要素に対応して 0 は文字 '.' に 1〜26 はそれに対応するアルファベット文字に 置き換えて得られる の…

二重の for 文に慣れよう！ 問題へのリンク 問題概要 長さが の数列 と、長さが の数列 が与えられる。 を満たすような組 (, ) の個数を求めよ。 制約 考えたこと この問題に限らず、2 つの数列からそれぞれ要素 をとってきて、それが条件を満たすかどうかを…

問題文の理解が大変かもしれない。 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。次の条件を満たす 2 角整数 () が存在しるかどうかを判定せよ。 「文字列 を 文字ごとに分割したとき、各分割された文字列の 文字目を連結して得られる文字…

二次元配列の基本問題！ ただし、問題文の意味を理解するのが少し大変かもしれない。 問題へのリンク 問題概要 のグリッドがある。グリッドの各文字は最初はすべて '.' である。今、 を満たす整数 をとり、 かつ を満たすマス の文字を '#' へと書き換えた。…

二次元配列の練習問題！ 問題へのリンク 問題概要 種類の栄養素があり、 番目の栄養素を g 以上摂取したい。 そこで、 個の食品を食べる。 番目の食品を食べると、栄養素 を g 摂取できる。 この 個の食品を食べることで、 種類すべての栄養素を必要量以上に…

二次元配列を二重 for 文で調べる最低ライン！ 問題へのリンク 問題概要 のグリッドにアルファベット文字が書かれたものが 2 つ () 与えられます。 これらは 1 箇所のみ異なっていることが保証されます。 であるような を答えてください。 制約 解法 (C++) …

「組」を全探索する問題！ 問題へのリンク 問題概要 個の整数 から 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>…

とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1)：値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…

ランレングス圧縮の典型題！ なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…

9 × 9 に並んだ数字が「数独」の解になっているかを判定する問題 問題へのリンク 問題概要 下のような 9 × 9 グリッドが与えられる。各マスの値は 1 から 9 までの整数値である。 このグリッドが数独の要件を満たすかを判定せよ。 1 2 3 4 5 6 7 8 9 4 5 6 7…

3 重の for 文を書くのが楽だと思う 問題へのリンク 問題概要 3 種類の文字 .、|、* からなる、長さ の文字列 が与えられる。 には | がちょうど 2 つ、* がちょうど 1 つ含まれる。 * が 2 つの | に挟まれているかどうかを判定せよ。 考えたこと 色々な解…

最長回文を求める問題！ 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列のうち、回文であるものについて、最長の長さを求めよ。 考えたこと この問題は次の 2 ステップに分かれている。 の連続する部分文字列を全種類抜き取る それら…