ACM/ICPC 国内予選 2007

ID	問題	難易度	考察
A	ICPC Score Totalizer Software	☆	-
B	Analyzing Login/Logout Records	★☆	-
C	Cut the Cakes	★★☆	-
D	Cliff Climbing	★★★	-
E	Twirl Around	★★★★★	grave
F	Dr. Podboq or: How We Became Asymmetric	★★★★☆	-

データがまだ公開されてませんが、解いてみました。解く順番はＡ→Ｂ→Ｃ→Ｄ→Ｆ→Ｅが妥当でしょう。しかし、３問目をトップで通過したチームはＡ→Ｂ→Ｄの順で解いています。なぜなら、Ｄは知識問題だからです。

最初の４問を解けないチームは、このままではアジア地区予選で撃沈してしまうでしょう。選手の皆さん練習頑張って下さい。

今年は、最初の４問をいかに速く解くかがポイントになりましたね。５問解いたチームはさすがです。

Karakuri Doll からくり人形

今年もACM/ICPCの模擬国内予選が開催されました。さすがOB/OG会の皆さん、すばらしい問題セットでした。取り急ぎ、自分ができそうな問題でかつ一番難しそうなFを解いてみました。このような、発想と実装力が必要でかつストリーが面白い問題を作成された方に感謝です。こういう問題をどんどん学生に挑戦させたいですね。

[問題]ACM/ICPC 模擬国内予選 2007: Problem F

OB/OG 会の解説を参考にして実装してみました（お粗末なコードです）

001 #include<iostream>
002 #define WMAX 64
003 #define HMAX 16
004 
005 using namespace std;
006 
007 class State{
008     public:
009     int toX, toY, toD; // to
010     int frX, frY, frD; // from
011     State(){}
012 };
013 
014 static const int dx[4] = {0, -1, 0, 1};
015 static const int dy[4] = {1, 0, -1, 0};
016 
017 int W, H;
018 char G[HMAX][WMAX];
019 bool visited[HMAX][WMAX][4][HMAX][WMAX][4];
020 State start, goal;
021 
022 int getSpaceDirection( int x, int y ){
023     for ( int r = 0; r < 4; r++ )
024         if ( G[x+dx[r]][y+dy[r]] != '#' ) return r;
025 }
026 
027 int getOposite( int r ){
028     return (r+2)%4;
029 }
030 
031 void turnRight( int &r ){
032     r--;
033     if ( r < 0 ) r = 3;
034 }
035 
036 void turnLeft( int &r ){
037     r = (r+1)%4;
038 }
039 
040 void move( int &x, int &y, int r ){
041     while ( G[x+dx[r]][y+dy[r]] != '#' ) { x += dx[r]; y += dy[r]; }
042 }
043 
044 bool findSource( int &x, int &y, int r, int p){
045     while (1){
046         if ( G[x][y] == '#' ) return false;
047         if ( G[x+dx[p]][y+dy[p]] == '#' ) return true;
048         x += dx[r]; y += dy[r];
049     }
050 }
051 
052 bool check( State s, State g ){
053     if ( s.toX == g.toX && s.toY == g.toY &&
054         s.frX == g.frX && s.frY == g.frY && s.frD == g.frD )
055         return true;
056     return false;
057 }
058 
059 bool recursive2( State u ){
060     if ( check( u, goal)  ) return true;
061     visited[u.toX][u.toY][u.toD][u.frX][u.frY][u.frD] = true;
062     
063     State v;
064     int r;
065     // next: right
066     v = u;
067     turnRight( v.toD );
068     move( v.toX, v.toY, v.toD );
069     r = getOposite(v.frD);
070     turnRight( v.frD );
071     while ( findSource( v.frX, v.frY, r, v.frD ) ){
072         if ( !visited[v.toX][v.toY][v.toD][v.frX][v.frY][v.frD] &&
073             recursive2( v ) ) return true;
074         v.frX += dx[r];	v.frY += dy[r];
075     }
076     
077     // next: left
078     v = u;
079     turnLeft( v.toD );
080     move( v.toX, v.toY, v.toD );
081     r = getOposite(v.frD);
082     turnLeft( v.frD );
083     while ( findSource( v.frX, v.frY, r, v.frD ) ){
084         if ( !visited[v.toX][v.toY][v.toD][v.frX][v.frY][v.frD] &&
085             recursive2( v ) ) return true;
086         v.frX += dx[r];	v.frY += dy[r];
087     }
088     
089     return false;
090 }
091 
092 void init(){
093     memset(visited, 0, sizeof(bool)*WMAX*WMAX*HMAX*HMAX*4*4);
094 }
095 
096 bool recursive1( State u ){
097     if ( u.toX == goal.toX && u.toY == goal.toY ) return true;
098     visited[u.toX][u.toY][u.toD][0][0][0] = true;
099     State v;
100     // to right
101     v = u;
102     turnRight(v.toD);
103     move(v.toX, v.toY, v.toD );
104     if ( !visited[v.toX][v.toY][v.toD][0][0][0] &&
105         recursive1(v) ) return true;
106     // to left
107     v = u;
108     turnLeft(v.toD);
109     move(v.toX, v.toY, v.toD );
110     if ( !visited[v.toX][v.toY][v.toD][0][0][0] &&
111         recursive1(v) ) return true;
112     
113     return false;
114 }
115 
116 int compute(){
117     start.toD = getSpaceDirection(start.toX, start.toY);
118     start.frD = getOposite(getSpaceDirection(start.toX, start.toY) );
119     move(start.toX, start.toY, start.toD);
120     
121     goal.toD = getOposite(getSpaceDirection(goal.toX, goal.toY) );
122     goal.frD = getSpaceDirection(goal.toX, goal.toY);
123     move(goal.frX, goal.frY, goal.frD);
124     
125     // to - from
126     init();
127     for ( int r = 0; r < 4; r++ ){
128         if ( recursive2( start ) ) return 0;
129         turnLeft(start.frD);
130     }
131     
132     // to
133     init();
134     if ( recursive1( start ) ) return 1;
135     
136     return 2;
137 }
138 
139 bool input(){
140     cin >> W >> H;
141     if ( W == 0 && H == 0 ) return false;
142     for ( int i = 0; i < H; i++ ){
143         for ( int j = 0; j < W; j++ ) {
144             cin >> G[i][j];
145             if ( G[i][j] == 'K' )
146                 { start.toX = start.frX = i; start.toY = start.frY = j;}
147             if ( G[i][j] == 'M' )
148                 { goal.toX = goal.frX = i; goal.toY = goal.frY = j;}
149         }
150     }
151     return true;
152 }
153 
154 main(){
155     while ( input() ) {
156         int judge = compute();
157         if ( judge == 0 )
158             cout << "He can accomplish his mission." << endl;
159         else if ( judge == 1 )
160             cout << "He cannot return to the kitchen." << endl;
161         else
162             cout << "He cannot bring tea to his master." << endl;
163     }
164 }

