プログラミングコンテスト

情報処理学会東北支部設立３０周年記念
プログラミングコンテスト
　ー みちのく　達人　秋の陣 ー
参戦者募集！！
http://www.maruoka.ecei.tohoku.ac.jp/procon/

こんな問題で差ができるんだろうか？？

おまにはできんな

>>2
解けないバカ発見

つか、報酬10万かよ。

>>1
課題を見て笑ってしまった。まぁ初学者には適切なレベルかと。
しかしなんで高卒は対象外なんだ…

しかも3人も集まってどうしろと言うのだろうか？
それと審査基準が客観的にとか言っときながら
絶対に主観によらない審査などできんだろうに・・・

審査が難しいだろうね。
説明書まで審査対象なのが日本人っぽい。
IBMのJava戦車の方がよっぽどわかりやすい審査基準だな。

これが分からなかったらプログラマ失格でつか？
みんな分からないでしょ。

なんか、ゲームウォッチみたいな問題だな。

O(n^2)で計算できればいいのか？
もっと速くできる？

>>1
そんなに笑える程簡単な問題ではないと思うが・・・

>>3
この問題を "解ける・解けない" で語るヴァカはけーん。

>>5
お前みたいな奴がいるからな（ｗ

>>10
その n ってりんごの数？

とりあえず漏れが今思いついた戦略（予選）を挙げてみる。
あまり深く詰めて考えていないので、誰かこれでうまくいきそうか検討してくれ。
・まず、りんごの落ちる速度が１／５という制約が面倒なので、
与えられたりんごの位置を５倍にしてから単位時間辺り１マスの割合で
落下する事にする。
・最後に落ちるりんごの位置・時間から "逆算" して求める（動的計画法使用）。

この課題、かなり奥が深いですね…
東北系の学生なんで一丁挑戦してみますｗ

>>11
リンゴの位置を5倍にしなくたって、
単純に落下する(y=0になる)時間を求めればいいだけじゃあないの？

東北限定じゃなかったら、漏れも出場したのに。
Robocodeでもやろうっと。

>>11
予選はその戦略でOKだと思う。
計算時間はO(MN)ですみそうだし。

でも本選は、似てるようで全くちがうゲームだし、難しいかも。

東北限定かよ(´Д｀)
考えて損した

東北のプログラマはDQNばっかり。まともな奴を見たためしがない。

予選ゲームでは、nが100万とかでも対応できるモノじゃないといけないのかな？

>>17
そういう質問すると
「常識の範囲で」
と返事をいただける罠。

常識が分からない場合はどうすればいいですか。

＞実際に用いるデータとして，N, M <= 100，n <= 1000 の規模のものを考えております．
読めよ

東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。
東北のプログラマはDQNばっかり。まともな奴を見たためしがない。

とりあえずn=1000の計算をしたが、
clock()の精度以下の時間しかかからんかった
でn=100000にすると159.48秒でした
AthlonXP1800+,WindowsXP
ついでに言うと、サンプルで付いてくる
move100.txtは42個しかとれんぞ、
俺の求めた最適解なら49個とれるのに・・・

>>22
＞ついでに言うと、サンプルで付いてくる
＞move100.txtは42個しかとれんぞ、

そりゃ、サンプルなんだから、優秀なプログラムじゃ困るっしょ。
サンプルプログラムを逆アセンブルして動作原理の解説をつけるだけで
予選通過するようじゃマズイし。

>>23
サンプルで付いてきたのは、
入力ファイルと出力ファイルを渡すと
アニメーションで経過を示してくれて、
実際何個とれるかを試すアプリケーションと
サンプルの入力ファイルとそれに対する出力ファイルです。
デバック用にお使いくださいと書いてあるんだから、
サンプルで与えられた解が最適解じゃないと
自分で作ったものが最適解なのかどうかも
試せないんじゃないかなと思ったりする。

>>17,18,20
>応募時に送付されたプログラムを，以下の観点から客観的に審査します．
>さまざまな入力データに対する成績
>実行時間
>動作原理の説明書の内容
>その結果，上位１６チームを本選出場とします．
何処にも「N, M <= 100，n <= 1000 程度の問題を解ければ予選通過です」とは
書いていないという罠。
「N, M <= 100，n <= 1000」という数字は
出題者が「どうせ餓鬼共ならこのぐらいのレベルしか解けないだろ、hahaha...」
と言う感じで出したものだと思うが。
当然、レベルが高い奴等が多数出場すれば、この程度の問題が解けても
落とされるのは自明だろう。

>>25
「問題仕様」のところに
「なお，実際に用いるデータとして，
N, M <= 100，n <= 1000 の規模のものを考えております．」
と、書いてあるんだから、少なくとも
「さまざまな入力データに対する成績」
で入力されるデータは
「N, M <= 100，n <= 1000 」
だと思うんだがな。
「考えております」っていう表現は非常に曖昧だけど
しかも、解ければ予選通過だとかだれもいってないけどな。

