パスワードを忘れた? アカウント作成
452369 journal

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;
}
-----

とりあえずメモリが富豪的である点は反省しているけれど、あとは特に悪い点も見つからず。強いて言うならば、最初に思いついたこの単純なアルゴリズムをそのまま使った点かな?

もうちょっとまじめに考えていれば、予選問題解答のようなコードが思い付いたかもしれないけれど、他の参加者のコードはどんなものだったんだろう?

# レポは?
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり

読み込み中...