トップページ⇒tech
629コメント165KB

[夏の]Supercon2004予選[電脳甲子園]

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
今年も全国のコンピュータヲタ達が熱きバトルを繰り広げるであろう
Supercon2004！
予選課題が発表されたわけですが、我々も一プログラマーとして挑戦してみようではありませんか。というわけで、超高速アルゴリズムをじゃんじゃん投稿しよう、という趣旨のスレです。

東京工業大学スーパーコンピューターコンテスト
http://www.gsic.titech.ac.jp/Japanese/Publication/Supercon/index.html

予選課題の内容
http://www.gsic.titech.ac.jp/supercon/supercon2004/yosen-mondai.html
0002デフォルトの名無しさんNGNG
がんがれ
0003デフォルトの名無しさんNGNG
電波
0004デフォルトの名無しさんNGNG
もりあがんねぇ〜。
0005デフォルトの名無しさんNGNG
↓は多分「糞スレ立てんな」とか言いそうな予感
0006デフォルトの名無しさんNGNG
｜
｜
｜
｜
↓
0007デフォルトの名無しさんNGNG
糞スレ立てんな
0008デフォルトの名無しさんNGNG
そういうのは予選が終わってからにしようよ… 予選の意味が無くなるよ？

というか，どうせ答えが知りたいだけなんだろうな．
0009デフォルトの名無しさんNGNG
答えを出さずに方針だけ出し合えばいいんじゃないのか？
いや、それでもヒントになるか。終わってからにするべきだな。
0010デフォルトの名無しさんNGNG
なんだこの問題、とか思ったら素数判定がPになったのね。
http://idm.s9.xrea.com/factorization/aks.html
0011デフォルトの名無しさんNGNG
10秒以内で解くのなんか無理。
何でそんなに速いのさ。
0012デフォルトの名無しさんNGNG
何が１０秒？
ここにはアップしたりはしないが、63msで実行できた。
ってことはこれって完全にレポート審査になりそうな予感。
0013デフォルトの名無しさんNGNG
予選問題詳細のページにi386って文字が見えるが
まさか本当に386で動かすわけでは・・・w
0014デフォルトの名無しさんNGNG
なんで>>13みたいなDQNがム板に居るの？
0015デフォルトの名無しさんNGNG
東工大生枠が無くなって鬱。
ふざけるな、渡辺。
icpc やってろってか？
0016デフォルトの名無しさんNGNG
予選が締め切られたみたいだけど、結局みんなエラトステネスのふるいを実装したんでしょ。
時間的にどのくらいの差が出たんだろう？
0017デフォルトの名無しさんNGNG
誤差範囲
0018デフォルトの名無しさんNGNG
ほとんど時間は差ないんでないか？レポート審査だな。
0019デフォルトの名無しさんNGNG
36秒で動いてそれ提出した。
みんなそんなもんなのかな？
0020デフォルトの名無しさんNGNG
出題者はそのくらいを想定してるけど,勝ち残るのは1秒未満.
0021デフォルトの名無しさんNGNG
10msです☆(マジ。XP,Pentium4 2.0)
エラトステネスのふるいでやってると死ぬよ？
発想の転換が必要。。
0022デフォルトの名無しさんNGNG
エラトステネス・・・
実装して提出　７００Mで１秒くらいでしたけど・・・・

