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

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

算数と数学

AtCoder ABC 356 D - Masked Popcount (1Q, 緑色, 400 点)

すごく教育的問題! 問題へのリンク 問題概要 非負整数 が与えられるので、次の値を 998244353 で割った余りを求めよ。 & 制約 考えたこと この手の問題は「主客転倒」して、上記の総和を各桁ごとに考えればよいと相場が決まっている!!! 具体的には、次の…

鉄則本 B12 - Equation (3Q, ★4)

方程式を解くのに二分探索が使えることが多々ある! 問題へのリンク 問題概要 正の整数 が与えられる。 を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。 制約 メモ editorial にとても解法が書いてある。 gith…

AtCoder ABC 355 A - Who Ate the Cake? (7Q, 灰色, 100 点)

ちょっと算数チックな問題 問題へのリンク 問題概要 人 1, 2, 3 が容疑者に挙げられている。次の証言がある。 「人 は犯人ではない」 「人 は犯人ではない」 犯人を特定できるかどうかを判定し、特定できるならば犯人を答えよ。 制約 は 1, 2, 3 のいずれか …

AtCoder ABC 048 B - Between a and b ... (5Q, 灰色, 200 点)

制約が と大きいので、ちゃんと整数論的処理をしないといけない! 問題へのリンク 問題概要 以上 以下の整数のうち、 の倍数は何個あるか? 制約 考えたこと 制約が と極めて大きいので探索手法で解くことは難しい。数学的に求めることを考える。 まず、「 …

AtCoder ABC 265 A - Apple (7Q, 灰色, 100 点)

ちょっと頭を使う系の問題。この時期の ABC-A にはこういうものが多かったね。 問題へのリンク 問題概要 りんごをちょうど 個買いたい 円払って 個買う 円払って 個買う のいずれかによって、ちょうど 個買うための最小コストを求めよ。 解法 以下のいずれか…

AtCoder ABC 207 B - Hydrate (5Q, 灰色, 200 点)

これ結構難しい! 数式を丁寧に立てよう。 問題へのリンク 問題概要 箱に水色のボールが 個入っている。 「箱に 個の水色のボールと、 個の赤色のボールを入れる」という操作を繰り返すことで、赤色のボールの個数が水色のボールの個数の 倍以上となるように…

AtCoder ABC 205 C - POW (5Q, 灰色, 300 点)

愚直に や を求めようとすると、色んな理由でおかしくなってしまう。数学的に綺麗に処理しよう! 問題へのリンク 問題概要 整数 が与えられる。 と の大小関係を求めよ (大きい、小さい、等しい)。 制約 考えたこと や はまともに計算するとものすごい桁数に…

JOI 一次予選 2022 (第 2 回) A - 立方体 (10Q, 難易度 1)

このくらい易しい問題はとてもいい! 問題へのリンク editorial 問題概要 一辺の長さが である立方体の体積を求めよ。 解法 求める体積は である。 よって、整数値 X の入力を受け取り、X * X * X の値を出力すればよい。 コード #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

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

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

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

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

JOI 一次予選 2023 (第 2 回) A - 時間 (10Q, 難易度 1)

「1 日 = 24 時間」ですね。 問題へのリンク editorial 問題概要 日とは、何時間であるか求めよ。 解法 1 日は 24 時間であり、2 日は 48 時間であり、3 日は 72 時間である。このように、日数に 24 をかけることで、時間数を求めることができる。 よって、 …

鉄則本 A01 - The First Problem (10Q, ★1)

鉄則本の最初の問題! 問題へのリンク 問題概要 一辺の長さが であるような正方形の面積を求めよ。 解法 求める正方形の面積は ですね。 よって、整数値 N の値を標準入力で受け取って、N * N の値を標準出力すればよいでしょう。 コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

AtCoder ABC 352 A - AtCoder Line (7Q, 灰色, 100 点)

算数系の問題! 問題へのリンク 問題概要 解法 入力の中に が含まれるが、これは結局使わない。こういう変数に惑わされないようにしよう。次の 2 つの場合に分けて考える。 のとき (上りのとき) のとき (下りのとき) 前者の場合は、"Yes" となる条件は と書…

JOI 一次予選 2024 (第 2 回) B - 火曜日 (8Q, 難易度 1)

慣れていないと少し難しいかもしれない。 問題へのリンク editorial 問題概要 今日は日曜日である。 今日の 日後が火曜日であるならば 1 を、そうでないならば 0 を出力せよ。 解法 日後が火曜日であるための条件を考えましょう。 「0 日後は日曜日」「1 日…

JOI 一次予選 2024 (第 2 回) A - 飴の袋詰め (9Q, 難易度 1)

