けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

そのまま覚えたい易しい教育的典型問題

AtCoder ABC 351 B - Spot the Difference (7Q, 灰色, 200 点)

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

鉄則本 A08 - Two Dimensional Sum (2Q, ★4)

二次元累積和! 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…

鉄則本 A07 - Event Attendance (3Q, ★3)

いもす法!! 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照!! コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…

鉄則本 B06 - Lottery (4Q, ★2)

累積和をやって、その次にやる類題として、そりゃこれを出すよね!! って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…

鉄則本 A06 - How Many Guests? (4Q, ★2)

累積和に関する問題!! 問題へのリンク 問題概要 日間にわたるイベントを開催し、日 には 人が来場した。次の 回のクエリに答えよ。 【クエリ】 各クエリでは が与えられるので、 日目から 日目までの間に合計何人が来場したかを答えよ。 制約 解法 累積和…

AtCoder ABC 085 B - Kagami Mochi (6Q, 灰色, 200 点)

古き良き、ABS にも収録した問題! 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…

AtCoder ABC 085 C - Otoshidama (5Q, 茶色, 300 点)

古き良き、ABS にも入れた代表的問題。 問題へのリンク 問題概要 10000 円、5000 円、1000 円が合計 枚ある。 このとき、これらの合計金額が 円になることがありうるかどうかを判定し、ありうるならばそれを 1 つ答えよ。 制約 解法 次の記事に解法を書いて…

鉄則本 B04 - Binary Representation 2 (6Q, ★2)

「十進法 → 二進法」変換。これも鉄則本公式解説とは異なる方法でやってみよう。 問題へのリンク editorial 問題概要 二進法で表記された整数 が与えられる。 整数 の十進法表記を求めよ。 解法 たとえば、二進法で表された整数 1101 は、十進法では、次のよ…

鉄則本 A04 - Binary Representation 1 (6Q, ★2)

ここでは鉄則本に乗っているのとは異なる方法でやってみよう! 問題へのリンク 問題概要 整数 が与えられる。 を二進法表記したものについて、先頭を 0 埋めすることで 10 桁で答えよ。 解法:二進法とは 整数 を二進法で表したときの各桁の値が求められれば…

鉄則本 A03 - Two Cards (7Q, ★1)

二重 for 文の練習! 鉄則本の例題なので解法はメモ程度に。 問題へのリンク 問題概要 2 つの数列 と が与えられる。 これらから要素を 1 つずつ選び、和が となるようにすることが可能か判定せよ。 メモ 二重の for 文を使おう! コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

鉄則本 A02 - Linear Search (8Q, ★1)

線形探索法の基本問題! 鉄則本の問題なので、解法はメモ程度に。 問題へのリンク 問題概要 個の整数 の中に、整数 が含まれるかどうかを判定せよ。 メモ for を使った全探索です! コード #include <bits/stdc++.h> using namespace std; int main() { // 入力 int N, X; c</bits/stdc++.h>…

JOI 一次予選 2024 (第 1 回) D - 現れている数字 (6Q, 難易度 2)

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

JOI 一次予選 2024 (第 1 回) C - ハミング距離 (8Q, 難易度 2)

for 文の練習をしよう! 問題へのリンク editorial 問題概要 長さ の文字列 が与えられる。これらの文字列のハミング距離を求めよ。 ハミング距離とは、 となる の個数のことを指す。 解法 for 文の出番です。S[i] != T[i] であるような i の個数を求めれば…

AtCoder ABC 350 C - Sort (3Q, 灰色, 300 点)

の計算量で良いなら簡単。 「どこに値 の要素があるのか」を管理するというテクニックをここで習得しよう! 問題へのリンク 問題概要 の並び替えである順列 が与えられる。これをソートしたい。以下の操作を 回まで実施できる。 を選んで、 と を swap する …

AtCoder ABC 350 B - Dentist Aoki (6Q, 灰色, 200 点)

「集計処理」の基本問題! 問題へのリンク 問題概要 (意訳) 個の LED が最初はすべて光っている。 回の処理を行う。 回目の処理では 番目の LED の状態を flip する (光っていたら消して、消えていたら光らせる)。 最終的に何個の LED が光っているかを求め…

AtCoder ABC 217 A - Lexicographic Order (灰色, 100 点)

辞書順という言葉は聞きなれないかもしれないが、ここでマスターしよう! 問題へのリンク 問題概要 文字列 が与えられる。 が よりも辞書順で小さいならば "Yes" を出力し、そうでなければ "No" を出力せよ。 解法 辞書順とは、その名の通り「辞書に出てくる…

AtCoder ABC 209 A - Counting (灰色, 100 点)

とても教育的な問題! 問題へのリンク 問題概要 整数 が与えられる。 以上 以下の整数は何個あるか? 解法 まず、 の場合は、 以上 以下の整数は存在しないことに注意しよう。この場合は 0 個と答えれば良い。 それでは、 としよう。この場合は、 以上 以下…

