Sum of Different Primes

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

[難易度]　★★☆

[解説]

動的計画法（ＤＰ）で解けます。
ナップザック問題をＤＰで解く仕組みを応用します。

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 }

Cubic Eight-Puzzle

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

[難易度]　★★★☆

[解説]

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

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

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

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

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 }

Manhattan Wiring

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

[難易度]　★★★★

[解説]

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

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

22
22

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

202
222

これらの回転

2002
2222

これらの回転

*000..00*
2000..002
2222..222

これらの回転

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

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

[サンプルプログラム]

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 }