Dice Puzzle

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

概要

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

解説

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

サンプルプログラム

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 }

Make a Sequence

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

概要

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

解説

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

サンプルプログラム

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 }

The Balance

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

概要
a グラムと b グラムの２種類の重りと天秤を使い、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）

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

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 }

ACM/ICPC 2004 Ehime

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