ACM/ICPC 模擬国内予選2007

ID	問題	難易度	考察
A	Space Coconut Grab	★	-
B	Osaki	★☆	-
C	Surrounding Area	★★	-
D	Square Route	★☆	-
E	Lifeguard in the Pool	★★★★☆	grave
F	Karakuri Doll	★★★☆	○

Cleaning Robot

[問題]ACM/ICPC Japan Domestic 2005: Problem F

[解説]
巡回セールスマン問題に帰着できます。タイルの数が最大 10 個までなので、動的計画法（とりあえずここを参考にして下さい）または力任せの総当りで解くことができます。

以下は力任せのアルゴリズム。
①幅優先探索BFSにより、「汚れたタイル」の全ての組み合わせ（All pairs）について、最短コストを求め、テーブルに保存する。
②「汚れたタイル」の全ての順列について、テーブルを用いてコストを計算し、最短のコストを求める。

[プログラム例]

#include<iostream>
#include<queue>
#include<algorithm>
#define MAX 20
#define DMAX 10
using namespace std;

class Point{
    public:
    int y, x;
    Point(){}
    Point( int y, int x ): y(y), x(x){}
    
    bool operator == ( const Point &p ) const{
        return ( x == p.x && y == p.y );
    }
};

int W, H;
char G[MAX][MAX];
Point start;
Point dirty[DMAX];
int dsize;
int T[DMAX]; // start to all dirty;
int M[DMAX][DMAX]; // all dirty to all dirty

int bfs( Point p1, Point p2 ){
    bool visited[MAX][MAX];
    int d[MAX][MAX];
    queue<Point> q;
    
    for ( int i = 0; i < H; i++ ){
        for ( int j = 0; j < W; j++ ){
            visited[i][j] = false;
            d[i][j] = INT_MAX;
        }
    }
    
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, -1, 0, 1};
    
    q.push( p1 );
    d[p1.y][p1.x] = 0;
    
    Point u;
    
    while ( !q.empty() ){
        u = q.front(); q.pop();
        
        if ( u == p2 ) return d[u.y][u.x];
        
        int nx, ny;
        for ( int r = 0; r < 4; r++ ){
            ny = u.y + dy[r];
            nx = u.x + dx[r];
            
            if ( !( 0 <= nx && 0 <= ny && ny < H && nx < W ) ) continue;
            
            if ( !visited[ny][nx] && G[ny][nx] != 'x' ){
                visited[ny][nx] = true;
                d[ny][nx] = d[u.y][u.x] + 1;
                q.push( Point( ny, nx ) );
            }
        }
    }
    
    return INT_MAX;
}

void computeDistanceTable(){
    for ( int i = 0; i < dsize; i++ ){
        T[i] = bfs( start, dirty[i]);
    }
    for ( int i = 0; i < dsize-1; i++ ){
        for ( int j = i; j < dsize; j++ ){
            if ( i == j ) M[i][j] = M[j][i] = 0;
            M[i][j] = M[j][i] = bfs( dirty[i], dirty[j] );
        }
    }
}

int getMinimumMove(){
    int order[DMAX];
    for ( int i = 0; i < dsize; i++ ){
        order[i] = i;
    }
    
    int minMove = INT_MAX;
    
    do{
        int move = T[ order[0] ];
        
        for ( int i = 1; i < dsize; i++ ){
            move += M[ order[i-1] ][ order[i] ];
        }
        
        if ( minMove > move ) minMove = move;
        
    } while( next_permutation(order, order + dsize )) ;
    
    return minMove;
}

bool notReachable(){
    for ( int i = 0; i < dsize; i++ ){
        if ( T[i] == INT_MAX ) return true;
    }
    return false;
}

void compute(){
    computeDistanceTable();
    if ( notReachable() ) cout << "-1" << endl;
    else {
        cout << getMinimumMove() << endl;
    }
}

bool read(){
    cin >> W >> H;
    if ( W == 0 && H == 0 ) return false;
    dsize = 0;
    char ch;
    for ( int i = 0; i < H; i++ ){
        for ( int j = 0; j < W; j++ ){
            cin >> ch;
            G[i][j] = ch;
            if ( ch == 'o' ){
                start = Point(i, j);
            } else if ( ch == '*' ){
                dirty[dsize++] = Point(i, j);
            }
        }
    }
    return true;
}

main(){
    while ( read() ) compute();
}

Hexerpents of Hexwamp

[問題]ACM/ICPC Japan Domestic 2006: Problem C

[解説]
本番では時間制限がないため、幅優先探索 BFS (ヘビの形の状態遷移)で解けたようです。僕はこれ↓が精一杯。キューに状態を突っ込むときに、ある程度見積もって、枝を刈っています。高速化の方法を考え中です。審判データを計算するのに数十秒くらいかかります。

[プログラム例]
なんか、すごいことになってしまいました

// @author yutaka C++
// BFS
#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<cassert>
#define MAX_SIZE 10
#define MAX_ROCK 105
#define LIMIT 20

using namespace std;

class Point{
    public:
    int x, y;
    Point(){}
    Point( int x, int y ): x(x), y(y){}
    
    int getDist( const Point &p ){
        return max(x, p.x)-min(x, p.x) + max(y, p.y)-min(y, p.y);
    }
    
    bool isAdj( const Point &p ){
        int dx = max( x, p.x ) - min( x, p.x );
        int dy = max( y, p.y ) - min( y, p.y );
        if ( dx == 1 && dy == 0 || dx == 0 && dy == 1 ) return true;
        if ( dx == 1 && dy == 1 && ( x - p.x ) != (y - p.y ) ) return true;
        return false;
    }
    
    bool operator == ( const Point &p ) const{
        return (x == p.x && y == p.y);
    }
    
    bool operator < ( const Point &p ) const {
        if ( x == p.x ) return y < p.y;
        else return x < p.x;
    }
};

class Snake{
    public:
    int size, cost;
    Point bodies[MAX_SIZE];
    
    Snake(){}
    Snake( int size ): size( size ){}
    
    bool operator < ( const Snake &s ) const{
        for ( int i = 0; i < size; i++ ){
            if ( bodies[i] == s.bodies[i] ) continue;
            return (bodies[i] < s.bodies[i]);
        }
        return false;
    }
};

