fc2ブログ



お城の堀

2007.09.29 18:23  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題09 お城の堀

概要

2次元配列上に地面'.', 堀'#', 天守閣'&' で表されたお城の見取図が与えられ、忍者が見取図の外側から天守閣(見取図上に1つしかない)に至るまでに、堀から這い上がらなくてはならない最小回数を求めよ。忍者は堀の中および地面を東西南北4方向に動くことができる。例えば

.###.
#...#
#.&.#
#...#
.###.

の見取図では、答えは 1

#######
#.....#
#.###.#
#.#&#.#
#.###.#
#.....#
#######

の見取図では、答えは 2

######
######
##..##
##&.##
##..##
######
######

の見取図では、答えは 1
(※忍者は堀を泳ぐことができるので、2 ではない)

########################################
#......................................#
#..#########...######################..#
#..#.......#...#....................#..#
#..#.......#...#.##################.#..#
#..#.####..#...#.#..........#.#...#.#..#
#..#.#..#..#...#.#....#######.#...#.#..#
#..#.####..#...#.#....#.......#...#.#..#
#..#.......#...#.#....#.#####.#...#.#..#
#..#.......#...#.#....#.#.&.#.#...#.#..#
#..#########...#.######.#####.#####.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#....................#..#
#..............######################..#
#......................................#
#......................................#
########################################

の見取図では、答えは 4


見取図のサイズは最大 100 × 100 である。

解法

天守閣'&'の位置(ci, cj)から深さ優先探索を反復することによって解くことができます。
(ci, cj) と隣接する地面、それらに隣接する地面...を色0で塗りつぶします。
色0に隣接する堀、それらに隣接する堀...を色1で塗りつぶします。
色1に隣接する地面、それらに隣接する地面...を色2で塗りつぶします。
色2に隣接する堀、それらに隣接する堀...を色3で塗りつぶします。
.
.
.
この処理の過程で、見取図からはみ出た時点の色nの半分が解となります。

サンプルプログラム

001 #include<iostream>
002 #include<string>
003 #define MAX 100
004 using namespace std;
005 #define GROUND '.'
006 #define CASTLE '&'
007 #define MOAT '#'
008 #define INFTY (1<<21)
009 
010 int H, W;
011 char G[MAX+2][MAX+2];
012 int T[MAX+2][MAX+2];
013 pair<int, int> castle;
014 
015 bool fill( int i, int j, int color, char target ){
016     T[i][j] = color;
017     if ( i == 0 || j == 0 || i == H + 1 || j == W + 1 ) return true;
018     static const int di[4] = {0, -1, 0, 1};
019     static const int dj[4] = {1, 0, -1, 0};
020     int ni, nj;
021     for ( int r = 0; r < 4; r++ ){
022         ni = i + di[r]; nj = j + dj[r];
023         if ( (G[ni][nj] == target && T[ni][nj] == INFTY) || T[ni][nj] < color ){
024             if ( fill( ni, nj, color, target ) ) return true;
025         }
026     }
027     return false;
028 }
029 
030 int compute(){
031     int color = 0;
032     
033     for ( int i = 0; i < H + 2; i++ ){
034         for ( int j = 0; j < W + 2; j++ ) T[i][j] = INFTY;
035     }
036     
037     while(1){
038         if ( fill( castle.first, castle.second, color, GROUND ) ) return color;
039         color++;
040         if ( fill( castle.first, castle.second, color, MOAT ) ) return color;
041         color++;
042     }
043 }
044 
045 bool initialize(){
046     cin >> W >> H;
047     if ( W == 0 && H == 0 ) return false;
048     for ( int i = 0; i < H + 2; i++ ) G[i][0] = G[i][W+1] = GROUND;
049     for ( int j = 0; j < W + 2; j++ ) G[0][j] = G[H+1][j] = GROUND;
050     
051     for ( int i = 1; i <= H; i++ ){
052         for ( int j = 1; j <= W; j++ ) {
053             cin >> G[i][j];
054             if ( G[i][j] == CASTLE ) {
055                 castle = make_pair(i, j);
056                 G[i][j] = GROUND;
057             }
058         }
059     }
060     return true;
061 }
062 
063 main(){
064     while(initialize()){
065         cout << compute()/2 << endl;
066     }
067 }
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




カードの総和

2007.09.28 10:27  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題07 カードの総和

概要

m (m < 8)種類(各種類のカードは複数(<11)存在する)のカードの集合から数枚カードを選んで、カードに書かれた数字の合計が n になるような組み合わせ数を出力せよ。

