読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

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

yukicoder No.458 異なる素数の和

問題 問題概要 N以下の数字を相異なる素数のみで表すことを考える。素数の数の種類の合計値が最大のときの最大値を求めよ。 解法 dpで解ける。 dp[i] := 合計がiとなるときの和の回数の最大値 として、これをループで求めていけばいい。 ただし、今回注意し…

yukicoder No.368 LCM of K-products

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

yukicoder No.12 限定された素数

問題 問題概要 LからRの範囲の中の素数が与えら数の数字(0~9)のみを使い(必ず使わないといけない)、R - Lの最大値を求めよ。 解法 素数判定はエラトステネスを利用、区間の最大値を求めるには、1~5000000までの素数でも、10000以上あるので、すべての区間を…

yukicoder No.407 鴨等素数間隔列の数え上げ

問題 問題概要 数列の隣合う数字の間隔が素数で表されるとき、すべてでいくつの数列が構成できるか求める問題。 解法 入力が5 12の時を考える。 素数2の時 0 2 4 6 8 1 3 5 7 9 2 4 5 8 10 3 5 7 9 11 4 6 8 10 12 上のような4つの数列が存在する。 このとき…

yukicoder No.6 使いものにならないハッシュ

問題 問題概要 省略 解法 ハッシュて書いてあるけど、特に知識などはいらず、ハッシュ生成の作業を実装するだけ。素数判定の部分にエラトステネスを使ってる。 またハッシュ生成後は1ケタの数字となるので、生成後の数字は多くても0~9の10通りに絞られるん。…

yukicoder No.2 素因数ゲーム

問題 問題概要 複数山の石取りゲーム 解法 まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するの…

yukicoder No.385 カップ麺生活

問題 問題概要 カップ麺を買う。買っていく途中で所持金が素数になるとはじめの所持金に戻ることができる。ただし、1つの素数につき、1度だけしか戻ることはできない。最大でいくつのカップ麺を買うことができるかを求める。 解法 まず、所持金以下の数字の…