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

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

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

予選課題の内容
http://www.gsic.titech.ac.jp/supercon/supercon2004/yosen-mondai.html

がんがれ

電波

もりあがんねぇ〜。

↓は多分「糞スレ立てんな」とか言いそうな予感

｜
｜
｜
｜
↓

糞スレ立てんな

そういうのは予選が終わってからにしようよ… 予選の意味が無くなるよ？

というか，どうせ答えが知りたいだけなんだろうな．

答えを出さずに方針だけ出し合えばいいんじゃないのか？
いや、それでもヒントになるか。終わってからにするべきだな。

なんだこの問題、とか思ったら素数判定がPになったのね。
http://idm.s9.xrea.com/factorization/aks.html

10秒以内で解くのなんか無理。
何でそんなに速いのさ。

何が１０秒？
ここにはアップしたりはしないが、63msで実行できた。
ってことはこれって完全にレポート審査になりそうな予感。

予選問題詳細のページにi386って文字が見えるが
まさか本当に386で動かすわけでは・・・w

なんで>>13みたいなDQNがム板に居るの？

東工大生枠が無くなって鬱。
ふざけるな、渡辺。
icpc やってろってか？

予選が締め切られたみたいだけど、結局みんなエラトステネスのふるいを実装したんでしょ。
時間的にどのくらいの差が出たんだろう？

誤差範囲

ほとんど時間は差ないんでないか？レポート審査だな。

36秒で動いてそれ提出した。
みんなそんなもんなのかな？

出題者はそのくらいを想定してるけど,勝ち残るのは1秒未満.

10msです☆(マジ。XP,Pentium4 2.0)
エラトステネスのふるいでやってると死ぬよ？
発想の転換が必要。。

エラトステネス・・・
実装して提出　７００Mで１秒くらいでしたけど・・・・

ただ単に素因数分解するのではなくて
途中で大分枝狩りが可能ですよ。

直前でcygwinで通ったのがvineで通らなくて焦ったよ。
コンパイルエラーは即死だからな。
もちろんみんなvineにgccで試したんだよな。

cygwinは通したけどvineは触ってもいない・・

conio.h とか getch() とか書いてないだろうな。

>>25
そりゃぁもちろん。。
でも型宣言(？)したらエラーで返ってきますた↓

エラトステネスのふるいは、素数表の作成に使ったけど、1msでいけた。（たぶん、この方法が一番速いだろう。）
その後、Supercon数表の作成に50msほどかかってクイックソートに1ms。
まあ、50〜60ms前後か。やっぱり、レポート審査になるかな？

素数表作成+素因数分解で500msくらいだった
ここ見るとこれじゃ遅いな
素因数分解は結構高速化したつもりだったが…
>>27
クイックソートってことは素因数分解じゃないみたいだな
直接生成? 何使ったんだろ

分解なんてしないでpow(x,1/12)までの素数を組み合わすだけでいいんじゃね？

違うか。x/2^11くらいか

>>29 >>30
うちはそうしましたよ!!
レポート化するのが一番大変だった・・・

Supercon数の出現頻度を考えれば素因数分解して確認していくより、素数を12個掛けた方がはやいね。
クイックソートするより、最初から sort されたところに入れていくほうが速い気がするけど、どうなの？
オーダーは同じ感じだけど。

>>32
うちはSuperCon数を作るたびにソートしてました。。
でもクイックソートが1msでできるのなら、
そっちのほうが早かったかもです・・・うちのやつよりは↓
てかnの値をもう少し大きくしないと一瞬で終わっちゃうんですけどww

50ms以内のやつはいねぇのか？

あぁ、ソートってそういうことか。
でも全部をソートしなくとも素数の組み合わせからソート済みの順番に生成できそうな悪寒。

>>29-32
なるほど・・
確かに範囲を絞れば1286^12も試行要らないか
うちは素因数分解で小さい方から素数で割っていって
p^(残り持つべき素数の数) > 現在までに素因数分解されたのの残り
になったら終了にしてた orz

>>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数の出現にもこれといった法則性がなさそうなのです。。

>>34
50ms切りましたよ☆
>>29さんと>>32さんを組み合わせた感じですけど、
要らない数字をはじきまくりました。。
たとえば2003って素数を2回かけたら、
残りが全て2でも出力する値を超えるので削除、とか…

quick sort は、いかに分ける値をランダムに選べるかが重要なので、
SuperCon数を生成するときに、小さい数 -> 大きい数みたいな傾向があると、
少し効率が悪くなってる悪寒。

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

まぁ、SuperCon数の生成がボトルネック。

ttp://www.gsic.titech.ac.jp/supercon/supercon2004/index.html
から、募集要項をクリックして、その後、本戦問題をクリックして見よう。
ttp://www.gsic.titech.ac.jp/supercon/supercon2004/honsen.html

びっくりした…。

なんでびっくりする？
って、８月２日後悔ってかｗ

あ、俺もびっくりしたww
てか41うまいけど上げんなヴォケ

素数テーブル作成＆Supercon数探索＆ソートで約1msです。
ちなみに、VC++6.0、Debugモード、Pentium4 2.8Ghz。
1ms普通に切ってる人いないかな？ちなみに素数テーブル作成はエラトステネス。
除算使うよ。発想の転換が大切。

gccでコンパイルしてtimeで計測してください。
それにしても結果出てるのに今更な書き込みですね。

早ぇっww

ageage･･･
予選問題解答っていつUpされんの？？

予選順位発表してほしいもんだなｗ

本戦問題の概要が届いたんだが、ページ上ではまだ発表されてないんだなぁ。
RSA暗号とだけ言っておこう。

>>ｵﾓﾀ。。大会中に聞こう･･･どぞよろしくｗｗ

>>47だ・・・スマソ

>RSA暗号

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

くらいしか思いつかない。
他に調べて損のない単語を挙げよう。

問題外にわからん・・・ちょっとだけヒントくれ･･･
ってかそれより下さい･･･まじで>_<

>>49
俺は関西からの出場だ。
本選で会おう！

ランダムを利用したアルゴリズムに関して少し勉強しておいた方が良いかも。
ランダムを利用した素数判定とか。

と、問題知らないけど予想してみるテスト。

MTでも出るんですか？

メルセンヌツイスターって書きたくなるよね。
メルセンヌツイスター。
メルセンヌツイスター。

乱数そのものと言うよりたぶん、乱数を使うアルゴリズムか出るんじゃないかと、
問題知らないけど予想してみるテスト。

>>47
同じく関西〜ｗよろですｗ

>>57
関西２校しかないから大体相手の見当付くよなｗｗ

あぁ,もう夏休みか.

みんなもうログインした?

Onyxに今入ってるところだったり。
DeleteKey周りの設定とか、
keymapの読み込みとかでちょっと手間取ったが…。

Emacs の設定ファイルは持ち込み可？

>>62
過去出場したけどOKぽかった。

予選レベルの高さに圧倒されまくりの浪人生だったりもしますが、
数年前の記憶を元に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() で所得できます。

