数学(整数問題)
というコーナーケースにやられた！ 問題へのリンク 問題概要 整数 が与えられる。 を で割った余りの一の位の値を求めよ。 (マルチテストケース) 制約 考えたこと まず最初に考えたのは「全体を で割った世界」で考えれば良いということ。 このことを正当化…
for 文を用いるのが楽だと思う。 問題へのリンク 問題概要 以上 以下の の倍数が存在するならば 1 つ求め、存在しない場合は -1 を出力せよ。 制約 考えたこと for 文を用いるのが最も楽だと思う。 について、 で割り切れるかどうかを判定していき、 割り切…
とても教育的な問題！ 問題へのリンク 問題概要 整数 が与えられる。 以上 以下の整数は何個あるか？ 解法 まず、 の場合は、 以上 以下の整数は存在しないことに注意しよう。この場合は 0 個と答えれば良い。 それでは、 としよう。この場合は、 以上 以下…
偶数か奇数かを判定する問題！ 問題へのリンク 問題概要 高橋君の今日の状態は "White" である。 毎日 "White" と "Black" が入れ替わる。 日後の状態を答えよ。 解法 が偶数ならば、"White" が奇数ならば、"Black" である。 #include <bits/stdc++.h> using namespace std;</bits/stdc++.h>…
ちょっと一見面倒な問題。 問題へのリンク 問題概要 999 以下の正の整数 が与えられる。 解法 の一の位の値は N % 10 で取得できる。この値を調べればよい。 ここで、コツとして、if-else 文の最後の else のところが最も面倒なものが来るようにしよう。ここ…
色んな解法がある！ この手の数値的なものに対して「全探索」という解法を選択肢に持てるようにしていこう。 問題へのリンク 問題概要 3 個の正の整数 が与えられる。次の条件を満たす整数が存在するかどうかを判定せよ。 の倍数である 以上 以下である 制約…
nC2 系の問題は ABC-D などで頻出だが、その練習ができる問題！ 問題へのリンク 問題概要 偶数の書かれたボールが 個 奇数の書かれたボールが 個 あります。これら 個のボールから 2 個選んで、書かれた数の和をとります。 この和が偶数になるような選び方は…
いい感じの複合問題。この時期の ABC-A としては少し難しめ。 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数をランダムに選ぶとき、それが奇数である確率を求めよ。 解法 以上 以下の 個の整数のうち、奇数の個数を とすると、求める確…
という表現が何を言っているんだ......と戸惑うかもしれない。これは、要は「ちょうど 秒後」も含むよということを言っている。 問題へのリンク 問題概要 ビスケット起動装置を起動してから、 秒後にそれぞれビスケットを 枚生成する。 起動してから 秒間の…
天才構築ゲー。これ完全自力で一発 AC できて嬉しかった！！ 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
面白かった！ 問題へのリンク 問題概要 以上の整数 と非負整数 が与えられる。 の正の約数の総積が で最大何回割れるかを 998244353 で割った余りで求めよ。 制約 考えたこと 一般に、2 以上の整数 の正の約数の総積は、 の約数の個数を とすると となる。た…
パリティの問題。ここのところ、算数や数学の問題が続いている。 問題へのリンク 問題概要 1 以上 3 以下の整数 が与えられる。 が奇数 となるような 1 以上 3 以下の整数 が存在するかどうかを判定せよ。 解法 一般に、かけ算をするとき 偶数が 1 個でも含…
分配に関する面白い問題！ 問題へのリンク 問題概要 枚のせんべいを 人に配る。 「最も多くのせんべいをもらった人」と「最も少ないせんべいをもらった人」の、もらったせんべいの個数の差を求めよ。 解法 もし、 が で割り切れるならば、全員に公平に分配で…
整数問題！ 問題へのリンク 問題概要 整数 が与えられる。 と の最小公倍数を求めよ。 解法 一般に最小公倍数を求める方法としてはユークリッドの互助法が知られている。しかし、今回は次のように簡単に考えられる。 が 2 の倍数のとき：最小公倍数は が 2 …
この問題を思い出した！ 問題へのリンク 問題概要 素数 と、 個の 1 以上 以下の整数 が与えられる。 を満たす整数 が存在するような の組の個数を数え上げよ。 制約 考えたこと 一瞬、原始根を考えたくなったが、原始根ではなく「位数」を考えた方が計算量…
「切り上げ処理」を要求する問題！ 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 の平均値を求め、小数点以下を切り上げて得られる整数値を答えよ。 解法 が偶数ならば、平均値は整数であって、答えは (a + b) / 2 となる が奇数ならば、平均値は…
整数値のままでも解けるし、文字列として受け取って解いてもいい。 問題へのリンク 問題概要 2 桁の整数 が与えられる。 が '9' を含むかどうかを判定せよ。 解法 を整数値で処理する場合は 一の位は N % 10 十の位は N / 10 で求められる。これを利用して判…
3 桁の整数で前から順に である数の表し方は中2で習う内容でもある。 問題へのリンク 問題概要 と書かれた 3 枚のカードをこの順に並べて得られる 3 桁の整数が 4 の倍数であるかどうかを判定せよ。 解法 3 桁の整数で前から順に である数は、 と書ける。 こ…
最小公倍数を求める。その際にはオーバーフローに注意！ 問題へのリンク 問題概要 正の整数 が与えられる。 の最小公倍数を求めよ。ただし、 を超える場合は "Large" と出力せよ。 制約 解法：最大公約数から最小公倍数を求める まず、整数 の最大公約数を …
この処理は今後めっちゃ頻出なので、スラスラ書けるようになっておきたい！ 問題へのリンク 問題概要 正の整数 が与えられる。 に最も近い 5 の倍数を求めよ。 解法 たとえば としてみよう。5 の倍数は 0, 5, 10, 15, 20, 25, 30, 35, 40, ... と続いていく…
整数 が 326-like 数かどうかを判定する処理が書ければ、この問題は解ける。 問題へのリンク 問題概要 整数 が 326-like 数であるとは、3 桁の正の整数であって、百の位と十の位の積が一の位に等しいことをいう。 与えられた整数 以上の、最小の 326-like 数…
for 文の練習 問題へのリンク 問題概要 正の整数 が与えられる。 の値を求めよ。 コード とは、 を 回かけた値である。よって、次のように for 文で求められる。 long long res = 1; for (int i = 0; i < B; ++i) { // A をかける操作を B 回行う res *= A; …
数学的な問題。 問題へのリンク 問題概要 正の整数 が与えられる。0 以上の整数 であって、 となるものが存在するかどうかを判定せよ。 制約 考えたこと 問題を解くときに、条件をわかりやすく言い換えていくことはとても大事！ 今回は次のように考えるとわ…
大好き！！ガウス整数の問題リストがまた 1 個増えた！ 問題へのリンク 問題概要 1 つの正の整数 が与えられる。 二次元平面上の任意の格子点を頂点としたグラフにおいて、距離の平方が であるような 2 点間に辺を張っていく。 こうしてできたグラフの連結成…
久しぶりの、再帰関数を書きたくなるタイプの全探索！ 問題へのリンク 問題概要 各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。 番目の 321-like 数を求めよ。 制約 321-like 数の個数 解法 (1)：異常 10 重 for 文 この解法は本当に根性で…
モノグサ社内で同僚と一緒に解いた！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…
整数の入門にいい感じの問題！ 問題へのリンク 問題概要 正の整数 と非負整数 が与えられる。次の条件を満たす正の整数 の個数を求めよ。 を で割った余りが である 制約 解法 を で割ったときの商を とおくと、 と表せる。これを式変形すると となる。この…
平衡三進法！ 問題へのリンク 問題概要 次の条件を満たすサイズ 9 の整数列 を求めよ。 である 以上 以下の任意の整数 に対して、次の操作を繰り返す操作列が存在して、整数列中に整数 が存在する状態にできる 操作 1：数列から 2 つの要素 を選び、その 2 …
また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張…
