数学(整数問題)
問題文を読み解くのが少し大変だった。 問題へのリンク 問題概要 2 つの整数 が与えられる。 、、 のいずれかが、3 で割り切れるかどうかを判定せよ。 解法 と と のいずれかが 3 で割り切れるかどうかを、or を表す演算子「||」を用いて調べれば OK。 #incl…
3 桁の整数で前から順に である数の表し方は中2で習う内容でもある。 問題へのリンク 問題概要 と書かれた 3 枚のカードをこの順に並べて得られる 3 桁の整数が 4 の倍数であるかどうかを判定せよ。 解法 3 桁の整数で前から順に である数は、 と書ける。 こ…
24 時制の問題 問題へのリンク 問題概要 24 時制で 時から 時間後の時刻を 24 時制で表したものを求めよ。 解法 基本的には を計算すればよい。もし 24 を超えたら 24 を引けばよい。 あるいは、剰余演算子「%」を用いて (A + B) % 24 を求めてもよい。 #inc…
最小公倍数を求める。その際にはオーバーフローに注意！ 問題へのリンク 問題概要 正の整数 が与えられる。 の最小公倍数を求めよ。ただし、 を超える場合は "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 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張…
2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…
Miller-Rabin 法や、モンゴメリ乗算を試せる問題ですね！ 問題へのリンク 問題概要 クエリが 個与えられる。 各クエリでは正整数 が与えられるので、素数かどうか判定せよ。 制約 解法 Miller-Rabin 法が使える。次のようなアルゴリズムである。 のとき：素…
ミラー・ラビンの素数判定法は、その背景にある整数論的考察もめっちゃ面白いので、ぜひそれも味わいましょう！！ 1. はじめに 本記事では正の整数 が与えられたときに、 が素数であるか否かを判定する問題を考えます。 よく知られた方法は、 を で順に試し…
これ、一見すると の計算量が必要に思えてしまうね！ 問題へのリンク 問題概要 正の整数 が与えられる。 かつ であるような正の整数の組 の個数を求めよ。 制約 の範囲を絞る 約数列挙アルゴリズムなどでもお馴染みの、大小関係から整数の範囲を絞って探索す…
なんかユーザー解説の数がすごいことになっててビビる！ 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…
これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…
「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…
これ系は好き！ これに近いのを ABC-D で最近よく見かける気がする。 問題へのリンク 問題概要 整数 が与えられる。 3 つの整数の組 であって、 がすべて 以下であるようなものの個数を 998244353 で割ったあまりを求めよ。 ケース与えられる。 制約 考えた…
ほどよい全探索問題！ 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！ 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか？ 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
面白かった 問題へのリンク 問題概要 以下の素数のみを素因数に持つ正整数を -smooth number と呼ぶ。 整数 および 、100 以下の素数 が与えられるので、 以下の -smooth number の個数を求めよ。 制約 考えたこと コンテスト中には、愚直 DFS を頑張って通…
上手に整理すれば、とてもシンプルな問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 を で割った商 を で割ったあまりを求めよ。 制約 考えたこと で割るような操作を 2 回しているので、 を で割った余りを考えるとよいのだろうなというあたりを…
floor sum のいい感じの練習問題！ 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…
floor sum と聞いて！！ 問題へのリンク 問題概要 以上 以下の整数のうち、 で割って 余るものを考える。そのような整数の popcount 値の総和を求めよ。 ( ケース与えられる) 制約 考えたこと TL を見て、floor sum と知った上での考察。 「popcount の総和…
レピュニット数を題材とした問題。 問題へのリンク 問題概要 を 個並べた数と、 を 個並べた数の最小公倍数を で割ったあまりを求めよ。 制約 考えたこと を並べた数をレピュニット数とよぶ。数学的に面白い性質が色々ある。 レピュニット数の最大公約数は、…
色々な考え方ができる楽しい問題ですね！ 3 通りの解法を自分なりに咀嚼して整理しました。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が の倍数となるような最小の整数 を求めよ。 制約 考えること：まずは素因数分解 この問題のように、「倍数…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