ただ単に素因数分解するのではなくて
途中で大分枝狩りが可能ですよ。
0023デフォルトの名無しさんNGNG
直前でcygwinで通ったのがvineで通らなくて焦ったよ。
コンパイルエラーは即死だからな。
もちろんみんなvineにgccで試したんだよな。
0024デフォルトの名無しさんNGNG
cygwinは通したけどvineは触ってもいない・・
0025デフォルトの名無しさんNGNG
conio.h とか getch() とか書いてないだろうな。
002624NGNG
>>25
そりゃぁもちろん。。
でも型宣言(？)したらエラーで返ってきますた↓
0027デフォルトの名無しさんNGNG
エラトステネスのふるいは、素数表の作成に使ったけど、1msでいけた。（たぶん、この方法が一番速いだろう。）
その後、Supercon数表の作成に50msほどかかってクイックソートに1ms。
まあ、50〜60ms前後か。やっぱり、レポート審査になるかな？
0028デフォルトの名無しさんNGNG
素数表作成+素因数分解で500msくらいだった
ここ見るとこれじゃ遅いな
素因数分解は結構高速化したつもりだったが…
>>27
クイックソートってことは素因数分解じゃないみたいだな
直接生成? 何使ったんだろ
0029デフォルトの名無しさんNGNG
分解なんてしないでpow(x,1/12)までの素数を組み合わすだけでいいんじゃね？
0030デフォルトの名無しさんNGNG
違うか。x/2^11くらいか
003121NGNG
>>29 >>30
うちはそうしましたよ!!
レポート化するのが一番大変だった・・・
0032デフォルトの名無しさんNGNG
Supercon数の出現頻度を考えれば素因数分解して確認していくより、素数を12個掛けた方がはやいね。
クイックソートするより、最初から sort されたところに入れていくほうが速い気がするけど、どうなの？
オーダーは同じ感じだけど。
003321・31NGNG
>>32
うちはSuperCon数を作るたびにソートしてました。。
でもクイックソートが1msでできるのなら、
そっちのほうが早かったかもです・・・うちのやつよりは↓
てかnの値をもう少し大きくしないと一瞬で終わっちゃうんですけどww
0034デフォルトの名無しさんNGNG
50ms以内のやつはいねぇのか？
0035デフォルトの名無しさんNGNG
あぁ、ソートってそういうことか。
でも全部をソートしなくとも素数の組み合わせからソート済みの順番に生成できそうな悪寒。
003628NGNG
>>29-32
なるほど・・
確かに範囲を絞れば1286^12も試行要らないか
うちは素因数分解で小さい方から素数で割っていって
p^(残り持つべき素数の数) > 現在までに素因数分解されたのの残り
になったら終了にしてた orz
003721・31・33NGNG
>>35
それが意外と大変なんですよね〜>_<
素数2個の組み合わせだけでも、
2*2 2*3 3*3 2*5 2*7 3*5 3*7 2*11 5*5 2*13 3*13 ...
そもそも素数の出現に法則性がない(らしい)ので、
SuperCon数の出現にもこれといった法則性がなさそうなのです。。
003821・31・33NGNG
>>34
50ms切りましたよ☆
>>29さんと>>32さんを組み合わせた感じですけど、
要らない数字をはじきまくりました。。
たとえば2003って素数を2回かけたら、
残りが全て2でも出力する値を超えるので削除、とか…
0039デフォルトの名無しさんNGNG
quick sort は、いかに分ける値をランダムに選べるかが重要なので、
SuperCon数を生成するときに、小さい数 -> 大きい数みたいな傾向があると、
少し効率が悪くなってる悪寒。

C++ なら std::set に突っ込んで終わりそう。

まぁ、SuperCon数の生成がボトルネック。
0040デフォルトの名無しさんNGNG
ttp://www.gsic.titech.ac.jp/supercon/supercon2004/index.html
から、募集要項をクリックして、その後、本戦問題をクリックして見よう。
ttp://www.gsic.titech.ac.jp/supercon/supercon2004/honsen.html

びっくりした…。
0041デフォルトの名無しさんNGNG
なんでびっくりする？
って、８月２日後悔ってかｗ
0042デフォルトの名無しさんNGNG
あ、俺もびっくりしたww
てか41うまいけど上げんなヴォケ
0043予選通過者NGNG
素数テーブル作成＆Supercon数探索＆ソートで約1msです。
ちなみに、VC++6.0、Debugモード、Pentium4 2.8Ghz。
1ms普通に切ってる人いないかな？ちなみに素数テーブル作成はエラトステネス。
除算使うよ。発想の転換が大切。
0044デフォルトの名無しさんNGNG
gccでコンパイルしてtimeで計測してください。
それにしても結果出てるのに今更な書き込みですね。
0045デフォルトの名無しさんNGNG
早ぇっww
0046デフォルトの名無しさんNGNG
ageage･･･
予選問題解答っていつUpされんの？？
0047デフォルトの名無しさんNGNG
予選順位発表してほしいもんだなｗ
0048名無しさん＠そうだ選挙に行こうNGNG
本戦問題の概要が届いたんだが、ページ上ではまだ発表されてないんだなぁ。
RSA暗号とだけ言っておこう。
0049デフォルトの名無しさんNGNG
>>ｵﾓﾀ。。大会中に聞こう･･･どぞよろしくｗｗ
0050デフォルトの名無しさんNGNG
>>47だ・・・スマソ
0051デフォルトの名無しさんNGNG
>RSA暗号

カーマイケル数
フェルマーの小定理
フェルマーテスト
擬素数