>>14
この問題N,Mの大きさは計算速度に関係ないのでは？

ほかに参加できそーなプログラミングコンテストってないのか？

>>22
マジで？
俺のだと48個なんだけど。
・・・見直してみよう

30

>>27
確かに「計算速度」に影響があるのはマシンのスペックだけだと思うが・・・
ところで君はどういう方法で検索しようと思っているの？
アルゴリズムを提示してくれ。

>>13
（遅レススマソ）
よくない。

>注意： りんごは同一の座標に 5 ステップ滞留しますが，y=0 のマスに限り
>2 ステップ目以降には消失し，後から籠が移動してきてもキャッチできません．

>>31
…もしかして M×N の配列とってたり…してないよね？

>>32
いやだから、y=0となる時刻をt_0とすると
t_0=t + y * 5;
で計算して、t_0とxがあれば求まる、
なにもt_0から5ステップとどまるような計算をするとは言っていない。
ってよく考えたら、yを5倍してるな・・・ｽﾏｿ
>>31
マシンのスペックだけが計算速度に影響する？？
Pentium 100MHzでO(n!)のアルゴリズムと
Pentium4 2.8GHzでO(n^2)のアルゴリズムで
n=10000とかの計算をさせたらどちらが早いでしょうかね？
計算速度って言うのはアルゴリズムとしての速さだけど
どうしてこの計算をするのに、
x軸、y軸の大きさが関係するのかがわからんのだが・・・
そりゃ、longに収まらないほど大きな値だったら別だけど、

しまった逆だ！！！

Pentium 100MHzでO(n^2)のアルゴリズムと
Pentium4 2.8GHzでO(n!)のアルゴリズムで

>>29
参考までに俺の出力ファイル（ちと迷惑かも知れんが）
これで確かにサンプルのapple100.txtファイルで49個とれる
0
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s r r r r r r r r r r r r
r r r r r r r r r s s s s s s s s s s s s s s s s s s s s s s s s s s s r r r r r r r r r r r r r r
r s l l l l l l r r r r r r r r r r r r r r r r r r r r r r r r r r r r r r s s l l l l s s s s s s
s s s s s s s s l l l l l l l l l l l l l l l l l l s s s s s s s s l s s s s s s s s s r s s s s s
s s s s s s s s s s s s s s s s s s s s s r r r r r r r r r r r r r r r r r s s s s s s s s s s s s
s s s s r r r l l l s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s l l s s s s s
r r r r r r r r s s s s s s s s l s s s l l l l l l l l l l l l l l l l l l s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s r r r r r r r s s l l l l l l l l l l l l l l l l l l l l l l s s
s s s s r r r r r r r r r r r r r r r r r r r r r s s s l l l l l l l s s l l l l l l s s s s s s s
s s s s s l l l l l l l l s s s s s s s s l l l l s s s s s s s s s s s s s s s l l l l l l l l l l

続き
l l l l l l l s s s s s s r r r r s s s s s s s s s l l l l l l s r r r r r r r r r r r r r r r r r
r r r r r s s s r r r r r r r r r r r r s s s s s s s s s s s s s s s s s l l l l l l l l l l l l l
l s s s s s s s s s s s s s r r r r r r r r r r r r r r r r r r r r r r r r s s s s s s s s s s s s
s s s s s s s s s s s s l s s s s s s s s s s s s s s s s s s s s s s r r r r r r r r l l l l l l l
l l l l l l l l l l l l l s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s r r r r r
r r r r s s s s s s s s s s s s s s s s s s s s l l l l l l l l s s s s s s s s s s s s s s s s s s
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s r r r r r r s s s s s s s s l l l l l l l
l l l l s s s s s s s s s s s s s s s r r r r r r r r r r r s s s s s s s s s s s s s s s s s s s s
l l l l l l l l l l l l l l s s s s s s s s s s r r r r r r r r r r r r r r s s s s r r r r r r r s
s s s s s s s s s s s s s s s s s s s s r r r r s s s s s s s s s s s s r r r r r r r s s s s s s s
s s s s s s r r s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s l l l l l l l l l l l l
l l l l l l l l l l l s r r r r r r r r r r r r r r s s s s s s s s s s s s s s s s s s s s s s s s
s s

>>34
一般にアルゴリズムの良否を決めるのは
「計算速度」ではなくて「計算量」だと思ったのだが・・・

>>38
むう、
計算量という言葉がでてこなかっただけです

>>36
個々の回答はもうどうでもいい。
ソースうｐしれ！（ｗ

>>34
バグが直ったので試しに出してみた。
同じ解が出たよー。４９個。

こっちも全検索でやってます。
枝の方から探すとか、線形計画法とか、
まあヘンなことはやってますが。

>>40
それじゃあコンテストにならんだろ