AtCoder ABC 208 A - Rolling Dice (灰色, 100 点)

「この数からこの数の間の数はすべて作れる」という考え方をする問題。この考え方は、より高度な問題では頻出! 問題へのリンク 問題概要 1〜6 の目が出るサイコロを 回振った。 出た目の総和が になることがありうるかどうかを判定せよ。 解法 これは難しい…

AtCoder ABC 204 A - Rock-paper-scissors (灰色, 100 点)

ジャンケンの問題。何気に将来非常によく出てくる構造を問う問題でもある。 問題へのリンク 問題概要 3 人でジャンケンをしたらあいこになった。3 人のうちの 2 人の出した手がわかっている。残り 1 人の手を答えよ。 なお、0 はグー、1 はチョキ、2 はパー…

AtCoder ABC 198 A - Div (灰色, 100 点)

実はすごく簡単なのだが、戸惑うかもしれない。 問題へのリンク 問題概要 個のものを A 君と B 君で分け合う。 A 君も B 君も 1 個以上もらうようにするとき、分け方は何通りあるか? 解法 次の 通りある。 A 君: 個、B 君: 個 A 君: 個、B 君: 個 ... A…

AtCoder ABC 196 A - Difference Max (灰色, 100 点)

頑張って頭を整理しよう! 問題へのリンク 問題概要 整数 が与えられる。 , となるように整数 を選ぶとき、 の最大値を求めよ。 解法 を最大にするためには、 を最大にする を最小にする ようにすればよい。よって、 , のときに は最大であり、最大値は であ…

AtCoder ABC 195 A - Health M Death (灰色, 100 点)

これは簡単! 剰余演算子「%」を確認しよう! 問題へのリンク 問題概要 2 個の整数 が与えられる。 が の倍数であるかどうかを判定せよ。 解法 が の倍数であるとは、 を で割った余りが 0 であるということです。 を で割った余りは H % M と書けます。 以…

AtCoder ABC 186 A - Brick (灰色, 100 点)

割り算の練習! 問題へのリンク 問題概要 トラックには合計で キログラム以下の荷物を載せることができます。 このトラックに、1 個 キログラムのレンガを最大でいくつ載せることができますか? 解法 中学 1 年生の数学「文字と式」を習うときの気持ちを思い…

AtCoder ABC 181 A - Heavy Rotation (灰色, 100 点)

偶数か奇数かを判定する問題! 問題へのリンク 問題概要 高橋君の今日の状態は "White" である。 毎日 "White" と "Black" が入れ替わる。 日後の状態を答えよ。 解法 が偶数ならば、"White" が奇数ならば、"Black" である。 #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…

AtCoder ABC 176 A - Takoyaki (灰色, 100 点)

この手の「切り上げ処理」は、もう憶えてしまおう! 問題へのリンク 問題概要 個のたこ焼きを作りたい。 たこやきを作り始めてから、 秒おきに 個のたこ焼きを作る。 個のたこ焼きを作り切るのに最低何秒かかるか。 解法 たこやきを生産する回数は、次のよう…

AtCoder ABC 159 A - The Number of Even Pairs (灰色, 100 点)

nC2 系の問題は ABC-D などで頻出だが、その練習ができる問題! 問題へのリンク 問題概要 偶数の書かれたボールが 個 奇数の書かれたボールが 個 あります。これら 個のボールから 2 個選んで、書かれた数の和をとります。 この和が偶数になるような選び方は…

AtCoder ABC 157 A - Duplex Printing (灰色, 100 点)

この切り上げ処理はぜひ憶えておこう! 問題へのリンク 問題概要 高橋君は、全 ページから成る書類を両面印刷する。両面印刷では、1 枚の紙に 2 ページ分のデータを印刷することができる。 最小で何枚の紙が必要か求めよ。 解法 が偶数のときは、 は 2 で割…

AtCoder ABC 153 A - Serval vs Monster (灰色, 100 点)

これはとても教育的な問題!! 問題へのリンク 問題概要 HP が であるモンスターとサーバルは戦っている。 1 回の攻撃で HP を だけ減らすことができる。HP が 0 以下になるのに必要な攻撃回数を求めよ。 解法 (1) を で割ったときに、余りがあるならば追加…

AtCoder ABC 148 A - Round One (灰色, 100 点)

発想ゲー。 問題へのリンク 問題概要 1, 2, 3 のうちの 2 つの整数 が与えられる。 残りの整数を答えよ。 解法 色んな解法が考えられる。 の値で場合分けして解くこともできる。 しかし、最も簡単なのは、合計値が なのだから、そこから と を引く方法であろ…

AtCoder ABC 147 A - Blackjack (灰色, 100 点)

if 文の練習。こういう現実のゲームを題材とした問題は面白いね! 問題へのリンク 問題概要 以上 以下の 3 個の整数が与えられる。 これらの整数の総和が 22 以上ならば "bust"、そうでなければ "win" を出力せよ。 解法 3 個の整数を受け取って、総和が 22 …