パソコン甲子園裏本選について
パソコン甲子園の裏本選(予選落ちしたチームも同じ条件でオンライン本選に臨める)が昨日ありました。私のチームのパートナーが1時間ほどで帰ってしまったため残り3時間ほどは私一人で寂しかったのですが、予選落ち校では35位という成績を残せました。ここでは解けた問題についていろいろ言っていこうと思います。(解けたのは1~3番、家に帰ってちょっと書きかえて解けたのが10番)
1番「4つ入力された数値から長方形が作れるかどうか判定しろ」
プログラム自体はソートして前2個と後ろ2個が等しければyes、そうでなければnoと出力するだけだったのですが、trueとfalseで出力したため提出回数が1回増えました。これはマジでもったいないミス
2番「12個入力された数値から直方体が作れるかどうか判定しろ」
ソートして4つごとに等しいかどうか判定してyes noを返すという感じでときました。
これは特に問題なく通過
3番「入力された異なる4つの値を当てはめて(A+B)/(C-D)の最大値を求めよ」
分母を優先する場合と分子を優先する場合に分けて組みました。差の最小は、ソートした後探索して求め、和の最大は昇順にソートして末尾の要素とその前の要素をとりました。(重複があってはならないので場合分けが必要だった)
問題文に
cout.setf(ios_base::fixed,ios_base::floatfield);
cout << result << endl;
って書けば小数点以下も表示できる
って書いてあったのにそのとおりに書いてもうまく行かず、結局
cout << fixed << result << endl;
って書きました。(これのせいで提出回数3回増えた)
ほんとにクソ
(あとから思い出したんだけどこれキャストして代入したらうまく行ったんだった int型のほうが強いんですねぇ)
10番「チェス盤を移動するアリが落下する順位を返すプログラムを作れ」
予選落ち勢ではだれも解けていなかった問題です。プランとしてはそれぞれのアリが落下する時間を求めて配列に格納し、それに順位をつけて出力しました。
アリの挙動もそこまで複雑ではなかったので10番という番号のわりにそこまで難しくは無かったと思います。(時間内に解けませんでしたが)
http://web-ext.u-aizu.ac.jp/pc-concours/2016/download/pck2016f_all.pdf
問題はこちらです
素数生成とグラボを使った多倍長演算
かなり昔の話ですが、素数を600億まで計算しました。アルゴリズムはエラトステネスの篩です。7以上の素数は30で割って1,7,11,13,17,19,23,29余るという性質を利用して8個にスレッドを分けています。この8個という数字、私のコンピュータのロジックコア数に相当するのでそれなりに効率よく処理を配分できていると思います。
タイムはintel Core i7 4770K 3.5~3.9GHzの8logic coreで、90秒でした。
篩処理は配列の要素を1に書き換えていくという方法を取っているのでgccのコンパイルの最適化オプションの-O3にかなり恩恵を受けています(タイムが半分ぐらいになった)
部活のi5のデスクトップで300億まで計算させてみたところ、こちらは60秒でした。(私のだと45秒だった)シングルロジックコアに割り当てられるキャッシュ量が部活のPCの方が多いのが原因かも知れません。
知っての通りC++のスタンダードライブラリに多倍長演算をサポートするものはありません。私はGMPという素晴らしいライブラリ(とにかく演算がめちゃくちゃ速い。FFTを使ってるんでしょううが8000万bit同士の演算が0.3秒で終わる)を使っていますが、それでももっと早くしたいなと思うことがあります。
掛け算とかの簡単な処理はグラボで処理させたほうが速いと思って調べてみてるところなのですが、積表を用いて演算する方式が取られているものがありました。コンピュータで演算させることを考えたらビット演算でやるのが良さそうなきがしますがどうでしょうね。
レピュニット素数
10進で1を並べて作った数のうち、素数になるものです。
超レアです。
2、19、23、317、1031、、、、というふうになるらしいです。
ミラーラビンで1から判定してみたのですが、確かにめちゃくちゃレアです。
1031の次は5万弱というのだから笑えませんね
メルセンヌ素数みたいに専用のアルゴリズムがあるわけではないでしょうし劇的な高速化も不可能な気がします。実際Wikipediaに載っているものもprobably primeなので私どうようミラーラビン判定法が使われていると考えられます。私が探したとき1031まで程度ならばそこまで時間はかかりませんでした
それと、ノートパソコンに入っていたWindows10を消してlinux mintを入れました。この先数カ月は動画を作る用事がなさそうなので持ち運びに便利なノートパソコンで開発をおこなえるようにしたかったのが理由です。 デスクトップのほうが使いやすいっちゃ使いやすいのですが、たまにはノートでやるのも悪くないですね。(ちなみにデスクトップのドライブの容量は128GBでノートが240なのでノートパソコンの方がでかい)
ただ、3月中旬から下旬にかけて動画をつくる用事が出てきそうなのでそれまでに500GB程度のSSDを買いたいなと思っています。
パソコン甲子園について
当方今高校1年で、ぱそこんをいじる部活の部長をしています。部活で先日(9月上旬だったかな?)会津大学主催のパソコン甲子園に出場しました。私を含め、出場者全員(4人)人生初の競プロだったのですが、私ともう一人の古参のチームがブロックの新人賞をいただきました。(予選落ちしましたが)
当初の予定としては、前半(1〜4までぐらい)をそいつが考えてる間に私が5番以降のアルゴリズムを考えるというイメージで行こうと思っていたのですが、案外6番以降が難しくて1番から5番までしか解けませんでした。(9番が解けそうだったらしいですがなんかコンパイラがへんな挙動を見せたらしい)
1から5番程度ならどちらか片方だけしかいなくても余裕で解けていたと思うのでちょっと不甲斐ない結果でした。
また、パートナーの実装力にとても助けられたと感じたコンテストでもありました。9番がおしいところまで行ったのはひとえに彼のおかげです。
来年はぜひ会津で本選に臨みたいです。
リュカレーマーテストとミラーラビンテスト
※リュカレーマーテストもミラーラビンテストもWiki見ればわかるので説明は省略します。
少し前にリュカレーマーテストを使って下から順にメルセンヌ素数を探すプログラムを組んだのですが、7~8時間かかって28番目が出ないという感じでした。
リュカレーマーテストは指数の二乗に比例して実行時間が伸びる気がするので、「リュカレーマーテストで全部の候補をテストするの効率悪すぎやろ」ってなって「これ確率的な方法である程度目星つけてからやってんのとちゃうか?」と思い、確率的素数判定アルゴリズムとして非常に有名なミラーラビンテストを実装して試しにサクッと組んで実装してみました。
2の9941乗-1を判定した(擬素数対策に100回判定)(乱数は64bit)
ちなみにリュカレーマー
ミラーラビンで一回しか判定しなくても0.4秒かかるのでリュカレーマーテストの方が速い
やはり任意の数を判定できるアルゴリズムなのでメルセンヌ素数に特化したアルゴリズムにはかなわないようです。
それにしても離散演算するとは言えGIMPSはどうやって49番目とか見つけたんでしょうね
どうもよろしく
ブログを書いた経験が全く無いので拙い文章が膨大に発生しそうですがどうぞよろしく(いきなり拙い日本語が露呈している)