>>42
>それじゃあコンテストにならんだろ
それを敢えてやってしまうのが２ｃｈだろ

じゃあ、チーム2chで出るか・・・

結局ま板のレベルは低い、と言うことで。

>45
ま板って書くとまろやか板みたいだから嫌。

とりあえず、うｐしてみたりして。。。（ｗ
http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20020915162730055.lzh

>>47
ウイルス

>>48
拡張子が .c のウイルスか。。。
珍しいな（ｗ

>>33
（またまた遅レススマソ）
上記の通り、見事にM×N の配列とってたりしてますが、何か？

>>47
なるへそ、そのアルゴリズムならM×N、
正確には(M*5+T)*Nで計算できるのか・・・
しかし、tについては範囲が限定されていないため、
入力データによっては不利な可能性があるなぁ、メモリも食うし、
計算量がリンゴの数nに関係する計算とどちらが有利なんだろう？

ブルブル４９．最適解かつブルブル震える

0,r,l,r,l,l,r,l,r,r,l,l,r,l,r,l,r,l,r,l,r,r,l,r,l,r,l,r,l,r,l,r,l,r,l,l,r,r,l,l,r,r,l,l,r,l,r,r,l,l,
r,l,r,r,l,l,r,l,r,r,l,r,l,l,r,r,l,l,r,r,l,l,r,r,l,r,l,r,l,l,r,r,l,r,l,l,r,r,l,r,l,l,r,r,l,r,l,r,l,l,
r,r,l,l,r,l,r,r,l,r,l,r,l,r,l,r,l,r,l,l,r,l,r,r,l,l,r,l,r,l,r,l,r,l,r,l,r,s,s,l,r,l,r,l,r,r,l,l,r,r,
l,l,r,l,r,l,r,r,l,r,l,l,r,r,l,s,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,s,r,r,r,r,r,r,r,r,r,r,r,r,
r,r,r,l,l,l,l,l,l,s,s,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,l,l,r,l,r,l,r,l,
r,l,r,s,s,l,l,l,l,l,r,r,l,l,r,s,s,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,r,r,l,l,r,r,l,s,l,r,l,l,r,l,
r,l,r,r,l,r,l,r,l,r,l,r,l,l,r,l,r,l,r,s,s,r,r,l,l,r,r,l,l,r,r,l,r,l,l,r,s,s,r,r,r,r,r,r,r,r,r,r,r,r,
r,r,r,r,r,r,r,r,l,r,l,r,r,l,r,l,r,l,r,l,l,r,l,r,l,r,r,l,l,r,r,l,r,l,r,l,l,r,r,l,s,l,l,l,l,r,l,r,s,l,
l,l,r,r,l,l,r,s,s,r,r,r,r,r,r,r,r,l,r,s,l,l,r,r,l,r,l,r,l,r,l,r,l,r,l,r,l,r,l,r,l,r,l,r,l,l,r,r,l,s,

続き

l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,s,s,r,r,r,r,r,r,r,l,r,l,r,s,s,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,
l,l,l,l,l,l,r,s,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,s,s,l,l,l,l,l,l,l,l,r,l,r,r,l,l,r,l,r,s,s,
l,l,l,l,l,l,r,l,l,r,r,l,s,s,l,l,l,l,l,l,l,l,l,r,r,l,l,r,r,l,l,r,r,l,r,l,s,l,l,l,l,r,l,l,r,s,s,l,l,l,
l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,r,r,l,l,r,l,r,s,r,r,r,r,s,l,l,l,l,l,l,l,r,s,r,r,r,r,r,r,r,r,r,r,r,r,r,
r,r,r,r,r,r,r,r,r,l,r,r,l,l,r,r,l,l,r,l,r,r,l,l,r,s,r,r,r,r,r,r,r,r,r,r,r,r,l,l,r,l,r,l,l,r,l,r,s,s,
l,l,l,l,l,l,l,l,l,l,l,l,l,r,s,l,r,r,l,r,l,l,r,r,l,l,r,r,l,r,l,r,l,l,r,r,l,s,s,r,r,r,r,r,r,r,r,r,r,r,
r,r,r,r,r,r,r,r,r,r,r,r,r,r,l,l,r,r,l,l,r,r,l,r,l,l,r,r,l,r,l,l,r,s,s,l,r,r,r,r,r,r,r,r,l,r,r,l,l,r,
l,r,l,r,r,l,r,l,l,r,r,l,r,l,r,l,r,l,r,l,r,l,l,r,s,s,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,r,l,l,r,
l,r,l,r,l,r,l,r,l,r,l,r,r,l,s,s,r,r,r,r,r,r,r,r,r,r,l,l,r,r,l,r,l,l,r,l,r,l,r,l,r,l,r,r,l,l,r,r,l,s,
s,l,l,l,l,l,l,l,l,l,r,r,l,r,l,l,r,l,r,r,l,l,r,l,r,l,r,r,l,s,l,r,l,r,l,r,s,s,r,r,r,r,r,r,l,r,r,l,r,l,
r,l,l,r,l,r,l,r,s,l,l,l,l,l,l,l,l,l,l,l,r,l,l,r,l,r,r,l,r,l,r,l,r,l,l,r,l,r,s,s,r,r,r,r,r,r,r,r,r,r,
r,r,l,r,l,l,r,l,r,s,s,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,r,s,s,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,l,r,l,r,l,l,
r,r,l,r,l,r,l,r,l,l,r,r,l,s,r,r,r,r,r,r,r,l,r,r,l,l,r,l,r,r,l,s,s,r,r,r,r,r,l,l,r,l,r,r,l,l,r,r,l,s,
r,r,r,r,r,r,r,r,l,l,r,r,l,l,r,l,r,r,l,r,l,l,r,r,l,r,l,l,r,r,l,l,r,l,r,s,s,r,r,s,l,l,l,l,l,l,l,l,l,l,
l,l,l,l,l,l,l,l,l,l,l,l,l,r,l,r,l,r,l,r,l,l,r,r,l,r,l,r,l,r,l,l,r,r,l,r,l,s,s,r,r,r,r,r,r,r,r,r,r,r,
r,r,r,

