質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • Python

    6842questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5308questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 199

karuminmin

score 8

初心者です
この問題に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)))

コード
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+6

いや、そんなランダムにサンプル持ってきてあたればいけるはず!では解けないですよ。競プロで乱数を使うのはかなり希です(ないことはないですが、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 22:09

    すごい丁寧にありがとうございます
    何個かTLEになっていたのでやっぱり遅いですよね…調べて使って見ます

    なるほど…⁈
    必ず合成数になる場合を見つけて最適化するのは全く思いつきませんでした
    まさに目から鱗というか…大変楽しく読ませていただきました
    これからも過去問たくさん解いていきたいと思っているので、また手を貸していただけると嬉しいです。

    キャンセル

+1

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

import random
import itertools

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

N = int(input())

primes_list100 = []
x = 0
for i in range(2,1000):
    if is_prime(i):
        primes_list100.append(i)
        x += 1
        if x >=100:
            break

primes_list = random.sample(primes_list100,N)
while True:
    prime_flag = False
    for combi in itertools.combinations(primes_list,5):
        combi_sum = sum(combi)
        if is_prime(combi_sum):
            prime_flag = True
            break
    if prime_flag:
        primes_list = random.sample(primes_list100,N)
    else:
        break

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

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

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

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

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()

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/05/19 21:08

    おお!そういう風に関数を定義することもできるんですね…
    while Ture:の部分はFalseになることはなく、else節のbreakで抜ける、という解釈であっていますか?

    キャンセル

  • 2018/05/19 21:13

    はい、そういうことです

    キャンセル

  • 2018/05/19 21:19

    なるほど!
    今回もわかりやすい解答をありがとうございました🙇‍♂️

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    リストサイズの大きい順列の求め方

    例: ["a", "b", "c", "d", e"] このようなリストがあったときに"e"が必ず最後に来るような順列を大きさ2~5の場合ですべて列挙したいです. つまり,

  • 解決済

    pythonでの加重平均について

    前提・実現したいこと 下記のような配列があり、amountの上位n人目までの加重平均を取りたいです。 10人目までの加重平均を取りたい場合は例の配列で言うと(500*3+400*7

  • 解決済

    Python 内包表記

    jupyter notebookでとある数列を求めるプログラムを作りました。 for文の中にあるfor文(for j in range(compare.size + 1)...)を

  • 解決済

    多重ループを抜ける方法

    前提・実現したいこと 多重ループの抜け方がわからないです 発生している問題・エラーメッセージ 多重ループを抜ける際breakなのかsys.exitなのかその他諸々なのかどれを選

  • 解決済

    python 行列式の計算

    pythonのnumpyによる行列式の計算で、 |123|   |234| |456|   |567| |789|   |891| のように、9の9乗通りの計算を自動で出来る簡単な

  • 解決済

    python3 既存コードの拡張

    現状 3枚のカードを並べて、1からxの組み合わせをl配列にいれました。 合計がYのカードに組み合わせを出力してます。 拡張したい部分 3枚ではなく、T枚のカードを並べるには、

  • 受付中

    pythonで、先頭、最後、先頭から2番目、最後から2番目、・・・のように順番に並べる方法が分かりま...

    問題 以下のようなデータ加工を行う関数作成してください。 input test1 1aaa 2bbb 3ccc 4ddd 5eee 6fff 7ggg このデータを 1aaa

  • 解決済

    python 素数メーカー breakの位置

    この問題を解くにあたって、55555以下の素数をランダムにN個生成するという関数を書きました↓ def primesmaker(): global x x =

同じタグがついた質問を見る

  • Python

    6842questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    5308questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。