bluedwarfの日記: スパコンの解答 9
日記 by
bluedwarf
<a href="http://www.gsic.titech.ac.jp/supercon/supercon2003/yosen-program.html">スパコン2003予選問題解答</a>が公開されました。
期末前なので、詳しい考察はその後にでもしますが、パット見でなにをやっているのかさっぱり分かりません。まぁ、そのあたりが本選出場者と私との違いなんでしょうけど。
ちなみに、私のは...
(自分のコンピューターに残っている奴なので、完成させていないバージョンだけれど、基本アルゴリズム(再帰)は全く同じ)
-----
#include <stdio.h>
#include <string.h>
#define N 100
#define MAX 2048
#define FROM_LEFT -1
#define FROM_RIGHT 1
#define FROM_UP 0
char Table[N][N];
int result[N][N]; /* find_longest_path(y,x,FROM_UP)の返り値を保存 */
int result_from_left[N][N]; /* find_longest_path(y,x,FROM_LEFT)の返り値を保存 */
int result_from_right[N][N]; /* find_longest_path(y,x,FROM_RIGHT)の返り値を保存 */
int main(int argc, char *argv[])
{
int i,j;
FILE *fp;
char buf[MAX];
char longest; /* 最長連鎖を形成する記号の種類 */
int x,y; /* 座標 */
int longest_path = 1; /* 最長連鎖の長さ */
int working_longest_path = 1;
fp = fopen(argv[1],"r");
for(i=0;i<N;i++){
char *p;
p=fgets(buf,MAX,fp);
for(j=0;j<N;j++){
Table[i][j] = buf[j];
}
}
fclose(fp);
for(i=0;i<N;i++){
for(j=0;j<N;j++){
result[i][j] = 0;
result_from_left[i][j] = 0;
result_from_right[i][j] = 0;
}
}
/* 結果を計算するプログラム */
/* デバッグ */
/*
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf("%c",Table[i][j]);
printf("\n");
}
*/
/* 左上からの最長連鎖を再帰的に見つける */
/*
x=y=0;
longest = Table[0][0];
longest_path = find_longest_path(0,0,FROM_UP);
*/
/* 各座標からの最長連鎖を調べる */
for(i=0;i<N;i++){
for(j=0;j<N;j++){
working_longest_path = find_longest_path(j,i,FROM_UP);
if(working_longest_path > longest_path){
longest = Table[j][i];
x = i;
y = j;
longest_path = working_longest_path;
}
}
}
printf("%c %d %d %d\n",longest,x,y,longest_path);
exit(0);
}
/*
指定された位置からの最長連鎖を見つける。
*/
int find_longest_path(int y, int x, int from)
{
int i;
int working_longest_path = 0;
if(from==FROM_UP){
if(result[y][x] != 0)
return result[y][x];
}else if(from==FROM_LEFT){
if(result_from_left[y][x] != 0)
return result_from_left[y][x];
}else if(from==FROM_RIGHT){
if(result_from_right[y][x] != 0)
return result_from_right[y][x];
}
if(x!=N-1 && from!=FROM_RIGHT){
/* 自分より右側の文字を調べる */
if(Table[y][x] == Table[y][x+1]){
i = result_from_left[y][x+1] = find_longest_path(y,x+1,FROM_LEFT);
if(i > working_longest_path)
working_longest_path = i;
}
}
if(x!=0 && from!=FROM_LEFT){
/* 自分より左側の文字を調べる */
if(Table[y][x] == Table[y][x-1]){
i = result_from_right[y][x-1] = find_longest_path(y,x-1,FROM_RIGHT);
if(i > working_longest_path)
working_longest_path = i;
}
}
if(y!=N-1){
/* 自分より下側の文字を調べる */
if(Table[y][x] == Table[y+1][x]){
i = result[y+1][x] = find_longest_path(y+1,x,FROM_UP);
if(i > working_longest_path)
working_longest_path = i;
}
}
return working_longest_path + 1;
}
-----
とりあえずメモリが富豪的である点は反省しているけれど、あとは特に悪い点も見つからず。強いて言うならば、最初に思いついたこの単純なアルゴリズムをそのまま使った点かな?
もうちょっとまじめに考えていれば、予選問題解答のようなコードが思い付いたかもしれないけれど、他の参加者のコードはどんなものだったんだろう?
# レポは?
期末前なので、詳しい考察はその後にでもしますが、パット見でなにをやっているのかさっぱり分かりません。まぁ、そのあたりが本選出場者と私との違いなんでしょうけど。
ちなみに、私のは...
(自分のコンピューターに残っている奴なので、完成させていないバージョンだけれど、基本アルゴリズム(再帰)は全く同じ)
-----
#include <stdio.h>
#include <string.h>
#define N 100
#define MAX 2048
#define FROM_LEFT -1
#define FROM_RIGHT 1
#define FROM_UP 0
char Table[N][N];
int result[N][N]; /* find_longest_path(y,x,FROM_UP)の返り値を保存 */
int result_from_left[N][N]; /* find_longest_path(y,x,FROM_LEFT)の返り値を保存 */
int result_from_right[N][N]; /* find_longest_path(y,x,FROM_RIGHT)の返り値を保存 */
int main(int argc, char *argv[])
{
int i,j;
FILE *fp;
char buf[MAX];
char longest; /* 最長連鎖を形成する記号の種類 */
int x,y; /* 座標 */
int longest_path = 1; /* 最長連鎖の長さ */
int working_longest_path = 1;
fp = fopen(argv[1],"r");
for(i=0;i<N;i++){
char *p;
p=fgets(buf,MAX,fp);
for(j=0;j<N;j++){
Table[i][j] = buf[j];
}
}
fclose(fp);
for(i=0;i<N;i++){
for(j=0;j<N;j++){
result[i][j] = 0;
result_from_left[i][j] = 0;
result_from_right[i][j] = 0;
}
}
/* 結果を計算するプログラム */
/* デバッグ */
/*
for(i=0;i<N;i++){
for(j=0;j<N;j++)
printf("%c",Table[i][j]);
printf("\n");
}
*/
/* 左上からの最長連鎖を再帰的に見つける */
/*
x=y=0;
longest = Table[0][0];
longest_path = find_longest_path(0,0,FROM_UP);
*/
/* 各座標からの最長連鎖を調べる */
for(i=0;i<N;i++){
for(j=0;j<N;j++){
working_longest_path = find_longest_path(j,i,FROM_UP);
if(working_longest_path > longest_path){
longest = Table[j][i];
x = i;
y = j;
longest_path = working_longest_path;
}
}
}
printf("%c %d %d %d\n",longest,x,y,longest_path);
exit(0);
}
/*
指定された位置からの最長連鎖を見つける。
*/
int find_longest_path(int y, int x, int from)
{
int i;
int working_longest_path = 0;
if(from==FROM_UP){
if(result[y][x] != 0)
return result[y][x];
}else if(from==FROM_LEFT){
if(result_from_left[y][x] != 0)
return result_from_left[y][x];
}else if(from==FROM_RIGHT){
if(result_from_right[y][x] != 0)
return result_from_right[y][x];
}
if(x!=N-1 && from!=FROM_RIGHT){
/* 自分より右側の文字を調べる */
if(Table[y][x] == Table[y][x+1]){
i = result_from_left[y][x+1] = find_longest_path(y,x+1,FROM_LEFT);
if(i > working_longest_path)
working_longest_path = i;
}
}
if(x!=0 && from!=FROM_LEFT){
/* 自分より左側の文字を調べる */
if(Table[y][x] == Table[y][x-1]){
i = result_from_right[y][x-1] = find_longest_path(y,x-1,FROM_RIGHT);
if(i > working_longest_path)
working_longest_path = i;
}
}
if(y!=N-1){
/* 自分より下側の文字を調べる */
if(Table[y][x] == Table[y+1][x]){
i = result[y+1][x] = find_longest_path(y+1,x,FROM_UP);
if(i > working_longest_path)
working_longest_path = i;
}
}
return working_longest_path + 1;
}
-----
とりあえずメモリが富豪的である点は反省しているけれど、あとは特に悪い点も見つからず。強いて言うならば、最初に思いついたこの単純なアルゴリズムをそのまま使った点かな?
もうちょっとまじめに考えていれば、予選問題解答のようなコードが思い付いたかもしれないけれど、他の参加者のコードはどんなものだったんだろう?
# レポは?
面白そうなので。 (スコア:1)
叩かれ覚悟でぃ。
here [cool.ne.jp]
速度は回答と一緒ぐらい。
抜いたり抜かれたりって感じ。
1.調べなくてもよいパターンを省く
2.左右下方向にキャッシュを用いる
ただ、ですね。
行数2.5倍 :-P
Re:面白そうなので。 (スコア:1)
#include <stdio.h>
int m[10000],p,t,P,L,T,j,N=100;S(p,l,i){++l>L?P=p,L=l,T=t:0;for(;m[p]=i--;)j=(i
&1?N:1)*(i&2?1:-1)+p,(i&1?p/N:p%N)-(i&2?99:0)&&m[j]==t?S(j,l,3):0;m[p]=t;}main(
int A,char**B){FILE*f;if(A<2?puts("No argument.")*0:(f=fopen(B[1],"r"))||0*puts
("I/O error.")){for(;(t=getc(f))+1;t-10&&p<N*N?m[p++]=t:0);if(p-N*N)puts("Stra\
nge data.");else{for(;p--;)t=m[p],S(p,0,3);printf("x=%d,y=%d,t=%c,l=%d\n",P%N,P
/N,T,L);}}return 0;}
元ねたは、2ちゃんねるの七行プログラミングスレ。
ルールは79Byte + 改行で7行以内。
エラー判定つきではこれ以上短くなる気はしないけど、勇者がいたらソースを拝見したいです。
#実行速度については触れない方向でw
「あとは特に悪い点も見つからず」 (スコア:0)
Re:「あとは特に悪い点も見つからず」 (スコア:1)
どれぐらい遅い?
# 100x100だと思ってなめてたけれど。
// Give me chocolates!
Re:「あとは特に悪い点も見つからず」 (スコア:1)
説明しにくいんですが,隣が自分と同じなら辿っていって...などとしてはダメです.解答のプログラムにアレイが一つしかないのはメモリを節約したからではなくて,それしか必要ないからです.
この辺は考え方の慣れが必要なのかもしれませんね.
Re:「あとは特に悪い点も見つからず」 (スコア:1)
元のデータ以外の計算用アレイ
です.
Re:「あとは特に悪い点も見つからず」 (スコア:1)
一応、ソース [okotama.org]。
ただ、この差が少ないというのはCPUのキャッシュとかに依存した結果で、もっと小規模なCPUで動かした場合などはもっと差が開いてくると思います。
# ちなみに、自分のコードはもっと遅かった(ぉ
# DiskSystemのRAMアダプタ使ってもギリギリだったからと言い訳。
# はっきりいって、素直に解いた方が速いです。
もうちょっと創意工夫が試される問題でも良かったのではないかなぁ。。
Re:「あとは特に悪い点も見つからず」 (スコア:0)
プログラミングで食っていくつもりなら。
Re:「あとは特に悪い点も見つからず」 (スコア:0)