とりあえず、このスレ見てる奴らの中で
このコンテストに潜れる奴いるの？
いたら本気で支援してやる。





VBだけど…

ついでに説明書＆実行ファイルも作ったぞ。

後は提出するだけだな・・・

http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20020916133801063.lzh

n=100じゃ全然比べらんないから、n=1000,10000くらいのやつだれか作んない？

>>56
りんごのデータの事？

つーかこんな簡単に最適解が求められていいんだろうか？
コンテストとして成り立つのか？

>>57
そそ
作るのは簡単だけど、アップが面倒

>>59
自動作成すればよろし。
シードと乱数発生ルーチンを自前で提供すれば皆共通で使える。
後はりんごの数（RINGO_NUM）を幾らでも増やせば良い。

#include <stdio.h>
#define MYRAND_MAX 32767
unsigned long next=123;
int MyRand(void){next=next*1103515245L+12345;return(unsigned)(next/65536L)%32768U;}
#define MyRandom(num)(int)(((long)MyRand()*(num))/(MYRAND_MAX+1))
#define RINGO_NUM 1000
#define M_MIN 22
#define M_MAX 46
#define N_MAX 64
#define T_MAX 2000
int main(void){int i;for(i=0;i<RINGO_NUM;i++){
int m=MyRandom(M_MAX-M_MIN)+M_MIN;int n=MyRandom(N_MAX);int t=MyRandom(T_MAX);
printf("%d,%d,%d\n",n,m,t);}return 0;}

>>60
おお、なるほど〜。


網探索系で作ってみたんだけど、MとかNが少ないときは配列作ったほうが圧倒的に早いねー

計算量：O(n)
メモリ：O(n)

ただしソートが入るからO(nlogn)かも…。

うお、肝心なとこミス。

計算量：O(n^1.2)

くらいかも。よく調べてない。

この問題、例えばｔでソートする場合、
上限下限が分かってるからバケットソートが使えるわけだが
ほんとに早くなるかな？？

>>63
あれO(n)でしょ？
試したことあるんだけど、むちゃ早くなるよ。

しかし、nが比較的小さい場合かえって遅い可能性も高かったりする罠

大体決まりきった、データ構造を使えばできるし、コンテスト自体
無意味だな

＞情報処理技術における戦略立案能力や問題解決能力を競うものです．
＞将来の情報技術産業を担う学生のみなさんの実力を世に問う絶好の機会
＞ですので・・
・
何が実力だよ。糞じゃねえか糞

>>66
でも糞以下のお前にはできんな

もう予選の問題のレベルが低いことはわかったから、本選の話でもしようよ。

>>67
馬鹿ハケーン、ただ言ってみただけだったんだね
コンテストなんか実務で全く役に立たないよ。

>>68
本選も面白くないぞ…

改良後1000000個のデータで2.16秒
これだけデータがでかいと、
読み込むだけで1秒以上かかってしまっている・・・

>>69
コンテストは実務で役に立たない。
実務で役に立てたかったら実務やれってか。
当たり前の事言ってんじゃねーって。

>>72
あほか

全検索でやってる人が多いみたいだけど、
これは遺伝的アルゴリズムとかいうのを使えっていう問題なの？
あれ実用的でないから使ったことないんだけど・・・。

ちなみにexeで提出ってことはjavaじゃだめｼﾞｬﾝ
漏れの一番の得意言語がダメなのでやる気を失った・・・。

> コンテストなんか実務で全く役に立たないよ。
> コンテストなんか実務で全く役に立たないよ。
> コンテストなんか実務で全く役に立たないよ。
> コンテストなんか実務で全く役に立たないよ。

