math/

README

Codeforcesのmathタグの問題

Last Change: 2020-09-12 22:12:59.

1354A

900、問題文を読み取るのが難しいだけ。

1355D ★

1400って嘘でしょ？

構築っぽさもある。

正当性の証明がゲキムズに見える。 リングバッファみたいなものと、その上での累積和から背理法で導ける。 リングバッファと累積和を想起するのは大事だが、厳密な証明はコンテスト中は厳しそう。 そこからは雰囲気で解きたい。

もう少し考えたら、

• リングバッファみたいなのを考えて循環する累積和（区間和）もOK
• 正の整数しか含まないので累積和は1つ伸びると必ず大きくなる
• 作れる区間和の種類に対してkの種類が足りずNOになる

みたいな感じで直感的にイメージするのがいいかもしれない。

1355C

1800だけどこっちのほうが上のやつよりはるかに簡単。 あんまり数学要素はない気がする。

三角形の成立条件はよく覚えておきたい。 三辺の大小関係がわからないと条件は「ある2つの辺の和が他よりも厳密に大きい（3つの不等式を調べる必要がある）」だけど、 最大辺がわかっている場合は1つの不等式だけを試せば良い。 競技ではよく使うことになりそう。

今回は x+y を固定して、条件を満たす z を数える、というのをすべての x+y に対して調べれば良い。 ここは二分探索を使ったが、別にしゃくとり法でもいけるし、多分もっと簡単な方法でも良い。

x+y の作り方のパターン数を求める部分はいもす法がいいと思う。 数学で都度 O(1) で求めることも出来るかもしれないが、自分にはよくわからない。

1354C1

1400。

なんとなく求めるものはわかったけど、それの求め方がわからなかったのでググったら公式が出てきた。

正多角形の辺心距離とかいうらしい。

1355A

1200。

コンテスト本番だったらはまって解けていなかったと思う。 ギャグに近くて、桁に0が現れると変化しなくなる。 そして冷静に考えると、たかだか81までしか増えないので、近い将来100の桁に0がでてくる。

1342C ★★

1600。

全くわからなかったので答えを見た。

まず、区間に関する個数を問われているため、 [0, r] がわかれば累積和の感覚で任意の区間について解答できることに注意。

x => a*b + x としても両辺とも変わらないため、 a*b で周期性があると考えることが出来る。 そのため、 a*b-1 までは所望の性質を満たすものについて真面目に調べて、後は周期性を利用して大まかに求め、 区間の端数部分は累積和で丁寧に求める。

結局、MODが与える周期性に気づき、それを利用する必要があるが、以下の点から気づきたかった。

• [l, r] がバカでかい割にクエリがめちゃくちゃ多いので、周期性から O(1) で各クエリに回答できる可能性がある
• そもそもMOD演算というのが周期性を与えるもの

1336B ★

1700。

ABCで似たようなものがあるが、これは真ん中にRGBの何を持ってくるかをすべて試す必要がある。 実装を簡易的にするために番兵を入れるが、回答するものが2乗和であることから何も考えずにやるとオーバーフローしてしまう。

自作のオーバーフローチェッカーを使って通したが、本番でやらないといけないとなると結構辛い。

全部の順序関係における、ある真ん中を固定したときの最小パターンだけを求めれば良い という部分がmath要素だと思う。

1334C

1600。

モンスターを全部倒すにあたり、すべての爆破は利用可能であることをイメージする。 すると、最初に倒すモンスター以外は後ろの爆撃を利用するのが最適で、 すべてのモンスターに対して爆撃を利用する場合に必要な残りの弾数というのを計算しておけばよい。 前計算を利用すると、すべてのモンスターを一番最初に倒した場合の弾数が求まるので、その最小を答えれば良い。

二分探索が必要かと思ったが、それすらいらずに O(N) で解ける問題だった。

1363A

1200。

0と1にエンコードした後ソートする。 ここから連続する x の区間和をすべて調べれば、可能かどうか判断できる。 なぜなら、 x 個のうち何個奇数を含めるかを1つずつ増やしながら検証できるから。

