そのまま覚えたい易しい教育的典型問題
の制約が小さいので、「区間」を思い切って全部探索しよう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 を満たすような についての、 の値の最大値を求めよ。 制約 解法 この手の問題で悩んでしまうのはもったいないと言えます！ まずは、コンピ…
集計処理を練習しよう！ 問題へのリンク 問題概要 以上 以下の整数からなる、長さ の数列 が与えられる。 長さ の新たな数列 を次のように定義する。 各 に対して、 を、 を満たす の個数 の最大値を求めよ。 制約 解法 問題の意味を解釈するのが難しいかも…
多重 for 文の全探索に慣れよう！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の条件を満たす 3 つ組の整数 が存在するかどうかを判定せよ。 の 文字目は 'I' である の 文字目は 'O' である の 文字目は 'I' である 制約 解法 を満たすような …
このような問題を解くためにも、「バケット」を習得しよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 こっらの数列の双方に登場する数をすべて昇順で出力せよ。 制約 解法 (1)：1 から 100 までの数を順に調べる 制約を見よう…
集計処理の面白い問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 に出現する整数のうち、出現回数が最小である整数を出力せよ。そのようなものが複数あるときは、そのうちの最小の整数を出力せよ。 制約 解法 このような出現頻度に関する問題で…
for 文の練習問題！ 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 は偶数である。 が「同じ文字列を 2 回繰り返したもの」であるかどうかを判定せよ。 制約 考えたこと 文字列 を前後で半分に割ると 文字ずつになる。よって、次の…
回転寿司を題材にした、とても教育的な面白い問題！ 問題へのリンク 問題概要 高橋君は料理を 皿分食べた。皿 の色は文字列 であった。 また、料理の価格は皿の色と対応し、各 について、色が文字列 の皿の料理は一皿 円である。 また、 のいずれとも異なる…
とても教育的な典型問題！ 問題へのリンク 問題概要 長さ の英小文字からなる文字列 が与えられる。 この文字列がすべて同じ文字で構成されているかどうかを判定せよ。 制約 考えたこと すべてが同じ文字だということは、「すべてが先頭の文字と同じ文字であ…
ビット全探索の典型問題！ 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…
いろんな方法が考えられる超典型問題 問題へのリンク 問題概要 長さ の整数数列 が与えられる。 この数列に含まれる整数の種類数を答えよ。 制約 解法 set 型の知識があれば、それを用いるのが最も楽だと思う (他の方法は公式解説を参照)。C++ の set 型を用…
「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…
しゃくとり法の基本！ 問題へのリンク 問題概要 個の整数 が与えられる。これらの整数から異なる 2 個を選ぶ方法のうち、2 個の値の差が 以下であるものの個数を求めよ。 制約 解法 (1)：しゃくとり法 鉄則本の問題なので、鉄則本を参照 #include <bits/stdc++.h> using nam</bits/stdc++.h>…
方程式を解くのに二分探索が使えることが多々ある！ 問題へのリンク 問題概要 正の整数 が与えられる。 を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。 制約 メモ editorial にとても解法が書いてある。 gith…
mod 998244353 の練習！ 問題へのリンク 問題概要 非負整数 が与えられる。 を 998244353 で割った余りを求めよ。 制約 考えたこと 「足し算・引き算・かけ算」をした計算結果を 998244353 で割った余りを求める方法論については、次の記事に詳しく書いた。 …
とても教育的な Greedy 問題！ 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…
二次元配列を二重 for 文で調べる最低ライン！ 問題へのリンク 問題概要 のグリッドにアルファベット文字が書かれたものが 2 つ () 与えられます。 これらは 1 箇所のみ異なっていることが保証されます。 であるような を答えてください。 制約 解法 (C++) …
二次元累積和！ 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…
いもす法！！ 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照！！ コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…
累積和をやって、その次にやる類題として、そりゃこれを出すよね！！ って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…
累積和に関する問題！！ 問題へのリンク 問題概要 日間にわたるイベントを開催し、日 には 人が来場した。次の 回のクエリに答えよ。 【クエリ】 各クエリでは が与えられるので、 日目から 日目までの間に合計何人が来場したかを答えよ。 制約 解法 累積和…
古き良き、ABS にも収録した問題！ 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…
古き良き、ABS にも入れた代表的問題。 問題へのリンク 問題概要 10000 円、5000 円、1000 円が合計 枚ある。 このとき、これらの合計金額が 円になることがありうるかどうかを判定し、ありうるならばそれを 1 つ答えよ。 制約 解法 次の記事に解法を書いて…
「十進法 → 二進法」変換。これも鉄則本公式解説とは異なる方法でやってみよう。 問題へのリンク editorial 問題概要 二進法で表記された整数 が与えられる。 整数 の十進法表記を求めよ。 解法 たとえば、二進法で表された整数 1101 は、十進法では、次のよ…
ここでは鉄則本に乗っているのとは異なる方法でやってみよう！ 問題へのリンク 問題概要 整数 が与えられる。 を二進法表記したものについて、先頭を 0 埋めすることで 10 桁で答えよ。 解法：二進法とは 整数 を二進法で表したときの各桁の値が求められれば…
二重 for 文の練習！ 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう！ コード #include <bits/stdc++.h> using na</bits/stdc++.h>…
線形探索法の基本問題！ 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です！ コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…
とても教育的な問題ですね。 問題へのリンク editorials 問題概要 0 以上 9 以下の整数からなる、 個の整数 が与えられる。 数列 の中に一度以上登場する整数を小さい順に出力せよ。 解法 (1)：値 0, 1, ..., 9 について個別に全探索 1 つめの解法は まず、…
for 文の練習をしよう！ 問題へのリンク editorial 問題概要 長さ の文字列 が与えられる。これらの文字列のハミング距離を求めよ。 ハミング距離とは、 となる の個数のことを指す。 解法 for 文の出番です。S[i] != T[i] であるような i の個数を求めれば…
の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう！ 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …
「集計処理」の基本問題！ 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…