例によって、一次予選の A 問題は教育的! 問題へのリンク editorials 問題概要 1 個 円の飴を 個と、 円の袋を 1 つ買う。 合計金額はいくらか求めよ。 解法 答えは です。 プログラムでは、整数値 A, B, C を標準入力で受け取って、整数値 A * B + C を標…

JOI 一次予選 2024 (第 1 回) B - 和の判定 (8Q, 難易度 1)

上手に場合分けしよう! 問題へのリンク editorial 問題概要 3 個の整数 が与えられる。 これらのうちの 1 個が、残りの 2 個の和として表せるときは 1 を出力し、そうでないときは 0 を出力せよ。 解法 「3 個の整数 のうちの 1 個」が残りの 2 個の和とし…

AtCoder ABC 228 A - On and Off (6Q, 灰色, 100 点)

これは結構大変! 問題へのリンク 問題概要 高橋君は、毎日 時 0 分に部屋の電気を点け、 時 0 分に部屋の電気を消す。電気をつけている間に日付が変わることもある。 時 30 分に部屋の電気がついているかどうかを判定せよ。 解法 これは整理するのが大変だ…

AtCoder ABC 227 A - Last Card (7Q, 灰色, 100 点)

これは難しいですね。何も考えずに for 文で求めるのが比較的楽でしょうか。 問題へのリンク 問題概要 と番号のついた 人に、 枚のカードを配っていく。 人 から始めて、人 の順に 1 枚ずつカードを配るとき、最後のカードは誰に配られるでしょうか? 解法 1…

AtCoder ABC 225 A - Distinct Strings (7Q, 灰色, 100 点)

これ結構難しいと思う! 数学 IA の「場合の数」をやると、よく出て来るやつですね。 問題へのリンク 問題概要 英小文字のみからなる長さ 3 の文字列 が与えられます。 の各文字を並び替えて得られる文字列は、何種類ありますか? 解法 「3 個のものを並び替…

AtCoder ABC 223 A - Exact Price (8Q, 灰色, 100 点)

えぐいコーナーケースに注意! でもサンプルにあるね。 問題へのリンク 問題概要 財布に 円玉が 1 枚以上入っています。 財布に入っている合計金額がちょうど 円であるようなことが、あり得るかどうかを判定してください。 制約 考えたこと 基本的には「 が …

AtCoder ABC 221 A - Seismic magnitude scales (灰色, 100 点)

for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 マグニチュード の地震は、マグニチュード の地震の何倍の強さか? (1 上がると 32 倍となる) 制約 解法 を 回かけた値を求めればよい (つまり )。 これを求めるためには、関数 pow() を用いるか、f…

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

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

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

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

AtCoder ABC 206 A - Maxi-Buying (灰色, 100 点)

出力がややこしい...... 問題へのリンク 問題概要 税抜価格が 円の品物に対して、消費税 8% を乗せた税込価格と 206 円との大小比較をせよ。 (出力形式はリンク先から) 解法 税込価格は (int)(1.08 * N) で求めることができる。 #include <bits/stdc++.h> using namespace s</bits/stdc++.h>…

AtCoder ABC 205 A - kcal (9Q, 灰色, 100 点)

算数ではよくある「比」の問題 問題へのリンク 問題概要 100mL あたり kcal のドリンクがある。 mL で何 kcal でしょうか? 解法 求めるカロリーを kcal とする。比で表すと、次のようになる。 内項の積と外項の積は等しいから、 よって、 と求められる。 今…

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

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

AtCoder ABC 202 A - Three Dice (灰色, 100 点)

算数! 問題へのリンク 問題概要 サイコロの 6 面のうち、3 面の数 が見えている。 隠れている残り 3 面の数の和を求めよ。 解法 6 面の数の和は なので、これから を引けばよい。 #include <bits/stdc++.h> using namespace std; int main() { int a, b, c; cin >> a >> b </bits/stdc++.h>…

AtCoder ABC 200 A - Century (灰色, 100 点)

切り上げ処理の問題! 問題へのリンク 問題概要 西暦 年は何世紀ですか? 解法 のとき、2 世紀 のとき、21 世紀 というように、 を 100 で割ったときの余りを切り上げたものが答えとなる。 これは、(N + 100 - 1) / 100 によって求められる (ここがピンと来…

AtCoder ABC 199 A - Square Inequality (灰色, 100 点)

不等式を頑張って実装! 問題へのリンク 問題概要 3 個の整数 が与えられる。 であるかどうかを判定せよ。 解法 if (A * A + B * B < C * C) によって判定できる。 #include <bits/stdc++.h> using namespace std; int main() { int A, B, C; cin >> A >> B >> C; if (A * A</bits/stdc++.h>…

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

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