1334A

1200。

注意力コンテスト。気をつける部分が多い。

1338A

1500。

Difficultyの割に簡単だと思った。 2進数をイメージすると好きな数を好きなタイミングで足せる、というふうに考えることが出来るため、 結局最も差が大きくなるところに注目すれば良い。

1330B

1400。

前半と後半で順列になっているかどうかをチェックする。 前から見たときと後ろから見たときで、prefix or suffixが順列になっているかどうかを最初にチェックしておけば、 各境界で正しいかどうかを O(1) で検証できる。

多分実装の難しさでスコアが上がっている。

1329B ★

1700。

考察は直ぐにできたが、実装でバグらせまくってしまった。 確実で思考をバグらせにくい方法もぼんやりあとから浮かんだので、いつか復習したい。

1332D @2020-06-02

1700。

構築。わからなかったので解答をそのまま通した。 結果だけ見るとギャグっぽさがあるけど、制約とか結構絶妙で、システス通すのも本番だと結構大変な気がする。

「ジャッジはどうするんだろう？」とかは考えない。

---

ここからは math, number theory の2つのタグからフィルタリングしたものを解いていく。

1332B @2020-06-02

1400。

登場する素数が少ないことに着目する。 構築では座圧を使うとバグがでなくて良さそう。

1312C @2020-06-02

1400。

k進数になおして、全要素に渡って各桁の総和が2以上にならなければOK。

1305C ★★ @2020-06-02

1600。

わからなかったので答えを見たら、わからなかったことにめちゃくちゃ腹が立った。

鳩の巣原理が関係している。また、m のあまりが等しい2数の差は m の倍数、というのも必要。 n <= m なら真面目に計算すれば良い。 n > m なら必ずあまりが等しいものが2つ以上存在するので、答えは必ず0になる。

1294C @2020-06-03

1300。

考察はめちゃくちゃ簡単だけど a^2 * b^2 でもOKにできることを見落としており、1ペナと長時間を失った。

1285C @2020-06-03

1400。

x を素因数分解して、素数のまとまりを a, b のどちらかに寄せればよいが、 それに関してはbit全探索で愚直にやって良い。

なぜなら、素数を小さい順に20個程度かけ合わせた段階で 10^12 という制約はオーバーしてしまうことから、 必要なビットはたかだか20個以下で抑えられるため。

考察を進めて自力で解けたが、割と非直感的な事実だと思った。

1349A ★ @2020-06-03

1600。

本番で解けなくて解説ACしたのに全く覚えていなかった。 というか想定解法の O(NlogA[i]) は天才過ぎて無理だった。

すべてを素因数分解すると、少なくとも n-1 個がある素数を素因数として持っていれば、 それは最後のGCDで生き残れることがわかる。 また n 個ある場合は下から2番目の指数を採用していいことに注意（これを忘れて1WAしてしまった）。

この解法だと O(N * sqrt(A[i])) になってしまうが、TLが3secなあたり、これも想定されてそう。

1266C @2020-06-04

1400。

行列の構築だけど、難易度を事前にわかっているとだいぶ簡単。 基本的には貪欲に最小になるケースを作ることを考えればよいが、 r == 1 || c == 1 がコーナーっぽい振る舞いをするので、 それらについては例外的に処理してしまう。

1220B ★ @2020-06-05

1300って嘘でしょ？

全くわからなかったので解説ACしたが、よくよく行列を眺めてみると、いかなる場合でも A[0]*A[0] == M[0][1]*M[0][2]/M[1][2] が成り立つ。

平方根は二分探索で見つければ良い、というのは何気に新しい学びだった（線形探索でもギリギリ間に合ったが、危ない）。

1209B @2020-06-05

1300。

制約が小さいので難しいことを考えずに、いもす法でシミュレーションした。 もうちょっとdiff高く合ってほしい気がする。

1200C @2020-06-05

1400。

移動可能なグループに番号をつけて、始点と終点が同じグループに属していると判定できれば良い。 その判定のためには n, m の既約の比を求める必要があり、これはGCDが計算できれば良い。

ABCのイワシの問題とかの前に解いておきたくて、教育的だと思う。

1178D ★ @2020-06-05

1500マジ？解けなかったので解説ACした。

素数が絡むのでnumber theoryタグがついているが、グラフ構築の側面が強い。 とはいえ、 「素数は結構密に存在している、具体的には [n, n+n/2] の範囲には何かしら素数が含まれる」 というのは 知識として覚えておきたい。

後は、単純なグラフとして閉路グラフからスタートするのも、グラフ構築の一つのパターンだと思う。 それ以外はうにグラフとか。

1195D1 @2020-06-05

1500。Div2の後半ということでちょっと高めに出てそう。

Easyバージョンなので考察は簡単。 各桁ごとに分けて何回合計に寄与するかを考えれば良い。 実装が本番なので、こういうのはスムーズにやりたいが、Goだとめんどくさい。。

1184A1 @2020-06-05

1200。

方程式を解くのと、全探索範囲は小さいことに気づく必要がある。 簡単なのでもう少し早くときたかった。

1149A @2020-06-05

1200。

隣り合う素数間の距離は 2, 3 を除いてすべて偶数であるため、 [2, 1] と並べた後は、 すべての2を並べる→すべての1を並べる、で最適になる。

1165D @2020-06-05

1600。diffの割にはやることは簡単なあたり、pretestが激弱だった可能性がある。。

矛盾の検証は順方向も逆方向も直感的に出来る。 逆方向を一発目で忘れてしまい1WA。

1155C @2020-06-05

1300。ReadForces。読解の面倒くささが難易度を水増ししている。

イベント間の差分のGCDを計算し、それを割り切るものが選択肢にあればOK。

1143B @2020-06-05

1200。

変に桁DPをやってしまったが、これも怖いのでtutorial通りの xxx999..9 の形を全探索すべきだった。

1133D ★ @2020-06-06

1500。

これは良い問題だと思う。 有理数のハッシュに関して基礎的なところに閉じてるので、以前のABCのイワシの問題の前の事前知識としてピッタリ。

1133B @2020-06-06

1200。このDiffについては最悪飛ばしてしまっても問題はないかもしれない。

あまりに着目するのはすぐに分かるが、具体的にもとめられているものの量の計算部分は少し迷ってしまった。

1114C ★ @2020-06-06

1700だけど「考察は」自力で解けた。 ABC148-Eの発展バージョンと言う感じ。

基数を構成する素数に着目して考察を素直に進めていけばよいが、 n! の素数の数え上げ部分でオーバーフローを起こしてしまうケースでバグり散らかしてしまった。 サンプル観るまで気づけなかったので、おそらく本番は悔しい思いのまま死んでいったと思う。

この手のオーバーフローは常に警戒するようにしたい。 掛け算は自分の感覚よりも早くオーバーフローしてしまう。

1110C @2020-06-06

1500。1WAしたが、これならおそらく本番でも修正できたと思う。

すべてのビットが立っているときがめんどくさく、その場合は x+y == a を満たす x, y について Gcd(x, y) が答えとなる。 a を素因数分解して、最も小さい素因数を一つだけ弾いてやれば良い。

1091C ★ @2020-06-06

1400。エスパーは簡単だが証明も含めると難しい。

ベズーの定理を視覚的にイメージするためには良い問題だと思うので、証明も含めてちゃんと理解したい。

1056B @2020-06-06

1600。だけどそんなに難しくない気がする。

i % m がわかれば (i * i) % m もわかる。 すべてのマスについて余り別に個数を分けて数えておくと、 n <= 10^9 のもとでも効率的に数えることが出来る。

このような (i, m-i) であまりのペアを考えるのは頻出かもしれない。

1061C ★★ @2020-06-07

1700。

DPなんだけど、配列再利用が必須で、経験値が少なく難しかった。 とはいえ、考察を進めると実は遷移が思ったよりシンプルであったり、 その遷移も約数のみに対象を絞ったりして時間的にも効率化する部分は面白いので、 個人的にとても好きな問題。

1062B @2020-06-07

1500。自力で解けたけど3WA。

素因数分解するとやるべきことは見えてくる。 サンプルを実行してみて、基本はSQRTの操作回数にのみ注目すればいいことはわかるが、 掛け算の必要の有無を最初から意識していないと、無駄にWAを発生させてしまうことになる。

場合分けは複雑になりがちだが、一つずつ丁寧に潰していく意識でやりたい。

1076B @2020-06-07

1200。

一見無理そうに見えるが、 素数 - 素数 = 偶数 かつ偶数のときは簡単なので、約数列挙や素因数分解ができれば良い。

1068B @2020-06-07

1200。自力で解けたけどちょっと迷いが生じてしまった。

LCM(a, b) = a * b / GCD(a, b) という基本的な式変形をすると、聞かれている値は b / GCD(a, b) となる。 1 <= a <= 10^18 に対して 1 <= b <= 10^10 なので、聞かれている値は必ず b の約数をすべて網羅する。

992B ★ @2020-06-07

1600。tutorialは見ないで通したが、ペナルティで解けてないのと同値になった。

x * y == a * b となることはすぐに見えるが、このまま約数列挙するとTLEする。 よくよく考えると y == a' * b' * x (Gcd(a', b') == 1) というふうに変形できる。

ここからの数え上げでバグり散らかした。 y/x は必ず整数なので y/x == a' * b' まで変形しないとおかしなことになってしまう。

数え上げに持っていく際は極力シンプルに考えよう。 少なくともペナルティが出始めたら、一度立ち止まる必要がある。

900B @2020-06-08

1300。

有理数の筆算をシミュレーションする。結果的に循環小数を循環するまで試行する必要がある。

なんとなく「100000回繰り返せば大丈夫やろ」と気軽にやってACできたが、 その周期は実はたかだか b であることが鳩の巣原理で証明できるのは初めて知った。 簡単に言うと、あまりの数が b 種類しかないため（以前と同じ余りがでたら、同じ計算を繰り返すことになる）。

証明の参考URL

937B ★★ @2020-06-09

1400ってマジ？

以下のいわゆる「素数は意外と密に存在する」というやつだが、これはそのまま知識として仕入れてしまって良さそう。

the prime gap of numbers less than billion doesn't exceed 300 and we're gonna factorize no more than 300 numbers in total.

923A @2020-06-10

1700。自力。

一見めんどくさいが、逆から考えていくと理詰めできる。 自分はエラトステネスの篩を使ったが、解説をみると必要ないらしい。

870C ★ @2020-06-11

1300。自力だが好ましくない思考になってしまい、2WAしてしまった。

大きいときは4をできるだけ使うべき、あとは余りに対して場合分けする、 というふうに考えてしまったが、それがコーナーケースを生んでしまった。

tutorialにある通り、小さい部分（具体的には15以下で十分？実際には安全をとってもう少し幅をとっても良さそう） の解はDPで求める、というのが良さそう。

模範解答のコード

876B @2020-06-11

1300。自力。とても簡単。

2数の差が m の倍数であるためには、2数の m で割った余りが等しくなければならない。

891A @2020-06-13

1500。自力。

ちょっと考え込んだが、 n <= 2000 からメタ読みしてしまった。 1がない場合はどこかで1を作る必要があるので、その区間で長さが最小のものを見つける。 1を一つ作った後は、それを全要素に対して上書きするように操作すれば、回数がわかる。

840A @2020-06-13

1300とは何事？証明が全く理解できない。

kmjpさんの解説を見つけた。 ときにはエスパーに身を任せることも必要かもしれない。

並べ替え不等式（rearrangement inequality）というのは覚えておいたほうが良いかもしれない。

※適当にソートしたら1000msec超えたので、こどふぉではなるべく定数倍も落としたほうが良い。

817A @2020-06-14

1200。易しめ。

x を変位させずに 2*y 変位させられる、というのに気づくと、あとはトントン拍子で進む。 とはいえ、ところどころ自信が持てず、解くスピードは微妙だった。

787A ★ @2020-06-14

1200。