くらいしか思いつかない。
他に調べて損のない単語を挙げよう。
0052デフォルトの名無しさんNGNG
問題外にわからん・・・ちょっとだけヒントくれ･･･
ってかそれより下さい･･･まじで>_<
005347NGNG
>>49
俺は関西からの出場だ。
本選で会おう！
0054デフォルトの名無しさんNGNG
ランダムを利用したアルゴリズムに関して少し勉強しておいた方が良いかも。
ランダムを利用した素数判定とか。

と、問題知らないけど予想してみるテスト。
0055デフォルトの名無しさんNGNG
MTでも出るんですか？
0056デフォルトの名無しさんNGNG
メルセンヌツイスターって書きたくなるよね。
メルセンヌツイスター。
メルセンヌツイスター。

乱数そのものと言うよりたぶん、乱数を使うアルゴリズムか出るんじゃないかと、
問題知らないけど予想してみるテスト。
005749NGNG
>>47
同じく関西〜ｗよろですｗ
005847NGNG
>>57
関西２校しかないから大体相手の見当付くよなｗｗ
0059デフォルトの名無しさんNGNG
あぁ,もう夏休みか.
0060デフォルトの名無しさんNGNG
みんなもうログインした?
0061デフォルトの名無しさんNGNG
Onyxに今入ってるところだったり。
DeleteKey周りの設定とか、
keymapの読み込みとかでちょっと手間取ったが…。
0062デフォルトの名無しさんNGNG
Emacs の設定ファイルは持ち込み可？
0063デフォルトの名無しさんNGNG
>>62
過去出場したけどOKぽかった。
0064デフォルトの名無しさんNGNG
予選レベルの高さに圧倒されまくりの浪人生だったりもしますが、
数年前の記憶を元にMPIについて少しだけ書いてみることにします。

MPIがTCP/IPと違うのは、サーバーとクライアントの振り分け処理と、
クライアントの数が決まっていることくらいだったという記憶があります。
＃それ以前にTCP/IPを例えに用いて良いのかは謎ですが。

TCP/IPでは、サーバー側がbindしてクライアント側がconnectするのに対し、
MPIではプロセス（プロセス数はコマンドラインで指定）が立ち上がるだけです。
そこで、どうやってクライアント・サーバーの区別をするかというと、
MPI_Comm_rank() の戻り値（０から１刻みで増えていく）が、
プロセスによって違っているのを利用します。
ちなみに、MPI_Comm_rank() == 0 ならサーバー側処理を実行して、
MPI_Comm_rank() != 0 ならクライアント側処理を実行するのが定番らしいです。
＃プロセス数は、MPI_Comm_size() で所得できます。
006564NGNG
後は、互いのプロセスのメモリを直接参照出来ない(=TCP/IPと同じ)のと、
全てのプロセスの出力内容はすべて同一のウィンドウに表示されることに
留意しながら、MPI_Send()＆MPI_Recv() を繰り返し書いていくだけです。
（各プロセスの処理時間）＞＞（プロセス間通信の時間）のようにプログラムを組めば、
ほかの関数群（MPI_Barrier,MPI_Bcast,etc）を用いなくても、それほど実行時間に
影響しないと思います。
＃それよりも、使う関数が多すぎて混乱して失敗、という悪循環の方が心配です。

ただし、MPI_Send()＆MPI_Recv() は、処理が終了するまで制御が戻らない
（マルチスレッドでは無い）ということに注意してください。メッセージの宛先や、
サイズ、タグが一つでも違うと、動作不良（たとえばフリーズしたり）になったと思います。

プロセス１　MPI_Send(宛先：プロセス２　メッセージタグ：0x0001)
プロセス２　MPI_Recv(宛先：プロセス１　メッセージタグ：0x0002)
↑この処理（タグが違う）が同時に起こるのは避けるべきです。

それと、構造体を送る場合は、MPI_CHAR + sizeof(struct HOGE) で送れます。
長文＆不正確な内容でスマソ。本選の方がんばってくださいませ！
＃で、私は東工大目指して頑張っている訳だがorz
0066デフォルトの名無しさんNGNG
Emacsの設定ファイルは持ち込み可能なのかぁ…。
本の持ち込みとか、自作ライブラリの持ち込みって可能なのかな？
(予選の段階で作った、素数の個数の近似求める関数等、持ち込めないともったいない)
0067デフォルトの名無しさんNGNG
.emacs にコメントで書いていけば？
0068デフォルトの名無しさんNGNG
補足．

>>65
> 全てのプロセスの出力内容はすべて同一のウィンドウに表示される
今回のルールがどうなるか分からないけど，rank!=0なプロセスからデータを出力するのは
禁止されているかもしれない．注意してください．
(自分の出場した時，そのせいで失格になったチームが居たような...)