int nBody, nRock;
Snake initial;
Point rocks[MAX_ROCK], goal;

bool onRock( Point target ){
    for ( int i = 0; i < nRock; i++ ) if ( rocks[i] == target ) return true;
    return false;
}

void tryMove( int pos, Snake current, set<Snake> &nexts, bool moved, int order ){
    nexts.insert( current );
    if ( order == 1 && pos == nBody || order == -1 && pos == -1 ) return;
    
    Snake next;
    
    // do not move
    tryMove ( pos + order, current, nexts, false, order );
    
    // move
    if ( moved ) return;
    
    static const int dx[6] = {1, 0, -1, -1, 0, 1};
    static const int dy[6] = {-1, -1, 0, 1, 1, 0};
    for ( int r = 0; r < 6; r++ ){
        Point target = current.bodies[pos];
        target.x += dx[r];
        target.y += dy[r];
        
        if ( onRock( target ) ) continue;
        
        int adjList[3], lsize = 0;
        for ( int j = 0; j < current.size; j++ ){
            if ( j != pos && target.isAdj( current.bodies[j] )) adjList[lsize++] = j;
        }
        
        int valid = false;
        if ( pos == 0 ){
            if ( lsize == 1 && adjList[0] == 1 ) valid = true;
        } else if ( pos == nBody - 1 ){
            if ( lsize == 1 && adjList[0] == nBody-2 ) valid = true;
        } else {
            if ( lsize ==2 &&
            ( adjList[0] == pos - 1 && adjList[1] == pos + 1 ||
            adjList[0] == pos + 1 && adjList[1] == pos - 1 ) ) valid = true;
        }
        
        if ( valid ){
            next = current;
            next.bodies[pos] = target;
            tryMove( pos + order, next, nexts, true, order );
        }
    }
}

int bfs(){
    queue<Snake> Q;
    map<Snake, int> D;
    
    Q.push( initial );
    D[initial] = 0;
    
    while ( !Q.empty() ){
        Snake current = Q.front(); Q.pop();
        int cost = D[current];
        
        if ( current.bodies[0] == goal ) return cost;
        
        set<Snake> nexts;
        tryMove( 0, current, nexts, false, 1 );
        tryMove( current.size - 1, current, nexts, false, -1 );
        
        for ( set<Snake>::iterator it = nexts.begin(); it != nexts.end(); it++ ){
            if ( D.count(*it) == 0 &&
                current.bodies[0].getDist(goal) + cost <= LIMIT + 1 ){
                D[*it] = cost + 1;
                Q.push(*it);
            }
        }
    }
    assert( false );
}

void compute(){
    cout << bfs() << endl;
}

bool input(){
    cin >> nBody;
    if ( nBody == 0 ) return false;
    
    initial = Snake( nBody );
    
    for ( int i = 0; i < nBody; i++ ){
        cin >> initial.bodies[i].x >> initial.bodies[i].y;
    }
    
    cin >> nRock;
    for ( int i = 0; i < nRock; i++ ){
        cin >> rocks[i].x >> rocks[i].y;
    }
    
    cin >> goal.x >> goal.y;
    
    return true;
}

main(){
    while ( input() ) compute();
}

Curling 2.0

[問題]ACM/ICPC Japan Domestic 2006: Problem D

[解説]
BFS または DFS で解きます。盤面の状態を保持できれば BFS でも解けますが、問題の定義より、DFS で全探索、つまりバックトラッキングしてもよいと思います。実装が簡単なので、DFS で解いてみました。

[プログラム例]

// DFS (exhaustive search)
#include<iostream>
#include<algorithm>

using namespace std;

#define MAX 20
#define LIMIT 10
#define SPACE '0'
#define OBSTACLE '1'
#define START '2'
#define GOAL '3'
#define OUTSIDE '*'

struct Point{int i, j;};

int W, H, mincost;
Point start, goal;
char G[MAX+2][MAX+2];

void shot( Point pos, Point &next, char &target, int di, int dj ){
    int i = pos.i;
    int j = pos.j;
    while(1){
        i += di; j += dj;
        if ( G[i][j] != SPACE ){
            next.i = i; next.j = j; target = G[i][j];
            break;
        }
    }
}

