python どうしても競技プログラミングのD問題が解けない

初心者です
この問題に3日にほど苦しめられています
きちんと出力まではできるのですが、答えが違うと言われるばかりで、どうにも解決策が見出せません…
お時間のある方、どうか力を貸してください

import random
import itertools

N = int(input())

primes_list100 = []
x = 0

for i in range(2,1000):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        primes_list100.append(i)
        x += 1
        if x >=100:
            break

primes_list = random.sample(primes_list100,N)

def primes():
    primes_list = random.sample(primes_list100,N)
    return primes_list

for i in itertools.combinations(primes_list,5):
    k = sum(i)
    for j in range(2,k):
        if k%j == 0:
            break
    else:
        primes_list = primes()

print(' '.join(map(str, primes_list)))

コード

回答2件

ベストアンサー

いや、そんなランダムにサンプル持ってきてあたればいけるはず！では解けないですよ。競プロで乱数を使うのはかなり希です(ないことはないですが、NP困難な問題を乱数をもちいて近似値を求めるというかなり難しい問題になります)。

では解説です。結論から言うとRubyでは2行になります。ちょっと、D問題にしては簡単すぎないかと思ったぐらいです。気づければですが。

素数同士を足したときに合成数になるパターンはどのような物かというのを考えます。

まず、2が含まれる場合です。2と4つの奇素数(奇数の素数)の和は必ず合成数になります。2の倍数個の奇数を足した場合、その数は必ず偶数です。偶数に2を足した場合も偶数です。そしてその数はかならず2より大きいですので、2と何らかの数を掛けた合成数になります。もう一つ重要なのは2以外の素数はすべて奇素数だということです。つまり、条件を満たす数列[a_1, a_2, a_3, ...]があれば、それに2を追加した[2, a_1, a_2, a_3, ...]も条件を満たすと言うことです。なぜなら、追加された2とそれ以外の素数の組合せでは、先ほどの話で全て合成数になると言うことがわかっているからです。

ということで、無条件で2が数列の中に追加できます。N個求めるという話でしたが、実際は3以上からなるN-1個の数列を見つければいいと言うことになります。これで、一個だけ最大が緩和されました。**と言いたいところですが、これは使っても使わなくてもどっちでも良いです。**それより次の方法がなかなか高速であるため、1個ぐらい多くても問題ないからです。

では、2以外の数を考えていきましょう。2の時は必ず偶数になるという組合せを考えた物でした。同じように、必ずある数の倍数になる組合せというのはあるのでしょうか？たとえば、[3, 5, 7, 11, 13]は3の倍数です。このとき3で割った余りを見てみましょう。[0, 2, 1, 2, 1]となりますが、これの合計も3の倍数です。そうです、合計がある数Xの倍数にあるということは、Xでそれぞれを割った余りの合計もXの倍数になると言うことです。しかし、3の場合は組合せが複雑なので、うまく求められません。では、5の場合は？[1, 1, 1, 1, 1]の合計は5です。きづきましたか？5で割った余りが1になる数を5つ集めれば必ず5になります。もしそういう数が大量にあっても、どの5個を集めても余りの合計は5になりますので、その数同士の和も5の倍数です。つまり、単純に5で割った余りが1になる数を探せば、その数同士の組合せは必ず5の倍数、合成数になると言うことになります。

もうおわかりですね。5で割った余りが1になる素数を単純に探していけばいいと言うことです。懸念すべきは、その素数が上限である55555を越えないと言うことです。ご安心ください。55555以下で条件を満たす素数は1408個もあります。この1408個の素数から、適当にN個取り出せば、任意の5個の和が合成数(5の倍数)になる数列ができあがると言うことです。

後は簡単ですね。5で割った余りが1になる素数をN個探して、それを表示するだけです。

その他のアドバイス

Rubyは標準で素数ライブラリprimeがありますが、Pythonにはありません。Pythonで回答する場合は、自分で素数生成するコードを書く必要があります。(Rubyが2行なのはこのライブラリがあるからです)
素数生成のアルゴリズムはエラトステネスの篩(またはその変形)を使わないと遅いです。TLEになる場合は、素数生成のアルゴリズムを見直してください。
最初の2の話はやってもやらなくても速度はさほど変わりません。もちろん組み合わせてN個ではなくN-1個だけ求めるというのもありです。

書いている間に解決している…。

投稿2018/05/19 12:47

編集2018/05/19 12:50

raccy

総合スコア21693

回答へのコメント

karuminmin

2018/05/19 13:09

すごい丁寧にありがとうございます何個かTLEになっていたのでやっぱり遅いですよね…調べて使って見ますなるほど…⁈ 必ず合成数になる場合を見つけて最適化するのは全く思いつきませんでしたまさに目から鱗というか…大変楽しく読ませていただきましたこれからも過去問たくさん解いていきたいと思っているので、また手を貸していただけると嬉しいです。

こんなになっちゃいました。可能な組み合わせの和の中に素数が入っていたら再サンプリングしなおしてやり直し、入っていなければbreakしてその結果を出す・・・というロジックですね。

python
1import random
2import itertools
3
4def is_prime(n):
5    for i in range(2, n):
6        if n%i == 0:
7            return False
8    return True
9
10N = int(input())
11
12primes_list100 = []
13x = 0
14for i in range(2,1000):
15    if is_prime(i):
16        primes_list100.append(i)
17        x += 1
18        if x >=100:
19            break
20
21primes_list = random.sample(primes_list100,N)
22while True:
23    prime_flag = False
24    for combi in itertools.combinations(primes_list,5):
25        combi_sum = sum(combi)
26        if is_prime(combi_sum):
27            prime_flag = True
28            break
29    if prime_flag:
30        primes_list = random.sample(primes_list100,N)
31    else:
32        break
33
34print(' '.join(map(str, primes_list)))

Nが大きくなると時間制約にひっかかると思います・・・。

よく読まないで書いてた回答

なんでこんなの書いたんだろう・・・。

python
1for i in itertools.combinations(primes_list,5):
2    k = sum(i)
3    for j in range(2,k):
4        if k%j == 0:
5            break
6    else:
7        primes_list = primes()