rank==0プロセスは他のプロセスの管理だけをやって計算に参加させないのもありだと
思うな．それをやってもどうせ計算速度は1/64しか落ちないんだし．
0069デフォルトの名無しさんNGNG
>>66
2001年の話なので古いかもしれないけど。

本はおっけー。
というか、大学にいてもいいのはお昼だけだから宿では何をやってもいいよ。
大学に自分のノートPCを持ち込んでプログラム書いたりしてる人もいたし、
多分sshでログインしてスパコンを使うこともできるはず。
.emacsとかあんまり気にしなくていいんじゃないかなと。

>>47あたり
みんなでソースコード貼らない？長さで投稿制限に引っかかるかな、、、

俺は2.8ms程度。環境はPentiumM 1.3GHz、RedHatLinux7.3上で実行。
コンパイラはgcc2.96でオプションが-O3。
0070デフォルトの名無しさんNGNG
>>68
気をつけます。。
>>69
本線終わったらどっかに張ろう!一応メンバーに確認とるけど多分大丈夫だ
2.8msか・・・早いな>_<;;

あと、しょうもない質問させてください・・・
MPI_SendとMPI_Recvは、一方がそこまでたどり着いていない場合は
もう一方は処理をとめて待っているのですか？？
recvの方は待ってるんだろうけどsendの方は･･･M(_ _)M
0071デフォルトの名無しさんNGNG
>>70
MPI_SendとMPI_Recvは待つよ。Sendも、受け取ってくれるまで待つ。
MPI_IsendとMPI_Irecvは待たないけど、普通は使わないよね。

んでSendとRecvはブロッキング通信だから、適当なことやってるとデッドロックします。
命令を呼ぶ順番にちょっとだけ気をつけましょうね、と。
まぁC言語に慣れてるならばかなり面白い大会のはず。楽しんできてね。予選通過おめ！
0072デフォルトの名無しさんNGNG
>>69
の話で思い出したんだが，本選に出る人たちに一つ言いたいことが．

-O3はやめておいたほうがいい．コードによっちゃ最適化オプションつけないのとは
スピードが何倍も変わる．
本選の評価では最適化オプションはつけないでコンパイルするからね．

というのは，自分のチームは本選中ずっと-O3コンパイルしてて，コンテスト終了間際に
それに気づいたときにはもう後の祭りだったという苦い思い出があって．
終了３時間前までは優勝を確信してますたorz
同じ間違いはしないでくれ…
0073デフォルトの名無しさんNGNG
>>72
mpp(東工大のorigin2000)のCコンパイラのデフォルト最適化レベルは-O0(最適化オフ)だね。
ttp://www.gsic.titech.ac.jp/Japanese/Service/R_System/Document/Tutorial/SGI/origin_advanced.pdf
-O3だと計算順序の入れ替えとか変更するから精度が落ちることあるし、並列プロセスからのデータの取得順序とか
計算順序も変わってくるんじゃなかったっけ？
普通に考えたらコンテストの審査で結果が変わるかもしれない-O3オプションでコンパイルするわけがありません。
予選もだけど、特に指定がなければオプションなしでコンパイルしていると思うべきだと思う。
デフォルトでコンパイルしている組との結果を比べてほくそえんでたとしたら･･･ご愁傷様でした。