void recursive( Point pos, int cost ){
    cost++;
    if ( cost > LIMIT ) return;
    
    static const int di[4] = {0, -1, 0, 1};
    static const int dj[4] = {1, 0, -1, 0};
    
    Point next;
    char target;
    
    for ( int r = 0; r < 4; r++ ){
        if ( G[pos.i + di[r]][pos.j + dj[r]] == OBSTACLE ) continue;
        
        shot( pos, next, target, di[r], dj[r] );
        
        if ( target == OUTSIDE ) continue;
        
        if ( target == GOAL ){
            mincost = min( mincost, cost );
            return;
        }
        
        G[next.i][next.j] = SPACE;
        next.i -= di[r];
        next.j -= dj[r];
        
        recursive( next, cost );
        
        next.i += di[r];
        next.j += dj[r];
        G[next.i][next.j] = OBSTACLE;
    }
}

void compute(){
    mincost = INT_MAX;
    recursive( start, 0 );
    cout << (( mincost > LIMIT ) ? -1 : mincost) << endl;
}

bool input(){
    cin >> W >> H;
    if ( W == 0 && H == 0 ) return false;
    for ( int i = 1; i <= H; i++ ){
        for ( int j = 1; j <= W; j++ ){
            cin >> G[i][j];
            if ( G[i][j] == '2' ) { start.i = i; start.j = j; G[i][j] = SPACE;}
            if ( G[i][j] == '3' ) { goal.i = i; goal.j = j; }
        }
    }
    for ( int i = 0; i < H+2; i++ ) G[i][0] = G[i][W+1] = OUTSIDE;
    for ( int j = 0; j < W+2; j++ ) G[0][j] = G[H+1][j] = OUTSIDE;
    return true;
}

main(){
    while ( input() ) compute();
}

Organize Your Train part II

[問題]ACM/ICPC Japan Domestic 2006: Problem B

[解説]
プログラムを簡潔に書くためには、string と STL の set が必須です。すべてのパタンを漏らさないように、 set に生成した string を突っ込んでいきます。

[プログラム例]
すべてのパタンを明示的に insert してみました

// @author yutaka C++
// String + Set
#include<iostream>
#include<string>
#include<set>

using namespace std;

set<string> departures;

void insert( string line1, int reversal1, string line2, int reversal2 ){
    if ( reversal1 ) reverse( line1.begin(), line1.end() );
    if ( reversal2 ) reverse( line2.begin(), line2.end() );
    departures.insert( line1 + line2 );
}

void compute(){
    string arrival, storage1, storage2;
    cin >> arrival;
    
    departures.clear();
    
    for ( int d = 0; d < arrival.size() - 1; d++ ){
        storage1 = arrival.substr(0, d + 1);
        storage2 = arrival.substr(d + 1, arrival.size() - d - 1 );
        
        insert( storage1, 0, storage2, 0 );
        insert( storage1, 0, storage2, 1 );
        insert( storage1, 1, storage2, 0 );
        insert( storage1, 1, storage2, 1 );
        insert( storage2, 0, storage1, 0 );
        insert( storage2, 0, storage1, 1 );
        insert( storage2, 1, storage1, 0 );
        insert( storage2, 1, storage1, 1 );
    }
    
    cout << departures.size() << endl;
}

main(){
    int tcase; cin >> tcase;
    for ( int i = 0; i < tcase; i++ ) compute();
}

Dirichlet's Theorem on Arithmetic Progressions

[問題]ACM/ICPC Japan Domestic 2006: Problem A

[解説]
"高速な"素数判定、またはエラトステネスの篩を実装して、おわり。

[プログラム例]

// @author yutaka C++
// Sieve of Eratosthenes
#include<iostream>
#include<cmath>
#define PMAX 1000000

using namespace std;

void eratos( int n, bool prime[] ){
    for ( int i = 0; i <= n; i++ ) prime[i] = false;
    for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
    prime[2] = true;
    int limit = (int)sqrt((double)n) + 1;
    for ( int i = 3; i <= limit; i += 2 ){
        if ( !prime[i] ) continue;
        for ( int j = i * i, k = i * 2; j <= n; j += k ) prime[j] = false;
    }
}

bool prime[PMAX +1];
int a, d, n;

void compute(){
    int curr = 0;
    for ( int i = a; ; i += d ){
        if ( prime[i] ) curr++;
        if ( curr == n ){
            cout << i << endl;
            break;
        }
    }
}

bool input(){
    cin >> a >> d >> n;
    if ( a == 0 && d == 0 && n == 0 ) return false;
    return true;
}

main(){
    eratos( PMAX, prime );
    while ( input() ) compute();
}