解法

再帰関数によって、全てのカードの組み合わせについての数字の合計を試します。
再帰関数内では、k 種類目のカードを 0 枚から amout[k] (k 種類目のカードの枚数)枚選んで、
k + 1 種類目のカードを選ぶ処理に移ります。
この過程で、選んだカードにかかれた数字の合計 v を計算していき、v が n と等しくなったとき、
カウンターを増やします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 7
004 
005 int m, n, counter;
006 int value[MAX], amount[MAX];
007 
008 void recursive( int k, int v ){
009     if ( v == n ) {
010         counter++; return;
011     } else if ( v > n || k >= m ) return;
012     
013     for ( int a = 0; a <= amount[k]; a++ ){
014         recursive( k + 1, v + value[k]*a );
015     }
016 }
017 
018 int main(){
019     while( cin >> m, m ){
020         for ( int i = 0; i < m; i++ ){
021             cin >> value[i] >> amount[i];
022         }
023         int g; cin >> g;
024         for ( int i = 0; i < g; i++ ){
025             cin >> n;
026             counter = 0;
027             recursive(0, 0);
028             cout << counter << endl;
029         }
030     }
031     return 0;
032 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




マス目

2007.09.28 09:55  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題04 マス目

概要

各要素が 0 または 1 である n × n (n < 256)の2次元配列が与えられ、上下、左右、または対角線方向に並んだ 1 の列のうち、長さが最大のものの長さを出力せよ。

例えば、以下のような入力に対しては、4 を出力する。

00011
00101
01000
10101

解法

動的計画法で解きます。
T[i][j][k] を G[i][j] から k 方向(k は右上、上、左上、左の4種類)に 1 が連続する数とします。
これを各列(j)を左から右、各行(i)を上から下という順番で計算していきます。
G[i][j] が 0 であれば、T[i][j][k] (k = 0, 1, 2, 3) は 0 となり、
G[i][j] が 1 であれば、
T[i][j][0] = T[i-1][j+1][0] + 1 (右上),
T[i][j][1] = T[i-1][j][1] + 1, (上)
T[i][j][2] = T[i-1][j-1][2] + 1 (左上),
T[i][j][3] = T[i][j-1][3] + 1 (左)
となります。
T の要素の最大値が答えとなります。

サンプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 255
005 
006 int n;
007 char G[MAX+2][MAX+2];
008 int T[MAX+2][MAX+2][4];
009 
010 void compute(){
011     for ( int i = 0; i < n + 2; i++ ){
012         for ( int j = 0; j < n + 2; j++ ){
013             for ( int k = 0; k < 4; k++ ) T[i][j][k] = 0;
014         }
015     }
016     
017     static const int di[4] = {-1, -1, -1, 0};
018     static const int dj[4] = {1, 0, -1, -1};
019     
020     int maxv = 0;
021     
022     for ( int i = 0; i <= n; i++ ){
023         for ( int j = 0; j <= n; j++ ){
024             if ( G[i][j] == '1' ){
025                 for ( int k = 0; k < 4; k++ ){
026                     T[i][j][k] = T[i+di[k]][j+dj[k]][k] + 1;
027                     maxv = max( maxv, T[i][j][k] );
028                 }
029             }
030         }
031     }
032     
033     cout << maxv << endl;
034 }
035 
036 main(){
037     while(cin >> n, n){
038         for ( int i = 1; i <= n; i++ ){
039             for ( int j = 1; j <= n; j++ ) cin >> G[i][j];
040         }
041         compute();
042     }
043 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




パソコン甲子園2007予選 

2007.09.28 01:15  パソコン甲子園 2007

パソコン甲子園2007予選問題

番号問題難易度点数
01 キャンディーとクラス期 3
02 視力検査 3
03 双子素数 8
04 マス目 ★☆ 8
05 ボウリングのスコア計算 ★★ 8
06 三角形と円 ★★★ 8
07 カードの総和 ★★☆ 8
08 スパイダー人 ★★★ 18
09 お城の堀 ★★★ 18
10 マトリョーシカ ★★★ 18


パソコン甲子園2007の予選が開催されました。問題は計10問。問題の質は良くなってきたと思います。問題01,02,06以外は、ACM/ICPCの国内予選に出てもおかしくない内容だと思います。ということで、簡単な問題も含めて解説したいと思います(※紹介するサンプルプログラムは審判データに対して正しい答えを出力することを保障するものではありません)。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(2) | トラックバック(1) | ↑ページトップ |




パソコン甲子園2007予選 3点問題(基礎)

2007.09.28 01:07  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題01 キャンディーとクラス旗

概要

n個のキャンディがあり、これらを39人の生徒が順番に1個ずつ取っていく。生徒は3C01から3C39までの生徒番号をそれぞれもち、最後のキャンディを取った生徒番号を出力せよ。

解法

キャンディの数を生徒の数で割った余りを計算し対応する生徒番号を出力します。
ただし、キャンディの数が生徒数で割り切れる場合は、最後の生徒番号を出力することに注意が必要です。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 main(){
005     static const int nstudent = 39;
006     int ncandy, target;
007     cin >> ncandy;
008     target = ncandy % nstudent;
009     if ( target == 0 ) target = nstudent;
010     cout << "3C";
011     if ( target < 10 ) cout << "0";
012     cout << target << endl;
013 }



問題02 視力検査

概要

複数の人の視力検査の結果を入力として、視力判定表に基づいて各判定にあてはまる人数を左右の視力別に出力せよ。

解法

各判定A, B, C, Dにおける左右の該当人数を保持する4×2の整数型配列を用意し、
分岐処理によって人数をカウントしていきます。

サンプルプルグラム

001 #include<iostream>
002 using namespace std;
003 #define A 0
004 #define B 1
005 #define C 2
006 #define D 3
007 #define LEFT 0
008 #define RIGHT 1
009 
010 main(){
011     int T[4][2];
012     for ( int i = 0; i < 4; i++ ) T[i][0] = T[i][1] = 0;
013     double left, right;
014     while( cin >> left >> right ){
015         if ( 1.1 <= left) T[A][LEFT]++;
016         if ( 1.1 <= right) T[A][RIGHT]++;
017         if ( 0.6 <= left && left < 1.1 ) T[B][LEFT]++;
018         if ( 0.6 <= right && right < 1.1 ) T[B][RIGHT]++;
019         if ( 0.2 <= left && left < 0.6 ) T[C][LEFT]++;
020         if ( 0.2 <= right && right < 0.6 ) T[C][RIGHT]++;
021         if ( left < 0.2 ) T[D][LEFT]++;
022         if ( right < 0.2 ) T[D][RIGHT]++;
023     }
024     
025     for ( int i = 0; i < 4; i++ ) {
026         cout << T[i][0] << " " << T[i][1] << endl;
027     }
028 }



問題03 双子素数

概要

n以下の双子素数(差が2となる素数の組)で最大のものを出力せよ。

解法

エラトステネスの篩などで素数表Tをつくり、入力nから5に向かってT[i] と T[i-2] が共に素数かどうかを調べます。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 #define LIMIT 10000
005 
006 void eratos ( int n, bool prime[]){
007     for ( int i = 0; i <= n; i++ ) prime[i] = false;
008     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
009     prime[2] = true;
010     int limit = (int)sqrt((double)n) + 1;
011     for ( int i = 3; i <= limit; i += 2 ){
012         if ( !prime[i] ) continue;
013         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
014     }
015 }
016 
017 bool prime[LIMIT+1];
018 
019 void compute( int n ){
020     int i;
021     for ( i = n; i >= 5; i-- ){
022         if ( prime[i] && prime[i-2] ) break;
023     }
024     cout << i - 2 << " " << i << endl;
025 }
026 
027 main(){
028     eratos(LIMIT, prime);
029     int n;
030     while ( cin >> n, n) compute(n);
031 }


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Dice Puzzle

2007.09.24 00:08  ACM/ICPC 2004

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem F

概要

側面に数字(1から6)が書かれたサイコロ27個を使い、
3×3×3×のキューブを完成させる。
入力としてキューブの上面と前面の状態が与えられるので、これを満たさなければならない。
また、隣り合うサイコロにおいて、接している側面に書かれている数字の和が7でなければならない。
求めるものは、キューブ右面に見える数字の合計。

解説

バックトラックで総当り探索。

サンプルプログラム

001 #include<iostream>
002 #include<set>
003 #include<algorithm>
004 using namespace std;
005 
006 int RT[24][6] = {
007     {1,2,3,4,5,6}, {1,3,5,2,4,6}, {1,5,4,3,2,6}, {1,4,2,5,3,6},
008     {4,2,1,6,5,3}, {4,1,5,2,6,3}, {4,5,6,1,2,3}, {4,6,2,5,1,3},
009     {6,2,4,3,5,1}, {6,4,5,2,3,1}, {6,5,3,4,2,1}, {6,3,2,5,4,1},
010     {3,2,6,1,5,4}, {3,6,5,2,1,4}, {3,5,1,6,2,4}, {3,1,2,5,6,4},
011     {5,1,3,4,6,2}, {5,3,6,1,4,2}, {5,6,4,3,1,2}, {5,4,1,6,3,2},
012     {2,1,4,3,6,5}, {2,4,6,1,3,5}, {2,6,3,4,1,5}, {2,3,1,6,4,5}
013 };
014 
015 int T[3][3], F[3][3], puzzle[27];
016 set<int> solved;
017 
018 int getRight(){
019     int sum = 0;
020     for ( int i = 2; i < 27; i += 3 ) sum += RT[puzzle[i]][2];
021     return sum;
022 }
023 
024 void recursive( int pos ){
025     if ( pos == 27 ){ solved.insert(getRight()); return; }
026     int i = (pos%9)/3;
027     int j = (pos%9)%3;
028     int k = pos/9;
029     
030     for ( int r = 0; r < 24; r++ ){
031         if ( i == 0 && T[3-k-1][j] && T[3-k-1][j] != RT[r][0] ) continue;
032         if ( k == 0 && F[i][j] && F[i][j] != RT[r][1] ) continue;
033         if ( i && RT[r][0] + RT[puzzle[k*9+(i-1)*3+j]][5] != 7 ) continue;
034         if ( k && RT[r][1] + RT[puzzle[(k-1)*9+i*3+j]][4] != 7 ) continue;
035         if ( j && RT[r][3] + RT[puzzle[k*9+i*3+(j-1)]][2] != 7 ) continue;
036         puzzle[pos] = r;
037         recursive( pos+1 );
038     }
039 }
040 
041 void compute(){
042     solved.clear();
043     recursive(0);
044     if ( solved.size() == 0 ) {	cout << 0 << endl; return; }
045     set<int>::iterator p = solved.begin();
046     cout << *p;
047     for ( p++; p != solved.end(); p++ ) cout << " " << *p;
048     cout << endl;
049 }
050 
051 main(){
052     int tcase; cin >> tcase;
053     for ( int t = 0; t < tcase; t++ ){
054         for ( int i = 0; i < 3; i++ ) {
055             for ( int j = 0; j < 3; j++ ) cin >> T[i][j];
056         }
057         for ( int i = 0; i < 3; i++ ) {
058             for ( int j = 0; j < 3; j++ ) cin >> F[i][j];
059         }
060         compute();
061     }
062 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Make a Sequence

2007.09.24 00:00  ACM/ICPC 2004

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem B

概要

3次元の○×ゲーム(n目並べ)をシミュレーションし、
勝者と勝負がつくまでの手数を求めよ。

解説

原点から13方向分の単位ベクトルを表す配列を用意すると実装が楽になります。

サンプルプログラム

001 #include<iostream>
002 #include<cassert>
003 using namespace std;
004 #define BLACK 0
005 #define WHITE 1
006 #define SPACE 2
007 int n, m, p;
008 int board[7][7][7], zsize[7][7];
009 static const int dx[13] = {0, -1, -1, -1, -1, 0, 1, 0, 0, -1, -1, 1, 1};
010 static const int dy[13] = {1, 1, 0, -1, 0, 0, 0, 1, -1, 1, -1, -1, 1};
011 static const int dz[13] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
012 
013 bool in( int a ){ return (0 <= a && a < n); }
014 
015 int parse( int x, int y, int z, int d ){
016     int nx, ny, nz;
017     int sum = 0;
018     nx = x; ny = y; nz = z;
019     while( in(nx) && in(ny) && in(nz) && board[nx][ny][nz] == board[x][y][z]){
020         sum++;
021         nx += dx[d]; ny += dy[d]; nz += dz[d];
022     }
023     nx = x; ny = y; nz = z;
024     while( in(nx) && in(ny) && in(nz) && board[nx][ny][nz] == board[x][y][z]){
025         sum++;
026         nx -= dx[d]; ny -= dy[d]; nz -= dz[d];
027     }
028     return sum - 1;
029 }
030 
031 void simulate(){
032     for ( int x = 0; x < n; x++ ){
033         for ( int y = 0; y < n; y++ ){
034             zsize[x][y] = 0;
035             for ( int z = 0; z < n; z++ ) board[x][y][z] = SPACE;
036         }
037     }
038     int move = 0;
039     bool isDraw = true;
040     int x, y;
041     for ( int i = 0; i < p; i++ ){
042         cin >> x >> y; x--; y--;
043         if ( !isDraw ) continue;
044         board[x][y][zsize[x][y]++] = ((++move)%2);
045         for ( int d = 0; d < 13; d++ ){
046             if ( parse( x, y, zsize[x][y]-1, d ) >= m )	isDraw = false;
047         }
048     }
049     
050     if ( isDraw ) cout << "Draw" << endl;
051     else {
052         cout << ((move%2 == 1) ? "Black" : "White") << " " << move << endl;
053     }
054 }
055 
056 main(){
057     while ( cin >> n >> m >> p, (n || m || p) ) simulate();
058 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




The Balance

2007.09.23 23:26  ACM/ICPC 2004

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem A

概要
a グラムと b グラムの2種類の重りと天秤を使い、d グラムを計るとき、以下の条件を満たすように
x (a グラムの重りの数)と y (b グラムの重りの数)を求めよ。

1. a グラムの重りを x 個、b グラムの重りを y 個使って、d グラムを計ることができる
2. 1 の条件を満たす (x, y) が複数ある場合は、(x + y) が最小のものとする
3. 1, 2 の条件を満たす (x, y) が複数ある場合は、(a*x + b*y) が最小のものとする

解法

天秤の状態を式で表すと、(a グラムの重りを a と表現します)

a*x = b*y + d (左に x 個の a、右に y 個の b と d)
a*x + d = b*y (左の x 個の a と d、右に y 個の b)
a*x + b*y = d (左り x 個の a と y 個の b、右に d)

の3つの状態が考えられます。これらを変形すると

y = (a*x - d)/b, ((a*x - d) が b で割りきれるとき)
y = (a*x + d)/b, ((a*x + d) が b で割りきれるとき)
y = (d - a*x)/b, ((d - a*x) が b で割りきれるとき)

x を 0 から b+d までについて、y を求め
(x + y) または (a*x + b*y) の最小値を更新していきます。

もちろん効率化の余地はありますし、整数論的に解けるのかもしれません。
ICPCで Accept されるには十分だと思います。

サンプルプログラム

001 #include<iostream>
002 #include<cmath>
003 #define LIMIT 50000
004 using namespace std;
005 int a, b , d, mx, my;
006 
007 void update( int x, int y, int &mx, int &my ){
008     if ( y < 0 ) return;
009     if ( x + y == mx + my && a*x + b*y < a*mx + b*my ){
010         mx = x; my = y;
011     } else if ( x + y < mx + my ){
012         mx = x; my = y;
013     }
014 }
015 
016 main(){
017     while( cin >> a >> b >> d, (a || b || d) ){
018         mx = my = LIMIT;
019         for ( int y, x = 0; x <= b + d; x++ ){
020             if ( (a*x - d)%b == 0 ){
021                 y = (a*x - d)/b; update( x, y, mx, my );
022             }
023             if ( (a*x + d)%b == 0 ){
024                 y = (a*x + d)/b; update( x, y, mx, my );
025             }
026             if ( (d - a*x)%b == 0 ){
027                 y = (d - a*x)/b; update( x, y, mx, my );
028             }
029         }
030         cout << mx << " " << my << endl;
031     }
032 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM/ICPC 2004 Ehime

2007.09.23 23:17  ACM/ICPC 2004

ID 問題 難易度 考察
A The Balance ★☆ -
B Make a Sequence ★★ -
C Leaky Cryptography ★★☆ -
D Pathological Paths ★★★☆ -
E Confusing Login Names ★★★? -
F Dice Puzzle ★★★☆ -
G Color the Map ★★★ -
H Inherit the Sphere ★★★★ -
I Crossing Prisms ★★★★★ grave

| コメント(0) | トラックバック(0) | ↑ページトップ |




Sum of Different Primes

2007.09.21 16:18  ACM/ICPC 2006

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem D

[難易度] ★★☆

[解説]

動的計画法(DP)で解けます。
ナップザック問題をDPで解く仕組みを応用します。

T[i][j][k] を

1 ~ i 番目の素数のうち k 個を用いて j を表す組み合わせの数

とすると、

T[i][j][k] = T[i-1][j][k] + T[i-1][j-primes[i]][k-1]

となります(primes[i]は i 番目の素数を示す)。

サンプルプログラム

001 #include<iostream>
002 #include<vector>
003 using namespace std;
004 #define PMAX 187
005 #define NMAX 1120
006 #define KMAX 14
007 
008 int T[PMAX+1][NMAX+1][KMAX+1];
009 
010 void eratos ( int n, vector<int> &p){
011     bool prime[NMAX+1];
012     for ( int i = 0; i <= n; i++ ) prime[i] = false;
013     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
014     prime[2] = true;
015     for ( int i = 3; i*i <= n; i += 2 ){
016         if ( !prime[i] ) continue;
017         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
018     }
019     for ( int i = 0; i <= n; i++ ) if ( prime[i] ) p.push_back(i);
020 }
021 
022 void initialize(){
023     vector<int> primes;
024     eratos( NMAX, primes );
025     
026     for ( int i = 0; i < PMAX; i++ ){
027         for ( int j = 0; j <= NMAX; j++ ){
028             for ( int k = 0; k <= KMAX; k++ ) T[i][j][k] = 0;
029             if ( j == primes[i] ) T[i][j][1] = 1;
030         }
031     }
032     
033     for ( int i = 1; i < PMAX; i++ ){
034         for ( int j = 0; j <= NMAX; j++ ){
035             for ( int k = 1; k <= KMAX; k++ ){
036                 T[i][j][k] += T[i-1][j][k];
037                 if ( j - primes[i] >= 0 ) {
038                     T[i][j][k] += T[i-1][j-primes[i]][k-1];
039                 }
040             }
041         }
042     }
043 }
044 
045 main(){
046     initialize();
047     int n, k;
048     while( cin >> n >> k, (n || k) ) cout << T[PMAX-1][n][k] << endl;
049 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Cubic Eight-Puzzle

2007.09.04 16:46  ACM/ICPC 2006

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem C

[難易度] ★★★☆

[解説]

この問題の難易度は、本番のタイムリミットによって大きく左右します(★★☆くらいかも)。
(実際のタイムリミットはどのくらいだったのでしょうか?orz)

まず、考えられるのが単純な幅優先探索(横型探索)ですが、
審判データで試すと、手元のマシンで3分ほどかかってしまいます。(実装力の問題ですかね)
この問題では、ゴールの状態数が大きいので、両側探索にする
メリットもあまりなさそうですし、実装も面倒臭そうだったのですが、
試してみると、案の定劇的な変化はなく30秒程度かかります。(これも実装力かなorz)

結局、問題の性質からして、反復深化(Iterative Deepening)(縦型探索)
がベストという結論に至りました。審判データを5秒弱で解けますし、
実装も簡単です。
選手の皆さんはどうやって解いたのでしょうか。。
何かポイントがありそうです(探索空間を縮小できるとか)。
この問題を縦型探索で解くには多少勇気がいる気がします。

マンハッタン距離を、現在の状態とゴールの状態における各セル上面の色が違うものの個数としました。
その他、マンハッタン距離を大きくするポイントがあれば高速化できるでしょう。
また、反復進化のLIMITの増加値を3とすることで、多少高速化できました。
[サンプルプログラム]

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 
005 struct Point{int x, y;};
006 
007 class Cube{
008     public:
009     char C[3];
010     Cube(){ C[0] = 'W'; C[1] = 'R'; C[2] = 'B';}
011     void setEmpty(){ C[0] = 'E';}
012     void rotate(int d){
013         if ( d % 2 == 0 ) swap(C[0], C[2]);
014         else swap(C[0], C[1]);
015     }
016 };
017 
018 char target[3][3];
019 
020 class Puzzle{
021     public:
022     Cube cubes[3][3];
023     Point empty;
024     int manhattanDist;
025     
026     Puzzle(){
027         for ( int y = 0; y < 3; y++ ){
028             for ( int x = 0; x < 3; x++ ) cubes[y][x] = Cube();
029         }
030     }
031     
032     void setEmpty( int y, int x ){
033         empty.x = x; empty.y = y;
034         cubes[y][x].setEmpty();
035     }
036     
037     void setmanhattanDist(){
038         manhattanDist = 0;
039         for ( int y = 0; y < 3; y++ ){
040             for ( int x = 0; x < 3; x++ ){
041                 if ( cubes[y][x].C[0] != target[y][x] ) manhattanDist++;
042             }
043         }
044     }
045     
046     void upDate( int y, int x, int d ){
047         if ( target[y][x] != cubes[y][x].C[0] ) manhattanDist += d;
048     }
049 };
050 
051 int ix, iy, tx, ty, limit;
052 Puzzle u;
053 static const int dy[4] = {0, -1, 0, 1};
054 static const int dx[4] = {1, 0, -1, 0};
055 
056 
057 bool dfs( int depth, int pre, int seq ){
058     if ( depth + u.manhattanDist-1 > limit ) return false;
059     if ( u.manhattanDist == 0 ) return true;
060     
061     int x, y, nx, ny;
062     
063     y = u.empty.y;
064     x = u.empty.x;
065     
066     Puzzle tmp = u;
067     
068     for ( int d = 0; d < 4; d++ ){
069         if ( pre != -1 && d == (pre+2)%4 ) continue;
070         ny = y + dy[d];
071         nx = x + dx[d];
072         if ( ny < 0 || nx < 0 || 3 <= nx || 3 <= ny ) continue;
073         
074         u = tmp;
075         
076         u.upDate(ny, nx, -1);
077         u.upDate(y, x, -1);
078         
079         u.cubes[ny][nx].rotate(d);
080         u.cubes[y][x] = u.cubes[ny][nx];
081         u.setEmpty(ny, nx);
082         
083         u.upDate(ny, nx, 1);
084         u.upDate(y, x, 1);
085         
086         if ( dfs( depth+1, d, seq) ) return true;
087     }
088     
089     return false;
090 }
091 
092 void compute(){
093     Puzzle initial = Puzzle();
094     initial.setEmpty(iy, ix);
095     initial.setmanhattanDist();
096     int start = initial.manhattanDist -1;
097     while( start % 3 != 0 ) start--;
098     for ( limit = start; limit <= 30; limit+=3 ){
099         u = initial;
100         if ( dfs(  0, -1, 0 ) ) {
101             if ( limit == 0 ) {cout << 0 << endl; return;}
102             limit -= 2;
103             u = initial;
104             if ( dfs(0, -1, 0 ) ) {
105                 cout << limit << endl;
106             } else {
107                 limit++;
108                 u = initial;
109                 if ( dfs(0, -1, 0) ) cout << limit << endl;
110                 else cout << limit + 1 << endl;
111             }
112             return;
113         }
114     }
115     cout << -1 << endl;
116 }
117 
118 bool input(){
119     cin >> ix >> iy;
120     if ( ix == 0 && iy == 0 ) return false;
121     ix--; iy--;
122     for ( int y = 0; y < 3; y++ ){
123         for ( int x = 0; x < 3; x++ ){
124             cin >> target[y][x];
125             if ( target[y][x] == 'E' ){ tx = x; ty = y; }
126         }
127     }
128     return true;
129 }
130 
131 main(){
132     while(input()) compute();
133 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(3) | トラックバック(0) | ↑ページトップ |




Manhattan Wiring

2007.09.02 00:45  ACM/ICPC 2006

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem E

[難易度] ★★★★

[解説]

深さ優先探索 + 枝狩り + 幅優先探索

まず、深さ優先探索(バックトラック)で、2と2を繋ぐパスを探します(総当り)。
パスを探す過程で、例えば以下のような「無駄な」あるいは「ありえない」部分パスを発見したら枝を刈ります。

22
22
ワイヤーが接してしまう場合

202
222
これらの回転

2002
2222
これらの回転

*000..00*
2000..002
2222..222
これらの回転

などなど、、.(ここまで刈ればPOJでも受理されます)

2と2を繋ぐパスを発見したときに、3と3を繋ぐ最短パスを幅優先探索で求め、最小値を更新していきます。

[サンプルプログラム]

001 #include<iostream>
002 #include<queue>
003 #include<algorithm>
004 using namespace std;
005 #define INFTY (1<<15)
006 #define MAX 9
007 #define EMPTY '0'
008 #define OBSTACLE '1'
009 #define TWO '2'
010 #define THREE '3'
011 
012 class Point{
013     public:
014     int i, j;
015     Point(){}
016     Point( int i , int j ): i(i), j(j){}
017     bool operator == ( const Point &p ) const{
018         return i == p.i && j == p.j;
019     }
020 };
021 
022 int N, M;
023 char G[MAX+2][MAX+2];
024 Point two[2], three[2];
025 int mincost;
026 static const int di[4] = {0, -1, 0, 1};
027 static const int dj[4] = {1, 0, -1, 0};
028 
029 int bfs(){
030     int D[MAX+2][MAX+2];
031     queue<Point> Q;
032     
033     for ( int i = 1; i <= N; i++ ){
034         for ( int j = 1; j <= M; j++ ) D[i][j] = INFTY;
035     }
036     
037     Q.push(Point(three[0].i, three[0].j));
038     D[three[0].i][three[0].j] = 0;
039     
040     Point u, v;
041     int ni, nj;
042     while(!Q.empty()){
043         u = Q.front(); Q.pop();
044         if ( u== three[1] ) return D[u.i][u.j];
045         for ( int d = 0; d < 4; d++ ){
046             ni = u.i + di[d];
047             nj = u.j + dj[d];
048             if ( D[ni][nj] == INFTY &&
049             (G[ni][nj] == EMPTY || G[ni][nj] == THREE)){
050                 D[ni][nj] = D[u.i][u.j] + 1;
051                 Q.push(Point(ni, nj));
052             }
053         }
054     }
055     
056     return INFTY;
057 }
058 
059 int manhattanDist( int i , int j ){
060     return max(i, two[1].i)-min(i, two[1].i) +
061     max(j, two[1].j)-min(j, two[1].j);
062 }
063 
064 int getWidth( int i, int j, int d){
065     int w = 0;
066     while(1){
067         if ( G[i][j] == TWO ) return w;
068         if ( G[i][j] != EMPTY ) return -1;
069         i += di[d]; j += dj[d];	w++;
070     }
071 }
072 
073 bool isSeq( int i, int j, int d, int w, char ch ){
074     for ( int s = 0; s < w; s++, i += di[d], j += dj[d] ){
075         if ( G[i][j] != ch ) return false;
076     }
077     return true;
078 }
079 
080 bool cut(int i, int j){
081     for ( int d = 0; d < 4; d++ ){
082         int w = getWidth(i+di[d], j+dj[d], d);
083         if ( w <= 0 ) continue;
084         if ( w == 1 || w == 2 ){
085             if ( isSeq( i+di[(d+1)%4], j+dj[(d+1)%4], d, w+2, TWO ) ||
086             isSeq( i+di[(d+3)%4], j+dj[(d+3)%4], d, w+2, TWO ) ) return true;
087         } else {
088             if ( isSeq( i+di[(d+1)%4], j+dj[(d+1)%4], d, w+2, TWO ) &&
089             isSeq( i+di[(d+3)%4]*2, j+dj[(d+3)%4]*2, d, w, EMPTY ) ||
090             isSeq( i+di[(d+3)%4], j+dj[(d+3)%4], d, w+2, TWO ) &&
091             isSeq( i+di[(d+1)%4]*2, j+dj[(d+1)%4]*2, d, w, EMPTY ) ) {
092                 return true;
093             }
094         }
095     }
096     
097     return false;
098 }
099 
100 
101 void dfs( int i, int j, int dist, int pre ){
102     if ( i == two[1].i && j == two[1].j ){
103         mincost = min( mincost, dist + bfs() );
104         return;
105     }
106     
107     if ( dist + manhattanDist(i, j) > mincost ) return;
108     
109     if ( pre != -1 ){
110         for ( int r = 0; r < 4; r++ ){
111             if ( r == pre ) continue;
112             if ( i+di[r] == two[1].i && j+dj[r] == two[1].j ) continue;
113             if ( G[i+di[r]][j+dj[r]] == TWO ) return;
114         }
115     }
116     
117     G[i][j] = TWO;
118     
119     if ( cut(i, j) ) return;
120     
121     int ni, nj;
122     for ( int d = 0; d < 4; d++ ){
123         ni = i + di[d];
124         nj = j + dj[d];
125         char target = G[ni][nj];
126         if ( target == EMPTY || (ni == two[1].i && nj == two[1].j ) ){
127             dfs( ni, nj, dist + 1, (d+2)%4 );
128             G[ni][nj] = target;
129         }
130     }
131 }
132 
133 void compute(){
134     mincost = INFTY;
135     dfs( two[0].i, two[0].j, 0, -1 );
136     if ( mincost >= INFTY ) cout << 0 << endl;
137     else cout << mincost << endl;
138 }
139 
140 bool input(){
141     cin >> N >> M;
142     if ( N == 0 && M == 0 ) return false;
143     for ( int i = 0; i < N+2; i++ ) G[i][0] = G[i][M+1] = OBSTACLE;
144     for ( int j = 0; j < M+2; j++ ) G[0][j] = G[N+1][j] = OBSTACLE;
145     
146     int s2c, s3c;
147     s2c = s3c = 0;
148     for ( int i = 1; i <= N; i++ ){
149         for ( int j = 1; j <= M; j++ ){
150             cin >> G[i][j];
151             if ( G[i][j] == TWO ) two[s2c++] = Point(i, j);
152             if ( G[i][j] == THREE ) three[s3c++] = Point(i, j);
153         }
154     }
155     return true;
156 }
157 
158 main(){
159     while( input() ) compute();
160 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |