srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

数学

yukicoder No.492 IOI数列

問題 問題概要 a1 = 1, ai = 100ai-1 + 1という数列がある. 第N項を1000000007と101010101010101010101で割ったあまりを求める. 解法 前半の解 数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けな…

SRM 661 div1 easy MissingLCM

問題 問題概要 lmc(1..M)=lcm(N+1,M)となる最小のMを求める. 解法 まず, 1,..,N,N+1,…,M N+1,…,M のlcmが一致することから,1…Nの中にlcmを作るのに寄与したものがいないので, 1…Nのなかに含まれる最大の素数の2倍の数がすくなくともMまでに含まれていなけれ…

ABC 034 C - 経路

問題 問題概要 道順の総数 解法 高校数学でやった気がする。 (w + h - 2)! / ((w-1)! * (h-1)!) の値を求めるだけでよい。ただ、割り算が入った形の計算式で、modを取らないといけないので、逆元だったり、フェルマーの小定理を使って求めればいい。 ミス な…

yukicoder No.368 LCM of K-products

問題 問題概要 Aの要素の中から、K個選んだ積のすべての要素の最小公倍数を求める。 解法 最小公倍数は、Bの要素を素因数分解したときの、各素因数に対して、Bの要素の中で最大の個数を持つものの積であらわされる。 今回の問題では、BはAの要素をK個選んだ…

yukicoder No.167 N^M mod 10

問題 問題概要 nm mod10 を求める。 ただし制約が大きい。 解法 数として計算するころはできないよね。今回の問題はmod10を求める問題なので、nをm回かけた後の下一桁だけがわかればよい。下一桁がわかればよいということは、nの下一桁のみをm回かければよい…

ARC 035 B - アットコーダー王国のコンテスト事情

問題 問題概要 省略 解法 解く時間が小さい順にといていけば、ペナルティーが最小になる。何通りあるかは、同じもののなかで並び替えてもペナルティーが最小であることに違いはないので、同じ数字がx個あれば、x!通り存在することになるので、それらをかけ合…

codeforces 368 div2 C. Pythagorean Triples

問題 問題概要 1辺の長さ与えられる。その辺を1辺とする、3辺が整数となる正三角形をを作れるなら、ほかの2辺の値をもとめよ。 解法 なんか数学的にあるんだろうなーと思ってググったら、ピタゴラス数の一般組があるみたい。 nが奇数のときと偶数のときで異…

yukicoder No.72 そろばん Med

問題 問題概要 そろばんの一列でいくつ数得られる? 下の制約強化版 mmxsrup.hatenablog.com 解法 そろばんの上の玉がy、下がxとすると、数得られる数は、 (x + 1)y + x -(1) という式で表されて、 条件から、 x + y = n -(2) という式も導かれるので、 yを消…

yukicoder No.71 そろばん

問題 問題概要 そろばんの一列でいくつ数得られる? 解法 そろばんの上の玉がy、下がxとすると、数得られる数は、 (x + 1)y + x -(1) という式で表されて、 条件から、 x + y = n -(2) という式も導かれるので、 yを消去すると求める答えは、下の式が最大とな…

yukicoder No.242 ビンゴゲーム

問題 問題概要 期待値の線形性を使う問題。 期待値の線形性を使う類題 No.144 エラトステネスのざる - yukicoder 解法 この問題のよくわからないところは、縦、横、斜めが独立でないので、どうやれば?て感じになる。ただ、どこか1列だけがビンゴする期待値…

codeforces Educational Codeforces Round 16 B. Optimal Point on a Line

問題 問題概要 x座標上のnこの点が与えられる。それらの点の中から、他の点までの距離の合計が最小となるものを見つけろ。 解法 中央値は母集団の各要素から絶対距離の和が最も小さくするという意味で母集団を代表していると見ることができる(Wikipedia)とか…

SRM 697 div2 easy TriangleMaking

問題 問題概要 3つの辺の長さが与えられる。それを使って、最も辺の長さの合計が長い三角形の辺の長さを求めさい。 解法 三角形の成立条件を使えばいい。成立条件を満たすのなら3辺の和そのものが答えとなり、条件を満たさないなら、最大辺を短くして、ギ…

yukicoder No.53 悪の漸化式

問題 問題概要 漸化式で表されている数列の第n項を求める問題。 解法 3項間漸化式を解いて、一般項を求めた。一般項は a(k) = 4*(3/4)k (k >= 0) となるので、これを利用した。 ミス 高校数学忘れるね。 コード #include <iostream> #include <cstdio> #include <cmath> using namespa</cmath></cstdio></iostream>…

yukicoder No.395 永遠の17歳

問題 問題概要 省略 解法 X進数で表した時17となるXを求める。17の1が数字X分の大きさを持つので、X + 7 = nより X = n - 7を解答として出力すればいい。ただし、17ということは少なくとも8進数以上であることを意味する。X = 8のときn = 15より、nが15より…