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

和歌山産pythonプログラマのブログ

和歌山出身プログラマmatsu7874が書いています。Python3と時々C++11を書きます。

素数は通れませんの裏話

Advent Calendar

Advent Calendar Contest Advent Calendar(以下ACCAC) 2015でNo.308 素数は通れません - yukicoderを出題させていただきました。 www.adventar.org

自分はyukicoderの★3を解くのにヒーヒー言う僕が、ACCACの初日に★4の問題を作れてしまったので、
作るときに何を考えていたかメモっておく記事です。

CodeFestivalでLayCurseさんの公演を聴く

みんな見ましょう。
www.youtube.com

ACCACの初日に無謀にも登録する

登録駆動作問ですね。もしかして強い人しか登録しないのかな?
大丈夫かな?などとビクビクしながら考える。

使いたいアルゴリズムを考える

今年一年で私自身が成長したことは幅優先探索がかけるようになったことなので、幅優先探索を使う問題が作りたい
幅優先探索といえば迷路を解く問題ですよね!

Twitterでこの画像をみる。

(google画像検索でソース分かるやろと思ってたらわからなくなってしまいました。分かる方教えて下さい。) f:id:matsu7874:20151226083001j:plain (!を足あとだと見る)

アドベントカレンダーを見る。

  • 私は初日 -> 25日まで行くとゴール
  • 解ける問題だけ通って25日に行けたらゴール。ゴールできるか判定する問題。
  • 簡単すぎ?何の変哲もない幅優先探索の問題になる?
  • でもどうせならゴールしたい。
  • ゴールできるように幅をずらせばいいのでは?
  • 幅を変えながら幅優先探索する問題。
  • 完成 それでいいのか?初日の問題だぞ?翌日LayCurseさんだぞ?作問講座の人だぞ?
  • もっと面白い問題にせねば!

通れるマスに規則性があったほうが面白いのでは?

  • 入力から通れるマスを受け取るより、ある規則に基づいて通れるますを生成できる方が考察が出来て面白いのでは?
  • 規則性といえば素数
  • 素数の方が少ないっぽいので素数は通れないことにしよう。

実験

  • 幅優先探索で書いてみる。
  • Nが小さい時はいろんな値が出てくる。
  • Nが大きい時は8と14しか答えにならないなー

証明

N-8とN-14が共に素数になる非素数Nが存在しないっぽい
とても分かりやすい解説ブログをお読みください。pekempeyさんありがとうございます。 pekempey.hatenablog.com

LayCurseさんの公演を思い出す。「制約を大胆に変えてみる」

  • 僕は大きい制約が好き。
  • 僕は僕はPythonが好き。
  • Pythonは遅い。でも多倍長整数が何も考えずに使える。

=> なんかNをめっちゃおおきくしたいなー

ミラーラビンを知る。

解けそう

  • 解けた。
  • Pythonでも制約が大きい問題が解けた!
  • N<1024の問題がTLEせずに解けた!

学び

  • テストケースが弱かった
    • N-8が擬素数になるようなNを出題する必要があった。のだろう。
  • 制約がきつすぎるとの声もあった
    • Pythonを使いましょう。
    • 競技プログラミングの醍醐味ってアルゴリズムの差で制約の格段に大きい問題を解けるところだと思います。
    • 「LLでは辛いかも」がOKなら「多倍長整数がない言語では辛いかも」もOK……OKですよね?
  • JavaにはBigIntegerも確率的素数判定もあるらしい
  • JavaScriptは誤差のない整数で扱える上限があるらしい。253乗より大きい数は浮動小数点で誤差あり。
  • 自分が作った問題を自分より強い人が解いてくれるのは嬉しい。
  • 自分が作った問題をたくさんの人が解いてくれるのは嬉しい。

yukicoderyukiさん、発起人の高♨級〠焼♨肉 (@camypaper) | Twitterさんありがとうございました。
参加者の皆さんありがとうございました。

僕は解説を見ながら★3の良問・難問を頑張りたいと思います。

追記

12/28
なぜ1024という中途半端な制約にしたのか説明し忘れていました。 Miller–Rabin primality test - Wikipedia, the free encyclopedia

if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

って書いていました。なので論文読んでないですが、この制約には約束されたACが存在します!!!
ロマンで書いても、実利で書いてもOKってやっぱりロマンですね。