>>74
そりゃ読み過ぎ。
そんなの想定してたら、高専なんか参加させないでしょ。

遺伝的アルゴリズムって何？

>>76
あれってそんな高度なの？
たしか大学で普通に教えてたみたいだけど・・・。
漏れは取らなかったけどね。

>>77
全部に対してサーチするんじゃなくて、
一度ランダムにやってみて
優秀なのについてそれに似たのをどんどんやっていく
とかいうやつだったと思う。
あまり詳しくないんで、詳しくは自分で調べて。

おいらの回答.
http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20020918235410019.zip

>>74
GAじゃ最適解検索できないじゃん.

>>79
それだとO(n^2)ですか・・・

>>80
ところがどっこい。
ほぼO(n)ですよ。

>>81
一番最初のソートはともかく
まずmake_treeで
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
なんてやってるので1/2(n-1)nのループ
さらに、
solveでも、一度検索した枝は追わないようにしているけど、
すべての木を検索するわけだから、すべてのリンゴについて
for(j=0;j<tree[i].nreach;j++)
のループがかかってるわけで、tree[i].nreach〜n-iだから
全部のループをあわせれば1/2(n-1)n程度のループが必要になっている

オーダーはO(n^2)になると思うんだが？
どこで計算量を減らしてる？
ちなみに、このアルゴリズム、
俺が一番最初に考えたのとほぼ一緒だと思う

あー、そうか。O(N^2)かも。

make_treeなくしてもソートさえしてれば
ほぼ同じように動くから変えてみようかな。

とりあえず、動的計画法じゃない方法を
使ってる奴を出したかったので。

ごめん、追記。

俺がこだわりたいのは「籠の怪しげな動き」であって
問題を解くスピードじゃなかったり。
行き過ぎてヨタヨタ戻る、とかやってみたくてさ。

http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20020919141414007.lzh

<100>
OK. Total 49 apples are catched.
Total time to take is 00:00:00.0100144.
<1000>
OK. Total 146 apples are catched.
Total time to take is 00:00:00.0100144.
<10000>
OK. Total 725 apples are catched.
Total time to take is 00:00:00.1502160.
<100000>
OK. Total 6933 apples are catched.
Total time to take is 00:00:01.5221888.
<1000000>
OK. Total 68503 apples are catched.
Total time to take is 00:00:15.1718160.

M,N,n,tは無制限。1/tに比例してO(n^2)に近づきますが、普通の環境ではO(n)です。

そだ。計測時間は入力とソート、出力時間は除いてあります。
入力に正規表現使ったから、ホントにTotalだと劇遅。。。

こんなにあっさり最適解が求められるのに､どうやって審査するんだろ？
実行時間は言語によっても変わるだろうし､書類で客観的評価ってのも……

>>87
でも、最適解を求める事が非常に難しい課題で
審査を行うことの方がむしろ大変だと思うが。
１６組を選ばなければならない時に、
最適解を求められた組がたった１組しかない場合、
当然、解が求められていない組からも合格者を
選ばなければならない。
こんな時に客観的に審査する方法はないのでは？

実際、本選課題の最適解を求める事は非常に難しいだろうし。

(さて、そろそろ本選課題の方も考えてみるか・・・)

本選課題を考えていたんだが、あまり良い方法が思いつかない。
ヒントも役に立たないし・・・

誰か、いいアイデア持っている人いない？（特に>>70）

・自分が相手より先行して捕獲できる場所で捕獲した林檎について+4,+3を計上する。
・相手が自分より先行できる林檎について、+1,+2を計上する。

総ポイントが高いルートを選択。

相手の行動なんぞ下手に予測すると余計にスコアが悪くなる気がするよ。

>>89
なんか「じゃんけん大会」みたいになりそう。
最強プログラムがたくさんあって
プログラムA は プログラムB に勝ち、
プログラムB は プログラムC に勝ち、
プログラムC は プログラムA に勝つ。
みたいな。

運がよかった人が優勝？

相手の動きを見て、次のプログラムを差し替えてもかまわないとか言ってるけど
それって、相手の動きを見ただけで、
使っているアルゴリズムを見極められる人ってそうそういないと思う

フギャー
SuperConの方が高度だな

それ最適解とはかぎらないよ

これは最適解を求める問題ではないと思われ

・さまざまな入力データに対する成績
・実行時間
・動作原理の説明書の内容
その結果，上位１６チームを本選出場とします．

や

なるべくたくさんのりんごをキャッチする籠の動かし方を求めるプログラムを作成してください

など最適解を求めろとかは書いてない。
なるべくたくさん！＝最適解
でないかい？
最適解に近い方がいいに決まっているけど、
処理時間なども考えるのが妥当じゃないか？
それがいいアルゴリズムというものじゃないか？

>>95
しかし、最適解でさえ、O(n)で求まる以上、それだけでいいんではないかと