全探索すればいいっていうのは何となく分かるけど、なぜ範囲が小さくて十分かがわからない。。

833A @2020-06-15

1700。考察は自力で完ぺきにできた。

両者に掛け合わされる値を一箇所に集めると、必ず k^3 になるという点に注目すると、 まず a*b の立方根が整数である必要がある。

そして a, b はともに立方根 c で割り切れる必要がある。 なぜなら、 c で割ったときの数値が、勝利によって得られた係数 k であるといえるから。

と思ったら、 n = 350000 の出力行数が多すぎてそこがネックとなりTLEしてしまった（TLが1secと短いこともあるけど）。

立方根を整数の範囲で求めようとすると二分探索するのが自然だと思うが、以下のsubmissionは参考にしたい。

	cbrt := func(a int64) int64 {
		r := int64(math.Round(math.Cbrt(float64(a))))
		if r*r*r == a {
			return r
		}
		return -1
	}

• 参考1
• 参考2

762A @2020-06-16

1400。やるだけ。

普通に O(sqrt(n)) の約数列挙が間に合う制約。 ソートして大丈夫か不安になるが、約数の個数はそんなに大きくはならないはず（高度合成数とかが関係してくる？）。

757B @2020-06-16

1400。ほぼやるだけ。

全部素因数分解してよいので、素数ごとにインクリメントして最大を取れば良い。

743C ★ @2020-06-16

1500。わからず解説AC。

2/n = 1/n + 1/n の方針は合っていたが、そこから進まなかった。

有理数の構築？ではよくある発想なんだろうか。。

742B @2020-06-16

1500。自力。

zero sum rangesの要領でやればよいが、ちょっと頭がこんがらがる。 C(n, 2) を加算して求めるやり方はちょっとイメージできないぐらいにはややこしく、 自分は前から重複を数えないようにデクリメントしながら加算するやり方を採用した。

735D ★★ @2020-06-16

1600。大きい素数に貪欲に分割すればいいと思ったが、早々とWAが出て散った。

ゴールドバッハの予想という知識が必須っぽい。

これは「すべての3より大きい 偶数 は2つの素数の和として表される」という予想で、 4 * 10^18 というところまでは正しいことが証明されている。

なので、与えられた n が、素数なら1、偶数なら2までは確定する。

では、3より大きい奇数についてはどうなるかだが、これも簡単に考察できる。 まず n-2 が素数ならば (n-2, 2) になって答えは2となる。

一方で、 (n-i, i) の両方が素数となるものはこれ以外にない。 なぜなら、 n は今奇数であるため、それぞれの偶奇は異なる。 すると、どうあがいても偶数となったほうをさらに分割する必要があり、答えは3以上となる。 しかしながら (n-3, 3) と分割してしまえば、 n-3 は偶数かつゴールドバッハの予想により2つの素数に分割されるため、 答え3を達成できる。

707C ★★ @2020-06-17

1500。全くわからず解説AC。

n を最大の辺ではないと仮定すると n^2 = (a + b) * (a - b) の積の形に持ち込める。 ここからは偶奇性に注意しながら構築っぽく考えると、 O(1) で答えが導ける。

678D ★ @2020-06-17

1700。ペナ出しまくったけど自力。

行列累乗。 自分は基本に従って（？）3項間の漸化式にしてから立式して解いたが、 負の数が絡むため、剰余の計算がややこしかった。 最初の行列の段階で正の数にしてしまえば、負の数の問題が発生する余地はなくなる。

※tutorialのもっと簡単な行列の立式がよくわからなかった。。また時間が経ってから見直したい。

678C @2020-06-17

1600。自力。

何もハマりどころがなかった。 古すぎてDifficultyがおかしくなっている気がするので、700より古い問題はとりあえず避けて良さそう。

1370C @2020-06-26

1400。自力。

ゲーム系かつ整数問題だが、詰めていくのはかなり簡単。

場合分けが多いので丁寧に。 簡単な条件から早期returnを活用してバグらないように注意する。

1372B @2020-09-12

1300。軽くエスパーした。

証明読んだが結構長いし、むずい。