持ち込みその他の条件については>>69の言うとおりだと思う。
0074デフォルトの名無しさんNGNG
本選前に練習問題作ってがんばりすぎた･･･
しかも同チームの奴が4分の1の時間でやりやがった･･･
んで今日は昼にPC煙出しそうな熱で停止するし･･･
誰かこんな俺にエールを(_no orz
0075デフォルトの名無しさんNGNG
しかも上げつった･･･すまそ>_,;;
0076デフォルトの名無しさんNGNG
＿|￣|○なんか>>74のあたりに仲間がいるな…。ﾅｶﾏﾆﾇｶﾚﾙﾄｻﾐｼｲ

どーでもいいのだが、まだOnyx2に接続できるなぁ。もう7/30過ぎてるんだが…。
馬鹿正直に31日になった段階で切断したﾔｼが損しないか？
007774NGNG
>>76
(*^o^)人(^-^*)ﾅｶﾏー
接続とかここ4日やってねぇ>_<;;
でも俺が思うにあれは記載ミスじゃないﾉﾝ？
0078デフォルトの名無しさんNGNG
いよいよだな･･･俺たちは明日出発します。。
みんなに会えるのを楽しみにしとくぞ!!
0079デフォルトの名無しさんNGNG
みんなーありがとう!!
最高の大会だったよｗ
１年間sage進行で保守する事を誓う!!
0080デフォルトの名無しさんNGNG
>>79
……本気かい。
ま、いいや。

ともかく、本当にいい大会だったよ。
来年も出たいなあ……
0081demekingNGNG
このスレではコテハン使うんでよろ〜
俺は関西人で一番喋って茶髪で(ry
家のパソコンのキーボードが使いにくくなってしまったｗ

俺は来年忙しいから出れへんけど、メールとかそんなんでみんな仲良ぅしよな〜☆
漏れも>>79に続いて誓う☆

ハイテンションな俺のノリについてきて喋ってくれたみんな、ありがとう〜☆
0082デフォルトの名無しさんNGNG
>>81
4位おめ。
俺はしばらくドラマーに戻りますｗ
008379NGNG
>>82
そういうお前はもしや最終日欠席者では･･･>_<;
>>80
本気ですぞ。。ちょうど1年後に新しいの建てる予定(2005Ver)
0084デフォルトの名無しさんNGNG
最終日欠席者は俺です。。。（＞。＜
ほんとマジでいい大会だったのに
最終日にダウンして家で寝てましたょ・・
みんなのアルゴリズムとか聞きたかったなぁ。

>>83
俺はドラマーじゃなくてギタリストに戻る予定です（笑
0085demekingNGNG
>>84　ﾄﾞｿﾏｲ

誰か今年度大会のHP作成ｷﾎﾞﾝﾇ
俺にそんな技術は無いのでｗ
008684改めrank==0NGNG
>>85
ＨＰ作成いいねぇ。どうせ作るなら本家のページより
詳しくて見やすいのとかどうよ？（笑
このページ見てる人でＨＴＭＬ得意な人とかいるかなぁ。
0087デフォルトの名無しさんNGNG
>>83
俺はSPAMと時計をもらった人ですｗ
0088demekingNGNG
とある高校の香具師が自宅で鯖管理してるらしいからその人に頼んでみてんけど・・・
HP作ったら長続きしそうやなぁ〜
0089デフォルトの名無しさんNGNG
で、どこが勝ったの?
0090デフォルトの名無しさんNGNG
…公式ページ更新されてないよな…。
0091デフォルトの名無しさんNGNG
まーいーよ。
書いちゃおうぜ。

一位は麻布のnemuiチーム。
二位は中国のchinaチーム。
三位は浅野のnomeanチーム。

……中国はともかく、「眠い」と「無意味」が上位に入るなんて、誰が予想しただろう。
あと、四位は兵庫県立長田高校のnagaterチーム。
国内上位三チーム全てが頭文字「n」であるという、異例の事態。
0092デフォルトの名無しさんNGNG
ほんまやーみんなnやーｗ
来年はn付けとこーww
SPAMｷﾀｰ(ﾎｽｲ

みんなコードどれくらいかいた？
うちデバック情報入れて12page(長)
0093デフォルトの名無しさんNGNG
>84
緑色のカードは速やかに返却すること。
(FAXも可)
0094デフォルトの名無しさんNGNG
……FAXって凄いな。
0095デフォルトの名無しさんNGNG
>>84
もったいないことしたなぁｗ
まぁその分いいギタリストになってくれｗ
>>90
なんか停電してるらしいぞ学校がｗ
0096デフォルトの名無しさんNGNG
>95
本日５時に、電源を入れました(＠サカモト)
009795NGNG
>>96
坂本先生さまでいらっしゃいますか･･･
失礼いたしました･･･(((^^;)(;^^) ))
0098demekingNGNG
大会HPうｐ待ち・・・
0099デフォルトの名無しさんNGNG
各チームアルゴリズム(とくにMPI化したところ)をここに書き込まないか?
3チーム以上の同意があればやろうとおもうのだが・・
0100nomean唯一の高三生　 ◆vG5F1vSPks NGNG
>>99
とりあえず、うちのチームはOKです。


ワードバスケット、横浜ロフトにも東急ハンズにも売ってないと思ったら
http://homepage.mac.com/jaga_online/wb/shop_list.html
有隣堂＆紀伊国屋で売ってるのか……
これから買いに行こ。
0101demeking ◆xIgpX047MQ NGNG
トリップ付けるん忘れとった・・・

>>100
勉強汁

ってか夏の課題終わらねぇ・・・
■ このスレッドは過去ログ倉庫に格納されています