平均時間が最小なのか、
最悪時間が最小なのか、
など最適にもいろいろある

>>95
なるほど。全ての問題に対して最適解を求めるのが必須ならば、「さまざまな入力データに対する成績」
はナンセンスだよな。だとすれば、むしろ「実行時間」のほうが重視されるのかもしれない。

最適解じゃないけどO( log(n) )なアルゴリズムとかもあるのかも知れない。
（本当に実現可能かどうかは知らんが）

ついでに、オーダーが同じだからと言っても実際の実行時間は全然違う場合もあるし。
例えば quick sort と merge sort は両方ともO( nlog(n) )だけど、実際にはquick sort
のほうが速い ( nの大きさと実装方法にも依存するが。 )

もちろん、>>97にも同意。

あと、どうしようも無くなったときは、「動作原理の説明書の内容」を重視して
マニュアルコンテストにしてしまうのかもしれないね。

正直あんたら関係者じゃないかと、、、、

>なお，実際に用いるデータとして，N, M <= 100，n <= 1000 の規模のものを考えております．


ゼロの数が圧倒的に足りねえよ。最適解を出して瞬間的に終わるんだから。

最適解を導くと時間が掛かるから、近似解で実用的な処理時間にする、なら分かる。
でも最適解で十分高速なら最適解が一番いいにきまっとるだろうが。

>>99
>正直あんたら関係者じゃないかと、、、、
へ？
どして？

>>98
> 例えば quick sort と merge sort は両方ともO( nlog(n) )だけど、実際にはquick sort
> のほうが速い ( nの大きさと実装方法にも依存するが。 )
ランダムデータの場合はな
quick sortに既にソート済みのデータをソートさせるとバブルソートよりも遅くなることがある

>>100
ホムペに書いてあることを主催者に都合のいいように解釈してるように見えるから。

>>102
俺は，もしこのスレで叩かれてるような事態になったとき、主催者はどういう対処を
してくるかな？と思って書いた。

うまく逃げ道が作ってあるという意味では、あの募集要項はうまく出来てると思う。

応募者のレベルが予想できないような場合，あのように幅を持たせたルールが
一番良いのかもしれない。

>>103
おれが工作員だと思った根拠な、、、

>俺は，もしこのスレで叩かれてるような事態になったとき、
>主催者はどういう対処をしてくるかな？と思って書いた。

これスレで話してたのは「そもそもそういう事態になること自体おかしい」ってこと。
そういう事態になった上で運営するための対処なんか知らんよ。

>うまく逃げ道が作ってあるという意味では、あの募集要項はうまく出来てると思う。

「うまく〜という意味」条件文の中に、すでに「上手い」という言葉があるから、
ゆえに条件の中で議論する限り結論も「上手い」ものになる。

この場合は逃げ道がフル活用されそうなことが問題なのであって、
逃げ道自体の質を問うてもまったく意味がない。
なんとしても良い点を探しているあたりも工作員の匂いだよ。

>応募者のレベルが予想できないような場合，
>あのように幅を持たせたルールが一番良いのかもしれない。

問題の難易度と、問題がコンテストとして成立するかは別物。
「参加者のために曖昧にした」なんてまさしく主催者側の弁明じゃないか。

>>104
主催者は、当然主催側に都合よく運営するはず。
なので、こちらとしては、主催者にいちいち文句なんて言ってないで、
それを見越した（＝主催者に都合のいい解釈での）行動、
戦略をとるべきだと思うよ。

ていうか、このスレ東北地方在住の参加者とか見てないの？
憶測であれこれ騒いでてもつまらぬ。
リアル参加者希望。

>>104
妄想を逞しくするのは個人の勝手だが、最適解が（簡単に）出るのは
あくまでも予選だけだろ。
開催者側にとっては本選こそが重要な訳で、予選課題なんてものは
足きりの道具にしか過ぎないのでは？
俺の目から見ても今回の募集要項は（それなりに）旨く出来ていると思う。

>この場合は逃げ道がフル活用されそうなことが問題なのであって、

逃げ道をフル活用される事に何か問題でもあるのか？
それが嫌なら、自分のコードをどっかにうｐして、最近やっと "Hello world" が
書けるようになったレベルの香具師らにばんばんコピペ（＆提出）させる様に
する事こそが、逃げ道をふさぐ一番の方法だと思うが（つーか、
漏れはそうなることが面白いので、うｐしたんだけど）。

俺が間違ってたわ。

まさか主催者の裏の意図を読み取ったり、心理的な駆け引きを主眼とした
コンテストだとはいまのいままで気がつかなかった。漏れはマ的に純粋な
競技を考えていたので的外れになってしまったみたいね。

age

*ｅ+６*ｌ+ｔ*０+g+＠*）+ｇ*）+４*ｋ+８*ｅ+ｋ*４+ｑ*ｅ+
の意味なんだか分かりますか？