後は、互いのプロセスのメモリを直接参照出来ない(=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

Emacsの設定ファイルは持ち込み可能なのかぁ…。
本の持ち込みとか、自作ライブラリの持ち込みって可能なのかな？
(予選の段階で作った、素数の個数の近似求める関数等、持ち込めないともったいない)

.emacs にコメントで書いていけば？

補足．

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

rank==0プロセスは他のプロセスの管理だけをやって計算に参加させないのもありだと
思うな．それをやってもどうせ計算速度は1/64しか落ちないんだし．

>>66
2001年の話なので古いかもしれないけど。

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

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

俺は2.8ms程度。環境はPentiumM 1.3GHz、RedHatLinux7.3上で実行。
コンパイラはgcc2.96でオプションが-O3。

>>68
気をつけます。。
>>69
本線終わったらどっかに張ろう!一応メンバーに確認とるけど多分大丈夫だ
2.8msか・・・早いな>_<;;

あと、しょうもない質問させてください・・・
MPI_SendとMPI_Recvは、一方がそこまでたどり着いていない場合は
もう一方は処理をとめて待っているのですか？？
recvの方は待ってるんだろうけどsendの方は･･･M(_ _)M

>>70
MPI_SendとMPI_Recvは待つよ。Sendも、受け取ってくれるまで待つ。
MPI_IsendとMPI_Irecvは待たないけど、普通は使わないよね。

んでSendとRecvはブロッキング通信だから、適当なことやってるとデッドロックします。
命令を呼ぶ順番にちょっとだけ気をつけましょうね、と。
まぁC言語に慣れてるならばかなり面白い大会のはず。楽しんできてね。予選通過おめ！

>>69
の話で思い出したんだが，本選に出る人たちに一つ言いたいことが．

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

というのは，自分のチームは本選中ずっと-O3コンパイルしてて，コンテスト終了間際に
それに気づいたときにはもう後の祭りだったという苦い思い出があって．
終了３時間前までは優勝を確信してますたorz
同じ間違いはしないでくれ…

>>72
mpp(東工大のorigin2000)のCコンパイラのデフォルト最適化レベルは-O0(最適化オフ)だね。
ttp://www.gsic.titech.ac.jp/Japanese/Service/R_System/Document/Tutorial/SGI/origin_advanced.pdf
-O3だと計算順序の入れ替えとか変更するから精度が落ちることあるし、並列プロセスからのデータの取得順序とか
計算順序も変わってくるんじゃなかったっけ？
普通に考えたらコンテストの審査で結果が変わるかもしれない-O3オプションでコンパイルするわけがありません。
予選もだけど、特に指定がなければオプションなしでコンパイルしていると思うべきだと思う。
デフォルトでコンパイルしている組との結果を比べてほくそえんでたとしたら･･･ご愁傷様でした。

持ち込みその他の条件については>>69の言うとおりだと思う。

本選前に練習問題作ってがんばりすぎた･･･
しかも同チームの奴が4分の1の時間でやりやがった･･･
んで今日は昼にPC煙出しそうな熱で停止するし･･･
誰かこんな俺にエールを(_no orz

しかも上げつった･･･すまそ>_,;;

＿|￣|○なんか>>74のあたりに仲間がいるな…。ﾅｶﾏﾆﾇｶﾚﾙﾄｻﾐｼｲ

どーでもいいのだが、まだOnyx2に接続できるなぁ。もう7/30過ぎてるんだが…。
馬鹿正直に31日になった段階で切断したﾔｼが損しないか？

>>76
(*^o^)人(^-^*)ﾅｶﾏー
接続とかここ4日やってねぇ>_<;;
でも俺が思うにあれは記載ミスじゃないﾉﾝ？

いよいよだな･･･俺たちは明日出発します。。
みんなに会えるのを楽しみにしとくぞ!!

みんなーありがとう!!
最高の大会だったよｗ
１年間sage進行で保守する事を誓う!!

>>79
……本気かい。
ま、いいや。

ともかく、本当にいい大会だったよ。
来年も出たいなあ……

このスレではコテハン使うんでよろ〜
俺は関西人で一番喋って茶髪で(ry
家のパソコンのキーボードが使いにくくなってしまったｗ

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

ハイテンションな俺のノリについてきて喋ってくれたみんな、ありがとう〜☆

>>81
4位おめ。
俺はしばらくドラマーに戻りますｗ

>>82
そういうお前はもしや最終日欠席者では･･･>_<;
>>80
本気ですぞ。。ちょうど1年後に新しいの建てる予定(2005Ver)

最終日欠席者は俺です。。。（＞。＜
ほんとマジでいい大会だったのに
最終日にダウンして家で寝てましたょ・・
みんなのアルゴリズムとか聞きたかったなぁ。

>>83
俺はドラマーじゃなくてギタリストに戻る予定です（笑

>>84　ﾄﾞｿﾏｲ

誰か今年度大会のHP作成ｷﾎﾞﾝﾇ
俺にそんな技術は無いのでｗ

>>85
ＨＰ作成いいねぇ。どうせ作るなら本家のページより
詳しくて見やすいのとかどうよ？（笑
このページ見てる人でＨＴＭＬ得意な人とかいるかなぁ。

>>83
俺はSPAMと時計をもらった人ですｗ

とある高校の香具師が自宅で鯖管理してるらしいからその人に頼んでみてんけど・・・
HP作ったら長続きしそうやなぁ〜

で、どこが勝ったの?

…公式ページ更新されてないよな…。

まーいーよ。
書いちゃおうぜ。

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

……中国はともかく、「眠い」と「無意味」が上位に入るなんて、誰が予想しただろう。
あと、四位は兵庫県立長田高校のnagaterチーム。
国内上位三チーム全てが頭文字「n」であるという、異例の事態。

ほんまやーみんなnやーｗ
来年はn付けとこーww
SPAMｷﾀｰ(ﾎｽｲ

みんなコードどれくらいかいた？
うちデバック情報入れて12page(長)

>84
緑色のカードは速やかに返却すること。
(FAXも可)

……FAXって凄いな。

>>84
もったいないことしたなぁｗ
まぁその分いいギタリストになってくれｗ
>>90
なんか停電してるらしいぞ学校がｗ

>95
本日５時に、電源を入れました(＠サカモト)

>>96
坂本先生さまでいらっしゃいますか･･･
失礼いたしました･･･(((^^;)(;^^) ))

大会HPうｐ待ち・・・

各チームアルゴリズム(とくにMPI化したところ)をここに書き込まないか?
3チーム以上の同意があればやろうとおもうのだが・・

>>99
とりあえず、うちのチームはOKです。


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

トリップ付けるん忘れとった・・・

>>100
勉強汁

ってか夏の課題終わらねぇ・・・

大阪人の口調真似はむりぽ

>>93
合宿行ってて今日帰りました。明日、即で送ります。

>>99
MPI化してないです（笑。ソースはチームメイトが持ってると思う。

>>102

漏れは大阪人ではない罠・・・

>>103
乙

やっとこのスレみつけたよ。

SuperCon終わったんで、しばらくパソコンは封印して算数ヲタにでももどろうかな。
けれども来年こそは３位入賞めざしてがんばるます。

>>ギタリスト
よければPCでも携帯でもいいのでアドレス教えてください。

封印30秒でといてしまった漏れ

>>105-106
みんな辿る道は同じなんだな（笑）

物凄い外れるが、いつHPの写真うｐするんや・・・


ってかまず何より好きな素数・元素・法則の奴が早く知りたい・・・ｗ

>>105
メアド教えたいのはやまやまなんだけど2chで晒すの痛いなぁ・・（−−；
>>108
の言ってるアンケート結果が配られればいいんだけど。。。

>>100
ワードバスケットのサイト発見･･･一瞬で見つかる。。
>>109
見事思うことは同じだな･･･アンケートは渡辺(だっけ)の好奇心と思われ
お互いの学校すら晒せればみんなのアド網を伝っていけるだろう･･･
算数オタは少ないだろうから各学校に聞きまわれば繋がるはずダ
みんな協力シヨー

ま、算数ヲタの検討ならついとるがな

昔は IRCで #sc2001とか,#sc2002とか立てて
いろいろ連絡とりあえってたり
Supercon-mlなんてのもあったんですけどね。
最近はアナウンスすら流れませんね。
俺がMLからはずされただけなんですかね。

そこんとこどうなんですかSGIのサカモトさん!!

メーリングリストか・・・

勝手にFreeMLとかでつくってしもていい？

いいぽ

昔のMLもはや反応なしくせえ

>>114

そうやな、裏SuperConがあるけどもうだめみたい（ぉ



というか本物のdemekingさん。コテハン語ってすいませんでした。
けれどもわかりやすいトリップはやめたほうがいいっすよ。

>>115

[email protected]っていうMLがあって、坂本さんとかもいるんだけど
どうやって新規参加誘えばいいのかかわからんし新規参加も０って状態っすわ

一年に一回だけだから、どうも興奮が冷めちゃうのかな？
俺は今年のレポートが聞きたいです

やっぱりわかりやすすぎかｗ
ホンモノです。算数ヲタに指摘されたのでトリプ変えます。

Wiki置いて放置とかじゃダメだよな。
＃それ以前に本選問題が知りたかったりもしますが・・・

本選問題･･･頑張って挙げましょうか･･･
というかいいんでしょうかサカモトさん!?

ちょっちまって。> 問題公開

公開されたよ。

>>110
いや、>>100のリンクは、ワーバスオフィシャルサイトの「販売店リスト」なんですけど……（汗
とりあえず、ワーバスは有隣堂横浜西口店にも、ルミネ店にも、関内本店にも売ってませんでした。
諦めて、永岡書店の通販を使う事にします。

……何か負けた気分。

なんか本選結果みるとがっかりするなぁ。
あと３位の色が目に痛い。


あとdemekingに指摘はしましたが偽者は僕じゃないですよ（＾＾；

んーとつまり、128bitのRSAというか
掛け算を全力でしまくるということ？

並列化とかできんのか？
分担するピクセルを分けるくらいしか思いつかないが。

ピクセルごとに分担させて、hardness順に処理してく。

けれどもそれじゃぜんぜん話にならない。
たしか　a^e * b^e = (a*b)^e (mod n)　を利用する。
実はこれで掛け算だけでなく割り算もできる。
仮に割り算ができないならばそれはnの素因数を見つけたことになるのでOK。

とかでhardness=20あたりになってとても小さな素因数をひとつみつけられるような値がくるらしい。例えば２とか３とか
でそれが見つかると急激に正答率が上がる仕組み。

ありゃま、ちらっと見てみたけど随分複雑そうな問題で^^;
とっさに思いついたので晒してみる。解法が違っていたらスマソ。
＃d[rsa](x) = d(x) , e[rsa](x) = e(x) , mod n は略

処理１：
m[x] = d(c[x]) 両辺をe() で括って、
e(m[x]) = e(d(x)) <=> e(m[x]) = x <=> (m[x])^11 = x
となるので、hardnessの小さい順にm[x] を求めて暗号を解く。

処理２：
m[x] * m[y] = d(x*y) , m[x*y] = d(x*y)
<=> m[x] * m[y] = m[x*y] の式変形を利用して、
判明したm[x] を掛け合わせて出来る数の暗号を解く。
例えば、m[3],m[5] が判明しているのなら、
(m[3])^1*m[5] = d(3^1*5) <=> m[3^1*5] = (m[3])^1*m[5]
(m[3])^2*m[5] = d(3^2*5) <=> m[3^2*5] = (m[3])^2*m[5]
(m[3])^3*m[5] = d(3^3*5) <=> m[3^3*5] = (m[3])^3*m[5]
の式変形のように、次々に判明していく。

この方法だと、rank==0がまだ判明していないm[x]をrank!=0に
配分していく処理が定番になってくるのかな？
＃RSA暗号についての知識が足りないとやっぱり難しいな、うん。
＃全部Whiteに設定して出力するという保険考えたけどダメぽorz

正午ごろ、これの第一稿を書いてたらブレーカーが落ちました。
なので、これを書くの二度目です。
頼むから今度は落ちないでくれ。ブレーカー……

んで、うちのチームが使った方法ですが、

>>125-126とは違う方法で並列化しました。
各CPUにそれぞれ別のピクセルを処理させるのではなく、一つのピクセルを全てのCPUを使って処理するようにしています。
どうやっているかというと、例えば、hardness20のピクセルを処理する場合、hardness+(0〜2^20)の値についてしらべなければいけません。
そこで、この2^20個の値を、64×CPUごとにブロック分けします。
（CPU数４個の場合、第一ブロックは、hardness+(0〜255) 、第二ブロックはhardness+(256〜511)、第三ブロックはhardness+(512〜767)、という風に）
そして、全CPUを使って一つのブロックを処理します。
（最初に処理するのは第一ブロックですが、その時各CPUは、４で割ると「０余る値」「１余る値」「２余る値」「３余る値」をそれぞれ処理します）
各ブロックの処理が終わるごとに、MPI通信を行って答えが求まっているか否かを調べます。そして、答えが求まっていた場合、全プロセスで答えを共有します。（全プロセスで共有するのは、>>126で書かれている処理２を、MPI通信をする事なく行うため）
以上の方法は、Hardnessが大きくなれば、うまく機能するでしょう。

……ちなみに、hardnessが低い時には、この方法は無茶苦茶遅くなります。
その事に気付いたのは、表彰式前日の夜でした。

その他の工夫については、また今度。
長文駄文失礼しました。

今、>>127が無意味に偉そうな文章である事に気付いた。
ちょっと＿|￣|○してくる。

>>128
そういえばしばらくパソコン触らんっておっしゃってましたけど･･･
絶対に帰ったその日にメールチェックしたでしょ？？？

>>129
……はい。しました。
っていうか、>>107は俺です。
現在、パソコン恐怖症は完治し、毎日勉強してるわけじゃないのに毎日パソコンはしているという、非人間な生活を行っています。

……やばいのはわかってる。
つっこまないで欲しい。

>>130

パソコン恐怖症治ったんやｗ
ある意味ｵﾒ

ゐ�`
漏れも毎日勉強なんてしてないからさ
（リーダーがこの頃怖いのはかなりの率でその所為と思われｗ）

洒落にならない致命的エラーを発見しました･･･
私がデバッグの時に書き換えたところでした･･･
すいませんチームの皆さん･･･
こんなエラー誰にもいえません･･･
すいませんホントに･･････

>>132
そう落ち込むなや。
いまさら悔やんでも仕方ないさ。

rank==0 が他の rank に m をばらまくけど、その hardness が例えば 12 より
大きいときは、hardness=12 に分割してばらまく。126 と 127 の中庸の道。

うちはhardness20づつに分割したかな･･たとえばhardness21の数は2プロさっせで処理して、
最小値0、最大値2^20-1をひとつに送り、もうひとつには最小値2^20、最大値2^21-1を送る。
ただ処理の途中で、masterに他のプロセッサで処理が終わってるかを聞きにいく。。
もちろんどこかですでに終わってたら次の数をもらう。。
マスクされてる値を見つけたプロセッサは、それをmasterに送り、すでに見つかっている数一覧をもらう。
そのことによってc1*c2=c3の式が使える。。んで計算し尽くしたら、masterにそれを送り返す、と。。
若干のタイムラグによって厳密に全てのc1*c2=c3をやっているわけではないけど、
いいかなぁと思ってやったら、予想以上にタイムラグが大きかったみたいで撃沈。。
乱文スマソ

c2*c3=c6 の計算は master のみでやってもよくない? slave でやると
master-slave 間の通信がえらい複雑になりそう。

そろそろ寂しくなってきたのでカキコ

bignum関連の関数の高速化次第で大きく結果が変わって来そうな内容だな。

__cdecl だとスタック格納したりとか色々あって速度出ないから、
bignum関連の関数をinline や __fastcall にして再定義してみたりとか。
それでも遅くて、bignum madd(bignum a,bignum b) { return (a+b)%n; } を、
bignum my_add(bignum *a,bignum *b) { (*a)+=(*b); } という風に変えたり、
#define で関数群を作成してみたりとか。
supercon.c , supercon.h の内容を見ないと一概に何とも言えないのが痛いorz

bignum solve(int c,bignum rsaN,bignum rsaE,int hardness,bignum hint) {
int i,j;
int max = 1 << hardness;
for(i=0;i<max;i++) {
bignum tmp1 = madd(hint,i,rsaN);
bignum tmp2 = tmp1;
for(j=1;j<rsaE;j++) {
tmp2 = mmul(tmp2,tmp1,rsaN);
}
if(tmp2.h == 0 && tmp2.l == c) return tmp1;
}
// printf("err: solve()\n");
return rsaE;
}

げ、早速ミス発見orz。rsaEを11と置き換えた方がいい気がするなー。
×for(j=1;j<rsaE;j++) {
○for(j=1;j<rsaE.l;j++) {

結局rsaE=17になりましたから
for(j=1;j<rsaE;j++) {
tmp2 = mmul(tmp2,tmp1,rsaN);
}
を
tmp2= mmul(tmp2,tmp2,rsaN); //BASICSTYLE:tmp2=tmp1^2
tmp2= mmul(tmp2,tmp2,rsaN); //BASICSTYLE:tmp2=tmp1^4
tmp2= mmul(tmp2,tmp2,rsaN); //BASICSTYLE:tmp2=tmp1^8
tmp2= mmul(tmp2,tmp2,rsaN); //BASICSTYLE:tmp2=tmp1^16
tmp2= mmul(tmp2,tmp1,rsaN); //BASICSTYLE:tmp2=tmp1^17
ってかんじでしょうか・・・？

http://www.itmedia.co.jp/enterprise/articles/0408/23/news011.html
記事が出ているね。

麻布パソコン部、国の威信を守ったかどうかはともかく、
東大進学の勉強と平行してプログラミングをやっているのに中国ナショナルチームに勝つ底力はたいしたもんだ。

rsaE=OxBになっとるがな

誰かカケー・・・ｼｮﾎﾞﾝﾇ

最後に撮った集合写真、現像が終わり次第、各チームリーダーの家に送るって言ってたよね。
アレ、いつ頃になるんだろうか？

東京MXテレビの画像も気になるし。

そうだよねぇ・・・８月中に好評をUpするって書いてあるけどまだみたいだし。。

http://p9c.cc.titech.ac.jp/jobs/tmp/sc04/funsheet.html

ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !

やはり逝ｯﾄﾘｳﾑを書いたのは俺だけか。元素占いの結果なんですｗ

>>147の言う　元素占い。
http://home.interlink.or.jp/~tsark/genura.htm

ちなみに計算式は(109-28*Year-9*Month+Day)%109な。

ちょっと試してみたんだが、
本選問題の素因数分解もfactor.exeにかかれば２秒なんだな。

仮にこれができたら確実に優勝だったな。

内部的にfactor.exe呼び出してたらぶん殴られたかな？
本選で。

100bit 整数の因数分解が2秒ってほんと?
factor.exe のアルゴリズムはなに?

パイナポー好き民族１票ｷﾀ━━━(ﾟ∀ﾟ)━━━!!!
俺最終日チームメイトと鬱ってる写真が(ry

しかし、8/5(2)はサムネイルとリンクがあってないぞ。
なにしてんだろう。

http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/howto.htm

これですね。factor.exe
多分、アセンブラ、MMX他でギッチギチに最適化してるんだろうけど、それにしても凄い……

どうでもいいが、

・ bignum をビッグニュムと読むチームメイト
・ 水をガバガバ飲むチームメイト

両方とも、俺の事じゃねえか……
F井もM永も、何考えてやがるんだ……

>>155
水を飲むのはいいことですな。。
風邪引いたら一日15L飲みますわ。。

http://www.gsic.titech.ac.jp/supercon/supercon2004/kaisetsu/index.html

本選の詳細な講評も来ましたね。
「４：最後の手段！？補間法」か……
「やって欲しく無い方法」だったみたいだ。
……うちのチームは、補完法だけで正答率を「２０％以上」上げてしまったわけですが。

http://www.itmedia.co.jp/enterprise/articles/0408/23/news011_2.html
の画像を見る限り、うちのチームと同じ位、補完を派手に使ってるチームは「nagater」だけのような気がするけど、どうなんだろう。

nageter平澤ですがー始めは補間法もっと派手に(さらに派手に)使う予定でしたがやめましたｗ
最終的にはまわりの８マスを見て、決定されているマスならwhite++;またはblack++;して、
white>=blackなら･･･といったような感じでやりました。。
あ〜割り算は時間かかるだろうと思ってあきらめていなければ(後の祭りw)

剰余類の逆数を使ったチームがnumeiとchinaだけだとあるけど
他に使ったチームなかったのかな？
それが本当なら俺のチームの伝播は失敗していたというわけだなorz

#define 伝播 電波
と置きたくなるのは関西人だけ･･･？

>>旅人達さん
>>始めは補間法もっと派手に(さらに派手に)使う予定でしたがやめましたｗ
……それじゃあ、派手に補完法を使ってるチームは、うちだけっぽいです。
うちのチームが使った補完法は……

１つめの処理：
まず、0〜（2の16乗）までの値の中から、既に正確な値の求まっているドットを検索して全て見つけます。
そして、正確な値の求まっているドット全てを、「フラグの立っているドット」という事にします。

２つめの処理：
全てのフラグの立っているドットの回り（上下左右の４ドット）のうち、フラグの立っていないドットを全て、フラグの立っているドットと同じ色にします（以下、ここで色を変更したドットを、「仮のドット」と表記します）。

３つめの処理：
仮のドットが一つでもあるなら、「４つめの処理」を行います。
仮のドットが一つも無いなら、補完プログラムを終了します。

４つめの処理：
仮のドット全てを、「フラグの立っているドット」という事にします。
そして、「２つめの処理」に戻ります。

……以上が、最終日の数時間で組んだ補完プログラムの、全貌です。
このプログラムは、「既に白色だとわかっているドット」と「既に黒色だとわかっているドット」の丁度真ん中に白色と黒色の境界線を作るようになっています。
白黒画像だから出来た力技だね……

>>#define 伝播 電波
それは、ハマっ子である俺も同じ。
……伝播の読みがわからなかったのは秘密だ。

sakamoto さんの ksh の設定ファイルはどこで手に入りますか?

適当にbmul()の最適化してみたら、2.5倍速ほどになった気が^^;
まぁ、VC++上で、#define long __int64 とやって実行速度測ったので、
スパコン上だともっと遅くなる気がしないでもない（ぇ

まだまだ早くなると思うので、高速化に挑戦したい人がいたら是非とも（何

// bbmul() , bbrem() はSuperCon.c よりコピペしてください。

#define MY_MASK0 (0x8000000000000000L)
#define MY_LMASK (0x00000000ffffffffL)
#define MY_HMASK (0xffffffff00000000L)
#define MY_HALF (32)
#define MY_MAX (0xffffffffffffffffL)

bignum my_mod[2];

// 初期化ルーチンぽ
void my_init(bignum n) {
bignum tmp_h,tmp_l;
tmp_h.h = 1; tmp_h.l = 0;
tmp_l.h = 0; tmp_l.l = 0;
my_mod[0] = bbrem(tmp_h,tmp_l,n);

tmp_h.h = 0; tmp_h.l = 1;
tmp_l.h = 0; tmp_l.l = 0;
my_mod[1] = bbrem(tmp_h,tmp_l,n);
}

// bbmul() の簡易バージョン
void my_mul2(bignum x,unsigned long y, bignum * zH, bignum * zL) {
unsigned long xhh, xhl, xlh, xll;
unsigned long ylh, yll;
unsigned long z0, z1, z2, z3;
unsigned long z1a, z2b, z3c;
unsigned long zHla, zHlb, zLha, zLhb;

xhh = (x.h & MY_HMASK) >> MY_HALF;
xhl = x.h & MY_LMASK;
xlh = (x.l & MY_HMASK) >> MY_HALF;
xll = x.l & MY_LMASK;

ylh = (y & MY_HMASK) >> MY_HALF;
yll = y & MY_LMASK;

z0 = xll * yll;
z1a = xll * ylh;
z1 = z1a + xlh * yll;
z2b = xlh * ylh;
z2 = z2b + xhl * yll;
z3c = xhl * ylh;
z3 = z3c + xhh * yll + (z1 < z1a);

zL->l = z0 + ((z1 & MY_LMASK) << MY_HALF);
zLha = (z1 & MY_HMASK) >> MY_HALF;
zLhb = zLha + z2;
zL->h = zLhb + ((z3 & MY_LMASK) << MY_HALF) + (zL->l < z0);
zHla = (z3 & MY_HMASK) >> MY_HALF;
zHlb = zHla + xhh * ylh + (z2 < z2b);
zH->l = zHlb + ((z3 < z3c) << MY_HALF) + (zLhb < zLha) + (zL->h < zLhb);
zH->h = (zHlb < zHla) + (zH->l < zHlb);
}

// mmul(x,y,n) の高速化バージョン（？）
bignum my_mul(bignum x,bignum y,bignum n) {
int cf1,cf2;
bignum ans_h,ans_l;
bignum tmp_h,tmp_l;

bbmul(x,y,&ans_h,&ans_l);
while(ans_h.h) {
my_mul2(my_mod[0],ans_h.h,&tmp_h,&tmp_l);
cf1 = (ans_l.l > MY_MAX - tmp_l.l ) ? 1 : 0; ans_l.l += tmp_l.l;
cf2 = (ans_l.h > MY_MAX - tmp_l.h - cf1) ? 1 : 0; ans_l.h += tmp_l.h + cf1;
cf1 = (ans_h.l > MY_MAX - tmp_h.l - cf2) ? 1 : 0; ans_h.l += tmp_h.l + cf2;
ans_h.h = tmp_h.h + cf1;
}
while(ans_h.l) {
my_mul2(my_mod[1],ans_h.l,&tmp_h,&tmp_l);
cf1 = (ans_l.l > MY_MAX - tmp_l.l ) ? 1 : 0; ans_l.l += tmp_l.l;
cf2 = (ans_l.h > MY_MAX - tmp_l.h - cf1) ? 1 : 0; ans_l.h += tmp_l.h + cf1;
ans_h.l = tmp_h.l + cf2;
}

cf1 = 1;
while(!(n.h & MY_MASK0) && (ans_l.h > n.h || (ans_l.h == n.h && ans_l.l > n.l))) {
n.h = (n.h << 1) | (n.l >= MY_MASK0);
n.l = n.l << 1;
cf1++;
}
while(cf1--) {
while(ans_l.h > n.h || (ans_l.h == n.h && ans_l.l >= n.l)) {
ans_l.h -= n.h;
if(ans_l.l < n.l) {
ans_l.h--; ans_l.l = MY_MAX - n.l + ans_l.l + 1;
} else {
ans_l.l-= n.l;
}
}
n.l = (n.l >> 1) | (n.h & 1 ? MY_MASK0 : 0);
n.h = n.h >> 1;
}
return ans_l;
}

>>155
factor.exeダウンロードしてみたらすごい･･･
本当にRSAが安全なのかを疑うぐらいすごい･･･
ということで今年中の目標はスペシャルな素因数分解プログラムを作ることw
でも数体ふるいの説明してるサイトって無いんですよね･･･
nfs_intro.pdf以外でご存知のものありましたら教えていただきたく･･･

>>168
……私にはｐ−１ methodすら理解できないわけですが……
数対ふるい法、一応ググってみましたが、そのpdfファイル以外には見つけられませんでした。
……もちろん、私には理解不能でした。

健闘を祈ります。
頑張ってください。

本番では楕円曲線法までは実装したんだがそのときは128bit整数じゃ
計算途中のサイズが足りなくて、16bit程度の値しか素因数分解できなかった。
他の方法でも計算中に128bitの範囲を超えるんじゃないかな？

>>169
p-1methodとやらは分かりませんが、なぜかnfs_intro.pdf内の定数倍法を必死に理解しようとすると
直説法と2次ふるい法が分かりまして･･･ｗ
>>170
楕円曲線法が分からないんですけど、２次ふるい法なら大丈夫ですよ。。
最後に公約数を求めるので、そのときだけ128bit超えますが。。
演算が遅くてもほとんど問題ないので多分できるのではないかと思います。。

>>162
｢質問のある諸君は、放課後職員室まで来てください｣
と言ってましたよ。
教えてくれるそうです。

600�`先なんですが/ｷﾆｼﾅｲ

台風来てから電柱の変圧器がおかしいみたいでよく停電するんですが･･･

>>174
そ、それはやばくないか…？
ブレーカーが飛ぶとかじゃないなら、
電力会社にｺﾞﾙｧしたほうがよろしいのでは？

昼間にドカンという音がして向こう三軒両隣(古っ)の人々が
飛び出してきたらしい。。母によると。。
無停電電源装置とか言うのｷﾎﾞﾝ

今何人くらいこのスレウォッチしてるの？

>>176
http://www.kakaku.com/sku/pricemenu/ups.htm

>>177
とりあえず今私が3人目ｗ
nomeanの水飲みさんがいない･･･

>>178
無停電･･･って一万円もするんだ･･･ｻﾝｸｽ..

パソコン復活☆

俺いるよー。

今日、F井から最終日に撮った集合写真を渡された。
……俺、右手に何かを持ってる。
……何持ってたんだっけ。記憶が無い。

ま、とにかく、いくらなんでも、そろそろ真面目に勉強しないと周囲から非人間の扱いを受けてしまう時期なので、しばらくここには来ないかもしれません。
……来年の３月くらいになっても書き込みがなかったら、色々と察してあげてください。

では。

頑張ってくださいー☆
右手･･･エビフライにしか見えません（ぇ

ｳﾜﾝ( ･д⊂ヽ゛

現在、「自己推薦のレポートを書くために」パソコンを起動中。
息抜きって事で、こんな所に遊びに来てみる。

先日、来年のスパコンに出る予定だった子（現中３）が、俺に「僕、来年のスパコン、やっぱ出場できないかもしれないです」と、言ってきた。
「何が起きた」と聞いてみると、「親が、2005年夏休み、７月末〜８月初頭にかけて、海外旅行計画に行く計画を作ってしまった（飛行機とかは予約済み）」らしい。

……来年、本選開催日時が夏休み始まってすぐor８月下旬に変更になる事を祈る。

来年3年生だから8月末はきついですねぇ･･･
たぶん坂本さんも見てるはずだし･･･7月末にしてください☆
そういや終わってからのパーティーで誰かが言ってた、
来年は中国で開催するっていうのは本当なんでしょうかねぇ･･･
学校からそこまでお金が出るかどうか･･･でないだろうな>_<;

中国のほうにすごいスパコンがあるんなら逝くけど・・・

７月末は学校の補習があるだろうなぁ
ぜひ７月末にｗ

ここを見てあの人は(ry
中国でスパコンがあって俺がついて行けるなら、俺は初めての外国体験になる訳かｗ
確か主催が東工大だった気がするから中国ではしないと思われるが・・・

何よりnomeanの後釜氏が「スパコン(本選だと思われる)に出る予定」なのがすごい…

俺、事後処理に未だ追われているんですが…(涙)

スパコンランキングってのがどこかのサイトにあったんだけどリンク忘れた･･･>_<;
東工大も4年ほど前は数十位だったけど今は300位ぐらいだったような･･･
まぁすべてのプロセッサを並列処理できると仮定して、の話だから実際はわからないけど。
まぁ当然のことながら地球シミュレータが1位でつた

http://top500.org/list/2004/06/

>>187
いや、後輩がスパコン本選に出れるかどうかは、わかりませんが……
ただ、スケジュールの都合で本選に出れないのが最初からわかってるなら、スパコン予選にも応募しないのが礼儀なわけで。

「スパコンに出る」は、「予選に応募する」って意味で書いたつもりでした。
今後は、誤解されるような事は書かないよう、気をつけるようにします。

私は来年も予選通過しますよ!!問題は誰か手伝ってくれないですかねぇ･･･
おそらく今年同様一人じゃ出れないでしょうから。。
進入部員の募集を頑張りましょうか･･･ｗ
>>189さんありがとうございます(*´∀`)

地球シミュレータがついに抜かれてしまったようですね。。。
東工大にはそれにも勝るスパコンを(ry

そういえば、LinuxMagazine10月号にSuperconの写真が出てたぞ。



もう店頭には11月号が並んでいるわけだが…。

http://linux.ascii24.com/linux/linuxmag/
ちょっと高いね･･･>_<;
けど買いに行きたい･･･

NEC＼(^O^)／ヤッター
ttp://headlines.yahoo.co.jp/hl?a=20041021-00000011-nkn-ind
（yahooだからリンク切れするけど堪忍）
ＣＰＵメモリー間のデータ転送速度が最大毎秒２６２テラバイトだってさ･･･

すごいなぁ、１１７万か

http://pcweb.mycom.co.jp/news/2004/10/27/007.html

SGIが横から掻っ攫っていきましたとさ

関連スレッド＠科学ニュース+板

「地球シミュレータ」の50倍、2PFLOPSのスパコン国内開発へ
http://news16.2ch.net/test/read.cgi/scienceplus/1085837914/l50
IBMのスパコン、地球シミュレータ超え最速に
http://news16.2ch.net/test/read.cgi/scienceplus/1096451444/l50
【ＩＴ】世界最速65TFLOPS　NEC「SX-8」発表(04/10/20)
http://news16.2ch.net/test/read.cgi/scienceplus/1098264131/l50

2PFLOPSなんて可能なものなの･･･?
1秒間に100万回が100万回あるわけでしょ･･･w

もう落ちたかと思った･･･危ない危ない･･･保守保守･･･
なんか70GFLOPSを超えたらしいですねぇ･･･

並列でいいなら、あとは数の問題だからねぇ。金持ちが勝つ論理です。>>199

OHS記念ﾊﾟﾋﾟｺ
とりあえずあれだ、

ぬるぽ

がわかるってすばらすぃ。
むしろ今まで知らなかった漏れは回線切手くb(ry

保守

age

もうそろそろ今年の話題は終わりかな・・・

学校のパソコン室(?)の44台をつないでmpichとか走らせてやりたいって
顧問に言ったら3秒後に無理だって言われた･･･ﾝﾇ

http://kagakububuturi.hp.infoseek.co.jp/
広島国泰寺高等学校の物理部（？）がすごいことやってるぞ。

ありえん・・・キモイ・・・
いや、すごいです。。すみません*_*:
ってかほしいなこのCDとソース。。

保守保守。

年末保守

数学セミナー１月号にスパコンの記事発見。

public class DQN extends SUPERDWN{
int baka,aho;
if (baka==aho){
System.out.println("あなたはDQNです")
else{
System.out.println("あなたは正常です")
}
}

なぜ4ヶ月も経ってからなんだろう･･･
とりあえず立ち読みしてみる･･･

明けちまったぞ（*ﾟДﾟ）ﾓﾙｧ!!おめで�d

今年も本選で会おうではないか。

UNIX板より

60 名前： 名無しさん＠お腹いっぱい。 [sage] 投稿日： 04/11/15 19:05:26
東・工・大！
東・工・大！
61 名前： 名無しさん＠お腹いっぱい。 [sage] 投稿日： 04/11/15 23:28:51
本館がロボットに変形します。
62 名前： 名無しさん＠お腹いっぱい。 [sage] 投稿日： 04/11/16 01:13:19
本館は表向き綺麗だが・・・
裏側は、かなりボロい箇所がちらほら。

おい友よ!アンケート結果のリンク見てふと気づいたんだが
http://p9c.cc.titech.ac.jp/jobs/tmp/sc04/
にいろいろなファイルがあるぞい。
文化祭用にいろいろ関数作ってた俺はなんなんだよorz

みちゃいやん。tmp だからもう消すよ? 必要な人はみんなコピーした?

ﾄﾞｿﾞｰ
ttp://www.gsic.titech.ac.jp/supercon/callforproblems.html

うおー、久しぶりに覗いてみたらまだスレ残ってる…。

受験勉強の真っ最中に
SuperCon出場したﾔｼなのだが、
滑り止めの合格発表が全部終わったよ。
結果は見事合格。
後は第一志望に向けて頑張るだけだ。

勉強かったりーってことも時々あったけど、
本選の、なにやら凄そうなメンバーの中に、
自分も混ざっていたのを思い出して、
自分もやれば出来るはず、
そう思ってコツコツここまできたよ。

あの時貰った某バックは、
お守り代わりに受験会場に持っていっている。
下手なお守りより勇気付けられるよ。

んでその第一志望なんだが、
　
　
　
　
　
　
　
　
　
　
ｺﾞﾒﾝ東工大はやっぱり無理だったorz
SuperCon主催団体はダテじゃない…。

ハンドルネーム変更……トリップはそのままで。

>>220
……こういう事って、かぶる物なのだろうか？
俺も今日、なんとか滑り止めに受かった。
滑り止めすら、ダメだった学校があるという体たらくだけど（苦笑）
第一志望、受かるよう、お互いがんばりましょう。

俺も、国立受験日にはスパコンで貰った名刺入れ持って行こうかな……
お守り代わりにするなんて、今まで全然思いつかなかった。



ところで、誰か>>219に応募した人っている？
俺、ちょっと送りたい問題があるんだけれど……
俺では何一つ有効な解決法を見つけられなかった問題が。

漏れも久しぶりに書き込んでみる。


受験生ｶﾞﾝｶﾞﾚ(ノﾟДﾟ)八(ﾟДﾟ　)ノ
って言うか入賞したんだからいけるさ、水飲み氏よ。(倒置法)



すごいどうでもいいことだが、漏れクラス文集で
曲がり角で知らない人とぶつかって、落ちたものをとろうとして手が重なるような出会いを期待してそうな人2位ですたorz

OK簡素に

「受かった」

そんな某出場3年生。
おまいらのお陰で勇気付けられたとこもあるぜ。

>>223
激しくおめ。

浪人したのに現実逃避しまくりで学力上がらなかった馬鹿がここにいます。
＃前期落ちましたorz

>>219
応募しても個人情報特定されて恥ずかしいので、ここで晒すことにする。
現実逃避の対象になっている某プログラムがネタ元なのは秘密。

＊平面座標に配置されている約１００万個のオブジェクト(それぞれに質量が設定されている）
　の中から、指定した座標群で作るポリゴンの内部にあるオブジェクトの質量の和を求めよ。
　座標、質量は n < 2^24 を満たす自然数とし、質量の和はdoubleで求めるものとする。
　ただし、オブジェクトの座標群はプログラムの実行時に１組だけ与えられ、ポリゴン座標の
　組は問題ごとに変わるものとする。

関数群

// オブジェクトの一覧を返す。戻り値 0 = 失敗 その他 = 問題数
int supercon_get_object(int *count,int *x[],int *y[],int *mass[]);

// ポリゴンのリストを返す。戻り値 0 = 成功 1 = 問題番号ミス 2 = その他エラー？
int supercon_get_question(int question_number,int *count,int *x[],int *y[]);

// 問題の解答を返す。
void supercon_ans_question(int question_number,double mass);

同じく前期落ちた。
しかも、後期は違う大学を受ける。
……まぁ、例の某無名私立大学でも満足できるアレな人間なので、精神ダメージはたいした事無いのですが。

>>225
ここで問題を公開したら、その問題は本選で使えなくなってしまうのでは……

>>225
大して難しくもない希ガス

なんか復活してますねぇ･･･
問題公開しても、向こうが手を加えるから大丈夫だと思いますよ？
ポリゴンを立体座標にすると、大変だけど面白くなる気が☆
あと重心を求めよとかいうのも･･･計算するだけですけど↓
試験後になりましたが･･･３年生の皆さん吉報を期待しております(*´∀`)

来年は漏れら・・・
ｶﾞﾝｶﾞﾚ漏れorz

このｽﾚもう役目を終えたんだな・・・

来年は2005のスレが立つのかなぁ・・・

保守orz

そろそろ2005のHPキボンヌ

激しく2005キボンヌ。。
去年って6月5日ぐらいに課題発表だった気がするんだが･･･？？
坂本さんー、、今年も出ますんでお願いしますf^ ^

お。がんばってこいよー

2005ｷﾀ━━━━━━━━━━(ﾟ(ﾟ∀(ﾟ∀ﾟ(☆∀☆)ﾟ∀ﾟ)∀ﾟ)ﾟ)━━━━━━━━━!!!

http://www.gsic.titech.ac.jp/supercon/supercon2005/index.html

って・・・更新日が明日になってるのでまだ去年のトップページの
ままの内容ではありますが。。ロゴが新しくなっててうれしい☆

予選課題発表6/6で、予選締め切りが7/7です。みんながんばろうぜぃ

一応･･･予選が円滑に行われるようsageて行きませう。。。

http://www.gsic.titech.ac.jp/supercon/によると、

『スーパーコン甲子園〜プログラミング大好き高校生たちの挑戦！』
日本評論社 2005年6月15日刊行予定

だそうな。。

>>237
一体、何を載せて本を作る気だろ？
本に載せれるようなネタは、全部ホームページに載せちゃってるじゃん。写真とか、アンケートとか、優勝チームのソースコードとか。
（そういうのが載ってるだけの本でも、買う人はいると思うけど……）

漏れの大活躍が載るに決まｔ(ry

今年の予選課題出たな

問題からして楽勝、、、、と思ったのに。。。

東工大学部生もでれるのか
でてみようかな

高校生に負けないようがむばってくへ

これは楽勝だな・・・
またレポート審査か。

楽勝なんだ…ありえねぇよ↓
とりあえず今のとこランダム生成した80000文字が60秒…みんなは??
たぶん244は3秒とかなんだろうなorz

1文字の繰り返しも含むのかな？
i<=jというからには含みそうだが。

Q&Aをミロのビーナス

ちなみに計算量はnlog(n)
メモリ量は線形でいける

計算量は非線形だな

僕は高校生じゃないから関係ない者なんだが、（どっちかっつーとNEET。OTL
簡単な実装を考えてみた。
C標準のstrstrを改造した、strnstrを作成。
そして、総当りする。
多いほうからやるのがベターなのかどうかはわからないが、後はアイディアだな。
試してないのでちょっと作ってみるか。

ところで、これって文字列じゃないのね。
文字列に変換するコストが馬鹿にならんので、strchrもどきも自前か。
ちょっとやってみよ。

総当りで3分切るのは苦しいだろう。さすがに。

総当りモドキ作ってみた。
正直遅い。
しかも、いろんな長さを試験しないといけないのに、
一つの長さを試験するだけで1時間かかるかも・・・・。(1000個で約50秒だった。
1Ghzでこれだけかかるのは正直勘弁・・・。（コンパイラも最適化できればもちょっと早くなるんだろうけどね。
-*-*-*-*-*-*-
100kを試験中。
3分どころか現在BGMに流してる曲は今、何ループ目だろう・・・。
あーなげー。（TT
*-*-*-*-*-*-*-
終わってみると70分かかってました。
これが100k回繰り返されるとすると
・・・800年？？
んナあほな。

偏った乱数を使わないと試験があってるかちょっと不安になるな〜。

とりあえず、今日の成果物。徹夜しちゃった。

http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/533.txt

改良の余地あり。（旨くすれば3時間以内に総当りできそうな感じ。
メインで走ってるBruteForce関数がちょっときちゃない。そして2重ループなので遅い。
もうちょっとコンパクトにしたいけどいい案が思い浮かばない。

使用法はmain()のなかのBruteForce呼び出しの最後のマジックナンバーをいじるとそれに沿った内容で実行します。
小さい数ほどヒットしやすいのかな？？

1Ghzのマシンで1時間ということは最近のマシンなら3倍ってことで20分でおわるかなー。（というか800年か。
まー、一度破棄して作り直したほうが早いかもね。（ＴＴ
3分だしね。

くそー、O(n^2)までしか思いついてないから3秒くらいかかる。。
O(nlogn)にする方法考えたほうがよさげ。

>>255
個人的には、一応まだ締め切りきてないからあんまり公開しないほうがいい気がする。

>>256
うは。
はえー。

俺も総当たりでやってみました。
ランダムに生成した10000文字で3秒。
総当たりでも行けるんじゃないですか？
一応高校生なんで応募しますが。

5000文字…2秒
10000文字…3秒
50000文字…80秒
100000文字…313秒
・・・駄目だ、O(n^2)だ。
他にどんな方法があるんだろう・・・

つ[ヒント：分割統治]

作ったソースとかヒントとか出すのやめようぜ、最低限のことは守ろう。。

つ[ヒント：randomize]

つ[ヒント：動的計画]

3回以上の繰り返しが合った場合に効果あるように、一度比較したところはスキップするようにしたんですけど、（リストで）
逆に遅くなりました・・・。

つ[ヒント：素因数分解]

>>265
関係ねーだろｗ
それにしてもムズいな

なんか削除依頼が出されてるぞ、なんなんだ？

http://qb5.2ch.net/test/read.cgi/saku/1098189517/74

依頼したのは俺ではないが、コンテストに不公平が出たら主催者側に迷惑がかかることを考えれば、削除してもらえるならしてもらった方がよいのでは？
その方が、コンテスト参加者も気分いいはず。

解法わかっていてコンテストに参加しない人は解法をいいふらしたくなるかもしれないけど、
ここはぜひ、締め切り直後にばしばし書き込んで誇示する程度にしてもらいたい。

>>258
1万で3秒だと10万ではなぁ…
それともtypo？

>>251
標準入力から受け取るんだから文字列だろ
問題文字列って書いてあるし

>>266
文字列を分割していって長さが素数になったら・・・

素敵になります。

標準入力ってscanfだろ？
どうやって100000文字も入力するんだろうな・・・
ファイルから読み込んだ方がいいのに。

>>269
typoじゃないけですど・・・
今ちょっと改良して、100000文字が3分を少し切りました

>>273
リダイレクトを使えば簡単

目標タイムは何秒か？

10ms

・・・マジ？

んなばかなw
どんなにがんばっても1秒が限界だろう。。
正直アルゴリズムにはすごく自信あるけどそれでも今18秒。
俺より速い香具師は1人ぐらいしかいないと思われ。

ttp://zeroichi.ddo.jp/diary/
ぐぐったら出てきた。
ランダムな100000字で1秒だそうだ。
凄い。

ランダムな10万文字なら1秒切ることもある
作為的なデータに弱いけどな('A`)

良い方法思いついた
10秒なら行けそうなﾖｶｰﾝ

>>279
ふふふふふふふふふ

資格がないので出ないけど、どんなデータでも0.1秒は切れる。
＃データによらないので
10msは目標であって、たぶん無理だけどｗ

ぁ、繰り返しがめちゃくちゃ長いと、10msいけるな。半分以上の長さとかね。

http://slashdot.jp/~pascal/journal/?06100045
こちらの人は4秒らしい

30msぐらい安定の俺がきましたよ。
ってか本当に計算量nlognとかになるのか？
どう考えても似ても似つかぬ計算量なんだが・・・

Nと時間のグラフうｐｈしる

DP で O(n log(n))

すげえな、オマイラ。
俺なんてまだまだか。

当然の話だけど、ランダムな文字列と作為的な文字列、
両方に対応してないと駄目だよな？

しかし、速度もみんなばらばらだねぇ。はやく予選締め切りがあけて、みんなの解法のupと正解アルゴリズムを知りたいな。
つうことで、締め切り後よろしく＞がんばってる方々

だれか sample input と sample output 作ってくれない？

293さん、それは止めておいた方がいいでしょう。。
一部でもプログラム自体やヒントを上げるようなのは、
ほんとに頑張って考えてる人が損をすると思う。。
だから締切までは自分の速さとか、抽象的なものだけにしましょうよ。

速さが抽象的？

>>293
outputはprintfで型どおりに表示するだけだろ
inputはscanfで適当に格納したらいいんじゃない？

1010010010

これでやってみて

>>297
？？

>>297
末尾に2がない。

駄目だ・・・
こりゃ予選通らねえわｗ
もう俺には無理ｗ

たぶん、上のすごい方々はスパコンＯＢ・ＯＧなんじゃないかと。
気にせず出せばよいかと（笑）

>>301
スパコンOGなんているのｗ

近年の女性の社会進出により、７０％が女性だそうです（嘘

やっと3分きったと思って、のぞいたら、なんなんだこの速さ。。。ぐぎぐぎ。

>>304
俺も・・・

後でどんなやり方でやったのか聞いてみたいよ・・・

すまぬ
O(nlogn)思いついたよ。

やはり、ずらしていくので良かった。
かなり工夫が必要だけどな

その表現だと、俺のn log nとは違うアルゴリズムらしい。。
まぁ、同じ計算量の違うアルゴリズムがあっても不思議ではないが。。

>>308
参加者？
俺は不参加だけど

いえ、資格なし（笑）

なんかO()ってのの説明サイトきぼむぬ。。

>>311
わたなべおさむちゃんのアルゴリズムとデータ構造の授業の資料だけど
このへんにのってるとおもうよ
http://www.is.titech.ac.jp/~watanabe/class/ad/

オーダーについてはこのへん？
http://www.is.titech.ac.jp/~watanabe/class/ad/4-19c.pdf

1111111111111.....1112
とか
0000000000000.....0002
とか同じ数が並んだ時は速さどれくらい？

>>313
2ms

>>313
1ms

とりあえず100000文字で何秒ほどでいければ予選突破できるのかな・・・

ここ見てる様子では10から15か、15から20秒ぐらいかと。。

ランダム100000文字なら1秒切らないと厳しいと思うよ

マジでか。
厳しいな・・・・・

まじすか///10秒切ったら安泰だと思ってた↓

ttp://zeroichi.ddo.jp/diary/
100000文字1秒のお方が「自分のでも予選通過はギリギリだろう」って。

>>321
それなら線形時間でできるかもしれないな。
いま対数時間でひぃひぃ言っているが
もしかしたら・・・

テスト問題の繰り返し区間の長さの答えが2005とかになっていることに1票（ｗ

新しく出た本の値段で2100文字ってのにも1票。高いよOTL

新しく出た本詳しく

どぞ ttp://www.gsic.titech.ac.jp/supercon/

ttp://www.kikuyashoten.co.jp/detail.jsp?ID=0105682281
ttp://www.amazon.co.jp/exec/obidos/ASIN/4535784337/qid=1119063384/sr=1-1/ref=sr_1_8_1/249-6420299-0161932

在庫無しとか1冊とかorz

前のSupercon数が2004番目だったからな。

>>323
複数のデータを使うそうですけど・・・？

>>328
微妙なレスいくない!!

複数のデータって、きっと
ランダムなやつとか繰り返し多いやつとか混ぜるんだよね

ひとつのデータの中で混ぜられた方がプログラムでは対処しずらいなぁ。。

すべての場合を高速化するのは無理な気がする

>>332
いやいや。
そんなことは無いだろ。

サンプル作りあって
秒数比較するとかどう？

>>334
やってみるか

「スーパーコン甲子園」感想
・出場者バカにしてるよね？チーム名すらも載せないってか
・毎年（可能なら全チーム）の解答ソースコードを見たかった
・坂本さんとか黒板競争とかはよかった


うーん、1580円くらいだな

解答ソースコードとかは著作権の問題をクリアするのが面倒、とかもありそう。
全員から許諾貰うのはまず無理な一方で、一部だけ載せるのもまた問題だし。

チーム名もまぁ、出場者以外は興味ないしね（ｗ
でも、出場者以外で買う人いるのか？

で、坂本さんの ksh の設定ファイルは何処で貰えるの？

MLでもさんかできるの？

>>336 N崎先生がやせててかっこよかったのがおもしろい。

>>337
大会に出した時点でそういうの認めてるって事になるんじゃねーの？

MLなんかで書いたら遅くて3分切れないだろ？

諦めて0,1をランダムに出力するプログラムの作成に取り掛かろうぜ

perl -e 'srand();for(1..500){print int(rand()*2)}print 2;'

>>342 OCAMLならはやいだろ？

#!/bin/zsh
for ((i = 0; i < 100000; i++)) { print -n $((RANDOM % 2)) }
print 2

それより、難しい01列を作る方がやっかいだ。

#!/bin/perl
sub genstr { my $a; $a .= int(rand(2)) for(1..$_[0]); return $a; }
print genstr(100).(((genstr(25)x139).genstr(10))x2).genstr(100)."2\n";

余り参考にならない方法ですが。

>>347も含めて、予想問題のうちにこんなのがある

・・・100000110000110001100110111
前にはいくらでも付け足せる

>>349
予想問題ってこっちの内輪のやつのことね。

348っていい感じ?
俺Linux微妙やから友達に頼まないとあかんねんけど…
いい感じのやつなら頼んでくる。。

こんなのはどう？

1. 適当な長さkの01列a[0..k-1]を作成
2. a := a[0..k-1]a[1..k-1]
3. if (k>=limit) 終了
4. k=2k-1
5. goto 2.

すまん、ちょっと修正
1. 適当な長さkの01列a[0..k-1]を作成、m=1
2. a := a[0..k-1]a[m..k-1]
3. if (k>=limit) 終了
4. k=2k-1 , m=m+1;
5. goto 2.

まだミスってるな。すまそ。
4.ですが、k=2k-mですね。

こうやって作ったものだと、ほとんどの位置で始まる繰り返し列があって、しかもそれらが異なる基本列なので、結構大変なはず。

ただ、めちゃくちゃ長いのがあると計算は楽なので、limitを1k程度にして、
違う配列からスタートさせたものをつなげて行く方が難しいかな。

アルゴリズムを考えたわけじゃないんだけど…

レポートってa[0..m]とか使わないといけないのよねぇorz

あげ

みんなもうレポートに突入してるのか?

大幅変更を余儀なくされた悪寒。まさに悪寒。

getchar()-'0'で入力するのはだめなのか？

だめなの?いい希ガス。

>>359
3種のアルゴリズムでプログラム組んでる。
単純、複雑、もっと複雑の３つ。
どれが早いかを直前に決める。
レポートはすぐに出来るから

つい先日、学校の先生にすすめられたのでやりはじめた。
試験一週間前だし期限近いし仕上がらなさげorz
もっとはやくいっといてくれよ、、、

>>362
>>361は数字が順番に並んでる文字コード体系のコンピュータでしか使えない
とはいっても今となってはそういうコンピュータはなかなかないだろうがｗ

>>365
Cの規格ではそうならないといけないと決まっていたはず。
アルファベットやそのほかは別にどうでも良かったが
数字の文字引く０の文字コード'は数字になるはず。

そろそろ追い込みいかがですか？

ばぐってたけどもう何も考えたくない。。。。
ちなみに今ランダムで2秒、、みんなどうよ？

レポートって何かけばいいの？

レポートおわらねー
試験でメンバー協力してくれんし

われわれは、下記のＡＢＣアルゴリズムを開発し、それを実装した。

下記下記下記

このアルゴリズムのポイントは○○と△△のところである。
△△については、[Hogehoge et al. 1312]の有名なO(hoge)時間
構成アルゴリズムを利用した。これのおかげで
この計算量は云々であり、きわめて速いアルゴリズムである。
実際様々な大きさの様々な性質（Ａ，Ｂ，Ｃ：別表参照）のデータ
に関して実験をしたところ、図Ｘのような計算時間となっており、
理論的計算量と合致したものになっている。

また、理論的計算量には貢献していないが、われわれは◇◇という
テクニックを用いて高速化している。これについては、このテクニック
を用いないアルゴリズムの速度との比較を図Ｙに掲載した。グラフから
見てわかるとおり、入力がＡというタイプにおいてこのテクニックを
用いることで平均１７．３倍の高速化が実現できている。
どーだすごかろう云々。

こんなかんじ。

100000 文字の最悪パターンで何秒〜？＞みんな

17時間。

>>372最悪って何？

>>374
実装したアルゴリズムに依存するのでは？

>>374
計算時間が最もかかるパターン。

んー、だから、そのアルゴリズムに対する、最悪のパターンってことでしょ?
俺のところは…40分はかかるかなぁ…。。
でもそんな文字列は2^10/2^100000位の確率なんで気にしないつもり。

>>377
んじゃ、平均は？？

>>377
大体そのアルゴリズムは分かったけど、多分想定の範囲内。
相手に狙われてアウトかと。

うそん…そんな簡単にわかるわけないじゃんw

>>380
なにいってる。
ココまで来たら大体皆同じアルゴリズムに決まってる。
あれか、これか、それか・・・。大体3種類くらいだろう。

問題はどれだけ高速化可能かっていう事だ。

＞俺のところは…40分はかかるかなぁ…。。
＞でもそんな文字列は2^10/2^100000位の確率なんで気にしないつもり。

少なくとも俺はこの一言で大体のアルゴリズムは分かったつもりだ。
第一、SuperCon事務局もココ見てるに違いないしな
そんな事を書くと不利になるだけだぞ

総当たりしか思いつかないので、ぴったしO(N＾2)。
どんなデータも50秒ぐらいかかってしまうんだが、やっぱだめかな?

たぶんだめ

やっぱだめかorz
残り時間少ないしな...

それはともかく、総当りはO(n^3)といわないかな。
対象がランダムの場合の期待値はO(n^2)だが。

意外とみんなO(n^3)だったりするから安心しろ。

おれはO(logn)だけどなにか？

「あれ O(n^3)」と「あれ O(n^2)」 しか思いつかん orz

>>388
つヒント:indexing

あーあ、どこでバグってるんだよ...
時間なくて出せなさそう...

>>385
いや、総当たりはデータがランダムかどうかは関係ないし。
理論上も実際もO(n^2)と思うが...
だが、そんなことよりこれではだめぽ orz

>>382
ちゃうちゃう。上(?)には上(?)がいるんだ。
最も古典的なアルゴリズムだと、O(n^3)かかるんよ。

最も古典的？
スマンが、二乗しか思いつかん。
３乗ってどうやればいいのか･･･

aの長さと仮定してb番目からとc番目からとを比べてるんじゃない？
明らかにc=a+bだからすぐO(n^2)になると思うけど

i番目から繰り返し区間があるかどうかを調べるには、繰り返し区間をO(n)種類調べないといけない。
しかも、ひとつの長さを調べるには最悪O(n)の長さ（ランダムだったらO(1)の期待値）を調べる必要がある。
これをすべての位置から始めれば、O(n^3)だよ。

>>389
わかっている人にしかわからないヒントだね（ｗ

おれはO(2^n)だけど何か？

>>396
n <= 20 くらいなら計算終るね

>>397
ﾜﾛｽ

ところで、入力時間は審査に含むのか？？

>>399
入力に10秒かかったりはしないでしょ。
入力程度の時間が問題になるくらいの速度なら、実行時間じゃなくてレポートの質で判断されると思われ。

なんか本当にアルゴリズムばれてるんだろうかという気になってきたよorz
ヤケになってもう1つ質問。ランダム10万文字なら難病ですか？？
うちは最速で2秒。。予選配布されたころに1秒切る勝負とか言ってたけど、
実際のところみんなどうよ？？うちってやばいの？大丈夫やんね？？

>>401
スペック次第だろ速度なんて。
ただ、いえることはここで書いてある速度が全部正しくは無いって事だ。

つーか、スパコンは運。
2003年連結の問題なんか、答えだしてる所全員通してるし。
基準なんて毎年違うんだから出してみないと分からん。

レポートうぜえええええええええええええ

>>403
>>370

つ、、、ついに外見バグなしな感じのものができた

っぽい


ところで標準入力って
scanf("%100000s", problem);
こういうので良いのかな。
面倒だから一行ですむものにしたけど。
でもVCだと4000文字ほどしか受け付けないorz


さーて今からレポートか。

fgets(line, sizeof(line), stdin);
*strrchr(line, '2)' = '\0';

> 提出物

> 1. 解答プログラム
> 2. プログラム開発に使用した計算機，コンパイラ，テストデータ，実行時間に関するレポート
> 3. プログラム中の主要アルゴリズムのアイデアを説明するレポート．


ってあるから
提出レポートは2つ？

やっと出来た。
速度安定しない。
100秒以上かかる（２Ｇで）
絶対落ちたな・oZL

おつかれ、当日提出ならコンパイルエラーに注意だな。。

みんな受理確認メールみたいなのってきた?
なにも来なくて届いたか不安なんだが。。

>>410
一応来ましたよ、昨日送ったら昨日に

ところで、もう終わったしソース公開しちゃっていいのかな

ソース公開は、決定後のほうがいいと思う

今日は締め切り間際に大量に申し込みがあっただろうから、受理確認も遅れてるんだと思う。
出すのが遅いとこういうときのリスクもあるよな。

ところでさ、速さについての話題ばかりだったけど、みんな正確さに関しては自信あるの？

>>413
20桁までの入力に関しては最悪に遅いが確実なプログラムと
出力を照らし合わせて確認した。。
それより長いのは･･･まぁソースを見る限り大丈夫かと(誰しもそうだろうけど)

去年は提出から発表まで早かったけど、
今年はえらく長い･･･単に土日をはさみたかっただけなのか、
レポートをじっくり見てから結果を出すつもりなのか、
もしくはそれぞれのプログラムに対して時間のかかる入力を検討するのか･･･
恐ろしいことは考えるときりがないよなorz

今回は実は正確性が重要だと思う。
01010101110101010110011012
上でやってみて。

ある方法だと、失敗するんだが・・・

>>416
01 8
0101 8
01100110 8
こんなのでいいですか?

[***@*** ***]# ***A/a.out
01010101110101010110011012
0110 8
[***@*** ***]$ ***B/a.out
01010101110101010110011012
0110 8
[***@*** ***]$ ***C/a.out
01010101110101010110011012
0110 8
[***@*** ***]$ ***D/a.out
01010101110101010110011012
0110 8
[***@*** ***]$ ***X/a.out
01010101110101010110011012
10 8
まちがってる？最後のだけアルゴリズム違うんだが。。

>>417
ﾄﾞﾎﾞﾝ

>>417&&>>419
なんで417みたいになるのか説明ｷﾎﾞﾝ

さーてこのスレに何チーム(人)いるのか見ようと思うんだが･･･
俺まず1人目。

>>419
>>417のどこが間違ってるんだよ？
01100110 8
は
0110 8
って表示されなきゃだめって話か？
そんなん、本人だってわかっでるだろ？
あと、解答は一つだけ出せればいいから、>>418みたいに解答全部出さなくてもいいんだよ。
予選問題、ちゃんと読みなさい。


どうでもいいが、昨年スパコン本戦にバリバリ出場したにも関わらず、最悪O(N~2)の方法しか思いつかない（しかも組むの面倒臭くて組んでない）俺がいる。
とりあえず、何年か前には、正答を出せるプログラムを提出したチームが１０チームしかなくて、正答を出せるプログラム作ったってだけで予選通過できちゃった年もあったらしいから、
正答を出してるっ「ぽい」プログラムを作れたところは、迷わずに送れ！

俺の場合、「絶対受かる」と思ってコード送った年に予選落ちして、「落ちるかも」と思った年に本選出場果たしたから。

>>422
２、解答プログラムは標準入力から文字列を入力し，標準出力に

繰り返し列　最長繰り返し区間長

を出力しなさい．複数候補がある場合はどれか一つを出力すればよい．

http://www.gsic.titech.ac.jp/supercon/supercon2005/yosen.html

422は理解したんだけど423の意図するところは?
422と一緒?

いや，一応422の書き込みに補足書いといた方がいいかなって。
それだけ。気にしないで。

未だに受理のメールが来ない。みんなはどう？

>>416に賛成だな。
乱数で大きな列を作って速く解けるようにするよりも、小さくてもいいから意図的に間違えやすそうな列を作成して
確実に解けるようにするほうがいいだろう。
乱数で作った列だと、そこから取り出した解が正しいか保証出来ないし、それを保証するためには全ての正解を取
り出せるようなプログラムを別に作らないといけないだろ。
審査も「原則として，すべてで正解を出すプログラムが評価の対象」って書いてあるんだからさ。

実行速度自慢じゃなくて >>416みたいなのリストアップしてみよーぜ。

100010000000001000100000000100000002
ってか総当たりすればいいと思うんだが。。

>>428
100010000000001000100000000100000002
010000000
18

>>429
自分は000100000になったので、
後ろからやるか前からやるかの違いですかねw

うわぁ・・・最長マッチと勘違いしてたナリ・・

うわぁ・・・勉三さんの中・・・あったかいナリ・・

0010001000102
どう？

./a.out <<<0010001000102
0010 12

うわぁ・・・繰り返し列の長さ50000だと・・・エラー吐くナリ・・orz

011111111101111111011111110111111110111111101111111002

./a.out <<<0010001000102
0010 12
./a.out <<<011111111101111111011111110111111110111111101111111002
1111111101111111011111110 50

<<<っていう入力法があったんだねぇ･･･いい事知った

だから上の方でリダイレクションって書いてあっただろ。

>>438

ごめんよ <fileは知ってたが<<<は知らんかった…
>fileとか2>fileとかも使ったりするけど。。

> 予選通過しましたのでお知らせいたします．
> コンテスト日程の詳細はコンテストページにて
> 公開いたしますのでご確認ください．

> ------------------------------------------
> スパコン実施委員会 ([email protected])

>>441
orz

>>441
文面が微妙に違うからそれぞれに書いてるのか担当違うのかなｗ

うちのは
X-Mailer: nPOP Ver 1.0.2
だった

提出確認のめーるは M2 だった

>>443 >>444
orz

今メール届いていない俺は落選ですか？

>>446
orz

7月11日発表ですし
事前にメールは来ないんですけど･･･。

釣られないよ

>なお、本選出場の確認のために、事前に問い合わせを行います。

>>448
去年は前日ぐらいにメールが来た。そんな俺は落ちた。。
だから信じざるをえない。。

>450
確かにそれはあるはずだ

毎年その記述はありますが、事前に来た事はなかった。
つーか、合格のメールのほうが釣りじゃね？

予選結果は、平成17年7月11日(月)正午に、電子メールで、予選通過者のみに通知します。
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

日本語読めないのか？

>>453
遠隔地だからかもしれんよ

落ちたからってw

ドキドキ

ｺﾈ━━(ﾟДﾟ)━( ﾟД)━( ﾟ)━( )━( )━(ﾟ )━(Дﾟ )━(ﾟДﾟ)━━ !!!!!

ﾄﾞｷﾄﾞｷ
ﾄﾞｷﾄﾞｷ

ﾄﾞｷﾄﾞｷ
ﾄﾞｷﾄﾞｷ
ﾄﾞｷﾄﾞｷ
ﾄﾞｷﾄﾞｷ
ﾄﾞｷﾄﾞｷ

清風南海学園（大阪） dodemoZ
一関工業高等専門学校（岩手） Epigonen
高田高等学校（三重） godtos
甲陽学院（兵庫） Imo
筑波大学附属駒場高等学校（東京） Lunatic
筑波大学附属駒場高等学校（東京） ytterby
東京工業大学附属科学技術高校（東京） NASA
東京工業大学附属科学技術高等学校（東京） UMAIBO3
広島国泰寺高等学校（広島） phoenix2
麻布高等学校 (東京） UNYUX

受かったみんながんばれ。
落ちたみんなおつかれ。

ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!

>>461
死ね

>>463
……

いや，俺はスパコン予選落ちの経験が二回ある（今年は応募すらしなかった）人間なんだが。

…………死んだ方がいいですかそうですか。

なんで応募しなかったの？

作る気力も起こらんかった。

おー
俺の母校が受かってんじゃん

予選落ちた人も、時間あったら最終日の発表を
見に行くと面白いと思うよ。

ごめん。僕 381 じゃないよ。なんで数字はいったんだろ。

通過した。
東京で会おう。

来年のスパコンは我々が頂く。

>>470
向こうのおやつタイムで
スムニダーていうからそういう奴が俺だと思ってくれ

関西弁話してる小柄な少年で
（・∀・）の携帯ストラップしてる奴が俺だと思ってくれ

それと、どうでも良いですが、物好きな人のために
予選に使ったプログラムを少しの間公開しておきますね
//fbox.info/program.c

筑駒つよそうだな
てか学校から2チーム出ると、そいつら裏で相談できんじゃん
せこいな

ヒント：相談しても速くなるとは限らない

やっぱり O(n logn) か

>474
同じミスしたら両方落ちるけどな。

他のチームと相談してもいいんだよ。相談のレベルにもよるけどさ。
やりすぎて出し抜かれても、それもまた人生。

>473
うーむ、スゴ過ぎ
繰り返しの多いデータでは特に早いし
アルゴリズムの解説をキボンヌ

>>473

うちのチームのプログラムのほうが速い
ランダム文字列なら3倍
同じ文字の列なら100倍くらい

ランダム文字列は実行オーバヘッドっぽい
もっとプログラムを軽くかこう

同じ文字の列はアルゴリズムの違いだね
前からじゃなく後ろから...

あと search() で出力するとか

>>480
ソースうp

本選問題は、当日まで概要も知らせないのだろうか。
去年は出場者には事前に知らせたんじゃないの？
どうなの＞去年の本選出場者

俺の口から正確なことは言えないが…
去年の場合は…
>>48みたいなことがあった。とだけ言っておこう。。
今年に関してはなんの保証もないけどなw

接尾辞木の説明サイトキボンヌ

http://www.google.co.jp/search?hl=ja&q=suffix+array

480は逃げたようだな。。

ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/747.c
おもいだしてかいてみた
ていしゅつしたのじゃないのでまちがってるかも
だいたいこんなかんじ

>>487
逆にすごい
読めん

>>487
萌えた

>>487
memcmpをﾂｶﾜﾝとfullでサーチ？

>>487
0110011011001100100110010011002　の結果が違うようです(正解は1001100 21)

ちなみに、他の某チームのソースを拝借して試してみたところ、この問題では
正答出していたようですが、誤答を出す問題がちらほらとあったようです。
枝切りは確かに重要ですが、過度にやると逆効果になることがあるので、
慎重に１歩ずつ進めていった方が良いと思います。
という私は、枝切りの段階までたどり着けずに全滅してしまったりもしますがorz

本番age

お、頑張って来い＾＾

本選問題概要が8/1発表になってるのにうｐされてないので
すごく文句の言いたい去年行けて今年落ちた漏れ

去年ここでの議論のせいで大会終了まで発表されないそうです。
2ちゃんねるへの書きこみをしないでくださいといってました。

去年もちゃんと大会中は誰も(出ていないヤシですら)
書き込んでない。。2chに信用がないというか
実行委員会が信用してないというか。。

好きな素数は3

みんな、乙

寂れてるorz

予選の解答プログラムはいつになったら公開する気なんだ

いや、毎年あんな感じでorz

>>501 中の人ですか？

>>502　大会期間中しか見てないんでないの。。

いやいや、そんなことは >> 503

さてさてみんな情報オリンピックにはでるのかな?

3年だｫ

ML登録した人挙手ｷﾎﾞﾝ。
俺は未だ様子見てる。。

こんなスレあったのか・・・
去年出場した人たちはみんなもういないのかな？

(漏れ

おお、生存者が！
どこの学校の方ですか？

えーと、、んー、、どう表現したらバレを防げるだろうか。。
3位チームの隣でプログラミングしてた学校(ﾜｶﾙｶﾅ?；；

学校の件名言ってくれればわかりますよｗｗ（ﾜﾗ

↑県名ですorz

実は毎日見てたりして

３位チームだが、隣に誰が居たか覚えてない

3位チームの横ってことはもしや漏れのﾁｰﾑかｗ
>>511はﾁｬﾘっ子と見た。
そんな漏れはﾁｬﾘ親分。

sage忘れたorz

お久しぶりでヤンす。
>>515 ひどいぉ；；
>>516 (。。)(ﾟｰﾟ)ｳﾝｳﾝ

誰かみてるか微妙だけど
情報オリンピックの5番の私なりの解答
ttp://private.fbox.info/joi/2006021205.html
暇だったら他のも作るかな

本選通過者発表されたね。

なんだか8人中6人が2005年スパコン出場者だなあ

中学生も一人いるのか．．．

とりあえずはSuperConメンバーでメダルは死守しましたよ＾＾＾

2004年組は結束堅そうでいいなぁ

ここで2004年組の俺が登場ですよ

何でmixiにSuperConコミュは無いのだろうか

>>526
たてれ！

526ではありませんがmixiにSuperConコミュたてておきましたです
mixi.jp/view_community.pl?id=654787

俺も2004年組なんだが、、情報オリンピックなんで去年やってくれなかったのかorz
(思ってたよりスレ人口多くて驚いたわ(´･ω･`)

保守

かなり沈降スレになってるけど、見てる人いるのかな？
6月の予選終わったら、みんなでソースとサンプル入力を持ち寄って、
どっかのHPで勝負してみない？(と参加資格なくなった者がいってみるﾃｽﾄ

もうそんな時期か…

今年も出たいなー

>>531をやってみない？
ともう一度声をかけてみるコンパイラ（あ、スレ違･･･

suffix array

2006年大会は関東・関西でやるそうです。
関西は大阪大学開催です。
http://www.gsic.titech.ac.jp/supercon/supercon2006/

>>536
関西人としては後輩たちが東京に行けるチャンスが減ってしまうのが残念だわさ。
まぁこれを機会にもっと有名な大会になってくれるとありがたいね。

完全にすべて大阪だけだとSuperConとは言えないから
やはり最終日は何らかの形で東京に行くのかもしれませんね、と
http://www.gsic.titech.ac.jp/supercon/supercon2006/annnai.html
を見て思ってみたり。すべては憶測。さて予選問題はいよいよ明日発表です。
まだ中間試験中なので当分はやりませんが、できあがったら皆で持ち寄れば
面白いですね。むしろ解答サンプルは期間中に欲しいぐらいです（ぉぃ

TSUBAMEつかえるのか
いいな

ttp://www.gsic.titech.ac.jp/supercon/supercon2006/yosen.html
入力は必ず解が存在するのかな？

辺の長さが偶数だと指定されているので必ず存在しますよー

ハミルトン閉路か…。
こりゃあ面倒だな。

これは最適には解けない前提で近似解？

というか頂点の詳しい数の上限下限を教えて欲しいのだが…。

nの上限が100だから、1≦n≦10000では？

訂正。1≦与えられる点の数≦n*n≦10000

まともにやったら無理だな。
O((n~2-1)!)なんて。

ミスった。O((n^2-1)!)

n^2ってどこからでてくるの？

点の数

ってかこれ問題文の一行目から近似解を求めてるってのがものすごく感じ取れるんだが…。

うは、ﾅﾂｶｼｽｗｗｗｗ
つか今は 2ch にスレがあるのか…
現役の人がんばってね。

> 「矩形閉路」とは，(…) 同じ辺を二度は通らずに，元の頂点に戻ってくるもの

という定義なら同じ「点」は二度以上通ってもいいよね? でも一方で

> 矩形巡回路なので， 同じ頂点は，(i) 出発点を除いて二度以上現れない

と書いてあったりするので、うーん。

できた

オーダーきぼんぬ

オーダーより近似度がしりたい
MSTのDFSだと2倍なのであまり良くないし

exeにしてうｐれ

http://up.nm78.com/data/up080246.jpg

今回ってSGI協賛しないの？

そういやSGIは潰れたとかいう話を父親から聞いたことがあるけど。事実かは謎ですが。

TSUBAMEはSGIじゃないから

そんな事は誰でも知ってる

http://enterprise.watch.impress.co.jp/cda/special/2006/05/22/7794.html
ここ読むといい。
日本SGIは安泰だし、本国も再建計画の見通しは明るい。

int main(){int n,x,y,i,a[100];scanf("%d",&n);memset(a,0,400);void p(int c, int d){
printf("%d %d\n",c,d);}while(1){scanf("%d%d",&x,&y);if(x==-1)break;if(n-1!=y
&&a[i=(x+1)/2]<y)a[i]=y;}for(p(0,0),x=1;x<n-1;x++){for(y=0;y<=a[(x+1)/2];
y++)p(x,y);for(x++;0<=--y;)p(x,y);}for(y=0;y<n;y++)p(n,y);for(x=n;0<x;x--)
p(x,n);for(y=n;0<=y;y--)p(0,y);p(-1,-1);return 0;}//This is too low quality

>>538
前日までプログラム書いて、最終日だけ東工大に移動するというのは厳しいし、去年までの会場だと20組を
収容するキャパがないように思えるので、本選発表会もリモートで参加という形になるような。
その場合、関西組は優勝してもTSUBAME本体を見ることもできないし、去年までスーパー
コンピュータの前で優勝者の写真撮影してたのはどうするんだろう。
あと、TSUBAMEへのログインなんかはともかく、発表会とかリモートで参加するシステムが
ちゃんと整備されてるのかなぁ。

>>564 この程度の回答なら問題ないと思うけど、
締め切り過ぎるまで待つとか、微妙な事は
避ける方向でよろしくご協力くださいな。

>>566
>>1読め。
見たくないならくるな。

>>567
高校生が参考にしたら大変でしょ。でしょ。

>>567 うん、1 読んだよ。でも、アルゴリズムを投稿するのと、
締め切り前にコードフラグメントを投稿しちゃうのの間には微妙な差が
あるじゃない?

(多分ないと思うけど)567 と同じコードを提出してきたチームがもし
あったら、偶然でも失格になっちゃう可能性もあるから、締切り前は自重
するのが大人ってことでお願いしますよ。

じゃあ、コードをいろいろはれば
だれかを失格にできる可能性があるのですね

まぁいろいろ意見があるようだけど、返信してしまうとよくないってのは皆様お分かりの通りなので。



ところで今年の問題はマトモな回答を出すことすら難しい気がするんだが、みなさんどうでしょう？

というか他大学チームも1チームだけでいいから出させてください・・・superconが楽しみで生きてきたのに（

>>571
っ ACM/ICPC
っ TopCoder
っ Google Code Jam

大学生入れるとまた別の大会になっちゃいますからね・・・。
ただ、情報系の大学生（院も？）が入り乱れての超高度な大会も面白そうです。

ICFP Contest とか ImagineCup もいいかも

ImagineCupは純粋にプログラミングの能力を競うものではないからなぁ…

どうてもいいがDPで近似解がでそう

>>576
近似解はでねえよ。

これで優勝するような高校生って情報系の院卒並の知識すでに持ってそう

やり方は知っていても名称は知らないとかそういうのが多そうだけどｗｗｗ

自分で発見/発明したと思ってて大学行ってから先人が居ることを知ってorzるんだよな

どれくらいの人が提出するのか気になる今日この頃

普通でもそれほど多くないのに、今回異常に難しいから定員割ったりして

>>582
そんな気もする、80%ぐらい。
チーム数も増えたしねぇ・・・ｗ

東京3チーム、大阪20チームとかだったらどうするんだろう。
東京は予選なし、大阪のみ予選になるのかな。

>>584
もしそこまでなったとしたら　合併させて例年通り東京でやるんでね？

ボーダーが予想つかん、誰かサンプルデータとかあげてくれ・・・

ttp://private.fbox.info/informatics/sc06y/sc06-data.lzh
0118+0268+0354+0746+1524+2476+1192+4486+7528+9822=28514(高)
0128+0226+0316+0662+1206+2412+1084+3528+5672+9066=24300(筑)
0122+0242+0328+0676+1274+2426+1146+3742+6100+9310=25366(甲)
0122+0256+0346+0728+1442+2470+1194+4276+7084+9734=27652(筑2)
28000切れば余裕。30000ぐらいがボーダー？

やたっ、予選通過だよぉって電話きたよぉ

Team Imoのソース及びレポートです
ttp://private.fbox.info/informatics/sc06y/imo.txt
ttp://private.fbox.info/informatics/sc06y/supercon.pdf

>>588　おめでとう！
俺の母校も来たらしい！さっそくMPI講習会でもしてやるつもり(笑

win98とmeのサポートが切れたので保守。

皆Linuxに四苦八苦してる中を持ち込みのMacで楽しようと計画しながら保守

※大阪会場は端末のOSはLinux

imoさんこんな所に居たのか...

>>592
ってかウィンドウズで使えるsuperconは見たこと無い

>>587のデータをこつこつ減らしてみたけど、結局26820止まり
どうやったら24300なんていくんだ・・・

今回も大騒ぎするぜー、というのは置いておいて。阪大は端末がLinuxなのに東工大はMacOSXなのはいろいろと差がつかないか？と思う。是非とも東側の人はXC○DEなんていう使いやすい環境は使わないで欲しい。（といいつつ私は15inのPowerBookG4でごにょごにょ
>595 結論は筑駒は強い、と。だが負けてられん！！

いや、弱い方の筑駒なんだがねｗ

まぢで、MacOSでやるんや・・・時代は変わったのぉ･･･ｗ

スパコン初めてなんだけど、なんか予習とかしとくべきなのかな？
なんかＣＰＵたくさんとか動かせる気がしないや

予習しようとしても実際がどのようなものなのかがわからないのが世の常であり実際問題使って見ないとわからないものであるのも世の常。

そして２年目が少しばかり有利なのも世の常。

初日にある説明を鹿と聞きなさいってこった＼(^o^)／ｼｶｼﾞｶｼｶｼﾞｶ

大丈夫vimの方が早い。

>>599
２００４年とかのページの、MPIチュートリアルってのを見ながら、分からない関数
(MPI_Send()とか)をネットでしらべとくといい。
そうしないと俺たちの年のように数チームはプログラムが組めずにあきらめだす（笑)

軽いノーパ持ってるなら持ってくると便利、とだけは言っておこう。

そろそろやね、みんな頑張ってｂ

えーん、MPI勉強してるのに全然わかんない
しかも学生証が見つからないしぃ・・・

うお学生証忘れてた。ありがと。

もう始まったかな？

・・・見えたっ！！

問題なんだっけ？

>>608
ん？？

>>609
本選問題は最終日に発表ですよ^-^)

関係者の方は見てないのかな、、大阪大学でも発表会があれば行きたいのだけど、
大阪大学の会場は公開されるのでしょうか？



あー、、いまごろはみんな必死でプログラム考え直してるころだろうなぁ･･･
俺たちも最終日は睡眠時間2時間で突っ込んだもんなぁ･･･あのころは若かったｗ

>>610
大阪大学に電話したけど無理って言われた

終わった

頑張って東工大に行くんだ。
きっとあっちの発表会場はガラガラだぞ。

よ・・・予選１位だもんっ！！！
最終審査なんて関係ないもんっ！！！

グループ番号が連続してなかったｱｯﾋｬｯﾋｬ

>>614
トリップすごいな

>>614
聞き飽きた

ショタDNA

いい加減問題公開してくださぃよぉ・・・＞実行委員会様

HP更新やる気なさ杉

絶望した！東工大のいい加減さに絶望した！

去年のsuffix treeもまだ？

公開されてるね。

出力結果も見てみたかったなぁ。もう記録に残っていないのだろうけど。

えーと、結果をぼんやり見てて思ったこと。

本選の最終って10分間って書いてあるけど、どこのチームも3分以内に出力してるのはナゼ？
俺には3分すぎ〜10分直前の７分間ものあいだに良い解が出せないというのが微妙なんだが･･･

まぁ俺も問題といたわけじゃないんだけどね。
各チームが極値解（？）から他の解を探すことができなかったのかなぁ･･･と残念ですな。。

superconは予選もかなり難化してきてちょっと敷居が高くなったかも？
来年はもう少し多くの高校生が予選に取り組めたらいいなぁと思います。。

あとさ、だれかOB会のURL知らない？知ってる人いたらメアド晒すんで送ってほしいな･･･

多分それは偶然だと思いますー
自分のチームは途中で無限ループ入っちゃったっぽくって１０秒以内ばっかりで論外なんですけどねorz

基本的には、別のデータでは時間増やせば増やすほど減ってくチームが多かったように見えたし、
むしろ、ランダムな初期値を与えて、そっから局地解出しまくる感じのチームも
結構あったから、３分以内しかないのが不自然すぎるんだよなぁ・・・

毎回同じ局地解に入ってるって可能性もないわけじゃないけど、
自分もちょっと不思議だと思いましたｗ

あの本戦用のPDFと同じような内容しか聞いていなければ3分間の出力しかないのは納得できるのでは？
有る程度解が更新されなかったら再び乱数解からスタートする焼き鈍し法だとか
部分的な解を交換しまくるGAだとか書いてないし。
TSUBAMEのCPU数が山のようにあったって、CPUコアと同じ数だけの出発点で終わっていたら
局所解を出して終わりでしょ。

んっと、自分のチームだと、局所解にいくのに遅くても１０秒ってとこだったんで・・・
他のチームも恐らくそれくらいだから、局所解を見つけて終わりってことはないはずですー

定期age

http://ex13.2ch.net/test/read.cgi/hsb/1161872899/l50