fc2ブログ



Curling 2.0

2006.07.07 15:06  ACM/ICPC

[問題]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();
}
スポンサーサイト



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

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




Organize Your Train part II

2006.07.07 15:05  ACM/ICPC

[問題]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();
}

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

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




Dirichlet's Theorem on Arithmetic Progressions

2006.07.07 15:01  ACM/ICPC

[問題]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();
}

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

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




ACM/ICPC 国内予選 2006

2006.07.07 14:56  ACM/ICPC

ID 問題 難易度 考察
A Dirichlet's Theorem on Arithmetic Progressions
B Organize Your Train part II ★☆
C Hexerpents of Hexwamp ★★★★
D Curling 2.0 ★★☆
E The Genome Database of All Space Life ★★☆ 作成中
F Secrets in Shadows ★★★★★ grave

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

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