何？こんな軽い課題でええんか？
大学１年だけど優勝しちゃる！！

>>110
答えは？

216.244.20.121
62.94.97.221
61.221.90.100
210.249.200.38
211.207.44.214
210.249.200.243
210.249.200.144
こいつら、毎回アタックかけてきてウザイ

>>112
アタックって何ですか？

ﾊﾞｸﾞを出したら、ﾕﾒだった。
会社に着いたら、ｸﾋﾞだった

汁ｶ！

応募人数が16チームを下回った場合どうなるんだろうか・・・
Webでしか宣伝されてないから、存在自体知らない人が多いと思う・・・

>>112
同じＩＰからは来ていなかった。
宝くじの番号確認みたいで、ちと楽しかった朝(w

>>112
Nimdaじゃねーの？

応募しちゃった・・・

>>116
いや、大学の掲示板に張られてるんじゃないかな？

>>119
経過きぼん。

>>120
いやいや、というより、担当の教授が無理矢理
自分の研究室の学生とかを出場させる。

>>121
被害者はこの人たちですか・・・
http://www.maruoka.ecei.tohoku.ac.jp/member.html
学生もそんなに暇じゃないと思うけどな

いよいよ明日が締め切り・・・
応募人数が少ないと言う旨のメールが届いた。
マジで16チームを割ってたりして・・・

>>123 東北大生ﾊｹｰﾝ。
実はそのメール, 俺も貰ったけど…。今さらどうしろと…。
間に合わないから，まじでこのスレで出た回答をコピペして送ってやろうか。

ム板にスレたててたならもうちょっと盛り上がったかもな。
明日になれば、後の祭りだが。

アトノ祭りマンセー。

予選結果はどうなったんだ？

予選通過した。
35チームが応募し
20チームが本戦通過だそうだ。
16チームではなかったのか？

結果が出てる
http://ukie.maruoka.ecei.tohoku.ac.jp/procon/passed.html

>>119
おめ age

しかし、せっかくのコンテストなんだから
予選通過者のソースぐらい公開してくれても
よいと思うのだが・・・

>>119
本戦に向けての調子はどうよ？

もうどうすればいいのか、混乱中・・・
一応の作戦としては
1．自分が有利に取れる半分に落ちてくるものにウェイトをつけて優先的にとる
2．何種類かの相手の動きを想定して、相手が取るであろうものを見つけて
自分が優先的に取れる部分に落ちてくるなら、さらにウェイトを上げ、
相手が優先的に取れる部分に落ちてくるなら、さらにウェイトを下げる。
みたいな感じ・・・

他になんか作戦ある？

ソース公開して欲しいなぁ・・・
私の、林檎 1,000個で 23秒・・・

どなたか >>85 のファイル、再UPして頂けないでしょうか？

>>119
めんどくさいから何も考えていない（笑

本戦の要項メール来たね
複雑なルールになったけれど、決勝で会えるようがんばろう！

>>132
２３秒といっても使う計算機に寄るだろ
うちのでも試したいんで、１０００個のデータうｐよろ

>>134
計算機！？ PCスペックで宜しいのでしょうか？
ThinkPad／CPU:PenIII 800MHz／Memory:256MB
clock()にて、処理開始から終了まで・・・
と言っても、読み込み＆ソートは、0.1秒以下で終わります。

１０００個のデータですが、実は学校に忘れてきまして、
明日でよければ、UPしますが・・・
>>60 さんのソースを使って作らせて頂きましたので、
そちらで作った方が速いと思います。そんな大差無いと思うので・・・

どんなデータであれ、>>85 さんのデータ<1000> で 00:00:00.0100144.
ってのは、私には無理なのです。
ツリー構造なんて使ってるから、遅いのでしょうけど・・・

あ呼ばれてる。

たしかMNtのサイズによってはおれじゃない人のほうのが速かった気がする。
あとあの計測データはファイルの読み込みとソートと出力入れてないから。
ソートとか出力が結構遅い。10000あたりからの話だけど。

ていうか1000個で23秒は遅いねえ。
ちなみにおれのプログラムも本質的にはツリーだったような気がするし。

1000ていう数もある意味異常だが。1000万なら納得。


C#で書いたから、それでいいならうpするけど。

スレ汚して、申し訳ないです。。。
自己解決しました・・・

どうやら、自作ツリー構造クラスの取得する所に、１行追加したら
00:23.00 -> 00:00.17 になりました。

>> 136 さん
C# ですが、私はきっと読めないし、自己解決してしまいましたので、
お気持ちだけ頂きます。
ありがとうございました。

>>132
ここでは、計算機＝ＰＣと思っていいよ

兎にも角にも、速くなったようだね
では、週末に会いましょう

>>137
まあ気にせんでよし。

>>131
先読みができるなら、1つ捨てて3つ取る、みたいなことを実装するとか、
自陣のもの(とくに一番端)をわざと相手に取らせて自分は取りやすいものを回収とか。

…ともっと混乱させてみる(藁

>>140
>自陣のもの(とくに一番端)をわざと相手に取らせて
分かっているとは思うが、本当にそれを相手が取ろうとするかどうかは
対戦前に既に決定しているので、意味が無いと思うが。

コンクール・コンテスト総合掲示板
http://jbbs.shitaraba.com/music/3054/

いよいよ明日、本戦です。
出場する皆さん、会場で会いましょう。

>>143
うまいの出来上がったか？
どうにもよろしくなくて、まだ作業中だー

俺の結論
決着は運だ

なんだか分からないまま、出発の時間と相成りました。
それでは皆さん、頑張りましょう

予選リーグで2勝2敗で3位・・・だめでした

>>147
残念

ACM主催のプログラムコンテストも明日です

>>119
もしかして、Aのリーグにいたか？

>>130
喪前はどうだった？

>>151
予選リーグは突破したものの、決勝でカラリと負けてシマータよ。

で結局 、優勝したのはどんなプログラムだったの?

優勝者曰く「相手の行動の予測を５，６回繰り返し、それに対する最適な動作を探索する。」と言っていた。
説明下手、もしくはあんまり話したくなかったらしく、よく分からなかったぞ。

もう終わったんだからソースの公開等してもらえると嬉しいのだけどね

>>154
説明下手でスマソ
公開の方は開催側から何も連絡がないので、参加者が勝手にやるしかないのかもしれない。
どうやって公開すればいい？

おお、優勝者降臨！
改めておめでとうございます

適当なうｐろだ探しておくからまたあとでよろしく

上で使っていた
http://tool-ya.ddo.jp/2ch/trash-box/index.html
がよいね

たのんます

置いた
http://tool-ya.ddo.jp/2ch/trash-box/contents.jsp?file=20021106190349036.lzh

さんくす
早速拝見させてもらいます

>>130
Aではありません。あんまり言うとばれるのでここまで
>>155
公開してくれたので、もうどうでもいいが、
負けが決まった後、主催側に優勝者のコードとかは公開してもらえるか聞いたら
ソースは著作権があるから公開できないとか言ってたな

分からんから、遺伝的アルゴリズムで。

以降、>>158に勝つアルゴリズムをﾊｹｰﾝするスレとなりますた。

じゃ、ジャッジと集計よろ＞>>162

>>162
予選で負けていたような気がするが＞優勝者
Ｃリーグは見ていたわけではないが、少なくともリーグ１位突破ではなかったようだぞ

>>158
mainの返り値がvoid・・・

返り血・・・ギャー！！

予選は３勝１敗です。決勝３位のチームに負けた。

>>165
voidだと何か問題あるの？返り値使わないときはいつもvoidにしてるんだけど…

>>167
厳密に言うとCではmain()の戻り値はintでなければならないことになっている。
が、このコンテストはそんなことは関係ないので問題なし。

１０万円もらってきますた。

改めておめで�d

記念式典で配られた冊子に一応答えが書いてあったね
零和行列ゲームにモデル化できてマックス・ミニ解が最適らしい
ただし、りんごが数百個になると5分で完全に求めるのはほぼ不可能なので、
5分以内でいかに近似解が求められるかということらしい

って答えでも何でもないか
ちなみに、入賞どころか予選すら通過しなかったのになぜその場にいたのかというと
研究室の方で人数が足りないからと頭数あわせにいかされたのでした

age

（＾＾）

名無し＠沢村ってプログラミングコンテストで優勝したんだろ?

CM見て思いついた

日本
興和
ぬるぽ！

懐かしいスレをあげたな。ものはついでに
今更だけど>>171の
>零和行列ゲームにモデル化できてマックス・ミニ解が最適らしい
は怪しくないか？
例えば、最適解で１個のりんごを取れるとして、
相手がそれを見越して戦略を立てた場合、
自分がそれをまた見越して自分の戦略を変更し、
２個のりんごが取れるようになることもあると思うが
（じゃんけんみたいだな）。

（＾＾）

（＾＾）

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

ハッキリ言ってアメリカなどの多民族国家では黒人の方がアジア人よりもずっと立場は上だよ。
貧弱で弱弱しく、アグレッシブさに欠け、醜いアジア人は黒人のストレス解消のいい的。
黒人は有名スポーツ選手、ミュージシャンを多数輩出してるし、アジア人はかなり彼らに見下されている。
(黒人は白人には頭があがらないため日系料理天などの日本人店員相手に威張り散らしてストレス解消する。
また、日本女はすぐヤラせてくれる肉便器としてとおっている。
「○ドルでどうだ？(俺を買え）」と逆売春を持ちかける黒人男性も多い。）
彼らの見ていないところでこそこそ陰口しか叩けない日本人は滑稽。

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