スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




Hexerpents of Hexwamp

2006.07.12 20:24  ACM/ICPC

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

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

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




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) | ↑ページトップ |




パソコン甲子園 2003 問題 019

2006.07.06 14:44  パソコン甲子園

[問題]
昨年他界した曽祖父の遺品を整理していたところ、次のような紙がでてきました。

treasure.gif

紙の裏には「最初の数だけ前に進んで、次の数の角度だけ右にまわる(負の数は左にまわる)、それ以降はその繰り返し」とメモがしてあります。祖母によれば「三本松」は、町のちょうど中心にあったそうです。しかし、今はビルや家が立ち並んでいて、ここに書いてあるとおりに歩くことはできません。地図の上で宝のある場所を探してください。

1 歩は 1m だとします。入力データは、進む歩数と回転する角度を書いた行が並んでいて、最後に「0,0」という行があります。最後まで指示どおりに歩いたときに着いた場所を「街の中心から東へ x m, 北へ y m 」のように測り、その x と y を表示して終了するプログラムを作成して下さい。西および南の場合は x, y は負の値となります。x, y ともに整数部を表示して下さい。

[入力]
歩数(100以下の正の整数) 回転角度(-180 以上 180 以下の整数)が半角カンマ区切りで与えられます。

[出力]
x, y をそれぞれ1行に出力して下さい。

[入力例]

56,65
97,54
64,-4
55,76
42,-27
43,80
87,-86
55,-6
89,34
95,5
0,0

[出力例]

171
-302

[解説]
与えられる入力は、現在地から進む距離 length と、"次のステップでの角度"を計算するための angle であることに注意しましょう。また、与えられる角度の単位は度(degree)なので、三角関数を使う場合はラジアンに変換する必要があります。

treasure2.gif

[プログラム例]

// @author yutaka C++
#include<stdio.h>
#include<cmath>

#define PI 3.14159265358979323846

using namespace std;

int length, angle, currentAngle;
double px, py;

void walk(){
    px += length * cos(currentAngle * PI / 180.0);
    py += length * sin(currentAngle * PI / 180.0);
    currentAngle -= angle;
}

main(){
    px = py = 0;
    currentAngle = 90;
    
    while (1){
        scanf("%d,%d", &length, &angle);
        if ( length == 0 && angle == 0 ) break;
        walk();
    }
    
    printf("%d\n%d\n", (int)px, (int)py);
}

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

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




パソコン甲子園 2003 問題 030

2006.07.06 12:44  パソコン甲子園

[問題]
図のようなマス目の「紙」があり、(1, 2)のように x, y の値の対でその上の位置を示すことにします。値は 0 から始まる整数とします。

この「紙」にインキを滴下します。インキ滴には「大」「中」「小」の3サイズがあり、インキ滴の落ちた地点を中心に図のように周囲も色がつきます。図で☆が中心、○が色の滲む範囲です。

ink1.gif

「紙」は、最初は「まっしろ」つまり、どのマスも色の濃さを示す値が 0 とします。インキ滴が落ちるごとに値が 1 ずつ増えていきます。「小の滴」が (1, 2)、「中の滴」が (3, 2) に落ちた場合、各マスの値は次図の左部のようになります。なお空白は値 0 を示します。滲む範囲が紙の外にもなる場合は、紙の外部を無視して下さい。

例えば、白紙に、「小の滴」を (8, 0) に落とした場合は、次図の右部のように y = -1 に相当する部分を無視することになります。同じ場所に複数のインキ滴が落ちることもありえます。

ink2.gif

落とすインキ滴」の x, y, サイズ(小 = 1, 中 = 2, 大 = 3)を入力として読み込んで、色のついてない部分(まだ滲んでこない部分)のマス目の個数と、一番濃いマス目の濃さを出力するプログラムを作成して下さい。なお、「紙」の大きさを 10 × 10 とします。滴下される点の位置を (x, y) とすると、( 0 ≦ x < 10 ), ( 0 ≦ y < 10 ) です。

[入力]

x1,y1,size
x2,y2,size
   .
   .
   .

[出力]
色のついていない部分のマス目の個数を第1行目に。1番濃いマス目の濃さを第2行目に出力して下さい。

[入力例]

2,5,3
3,6,1
3,4,2
4,5,2
3,6,3
2,4,1

[出力例]

77
5


[解説]
この類の問題を解くためのプログラムでは、原点(インキを落とす座標)からの相対座標を求めるために、if 文をごちゃごちゃに駆使し、プログラムが汚くなってしまうケースがよく見うけられます。ポイントは以下の2点です。

  • 紙からインキがはみ出るか否かを調べることを避けるために、いわゆる"番兵"として、紙を表す2次元配列のサイズを x 軸, y 軸それぞれについて 4 づつ増やします(下図参照)。ここで、インキを落とす範囲は、2 ≦ x ≦ 11、 2 ≦ y ≦ 11 となります。番兵の領域に滲んだインキがはみ出ても、配列のサイズを超えることはありません。

  • ink3.gif
  • インキが落とされた原点 (x, y) からの相対座標を求めるために、(x, y) からの差分を記録した配列 dx[], dy[] を用意します(下図参照)。左図は x, y 座標の差分を表します。配列のインデックスの順番を、右図のようにしておくと便利です(プログラム例参照)。

  • ink4.gif

[プログラム例]

// @author yutaka C++
#include<stdio.h>
#define MAX 10

using namespace std;

int paper[MAX + 4][MAX + 4]; // +4 = 番兵

void initialize(){
    for ( int y = 0; y < MAX + 4; y++ ){
        for ( int x = 0; x < MAX + 4; x++ ) paper[y][x] = 0;
    }
}

void drop( int x, int y, int size ){
    x += 2; y += 2; // 番兵の分を足す
    
    static const int dx[13] = {0, 1, 0, -1, 0, 1, -1, -1, 1, 2, 0, -2, 0};
    static const int dy[13] = {0, 0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2};
    
    int limit = size * 4 + 1;
    for ( int r = 0; r < limit; r++ ) paper[y + dy[r]][x + dx[r]]++;
}

main(){
    int x, y, size;
    int numberOfEmpty = 0;
    int maxValue = 0;
    
    initialize();
    
    while ( scanf("%d,%d,%d", &x, &y, &size) != EOF ){
        drop( x, y, size );
    }
    
    for ( int y = 2; y <= 11; y++ ){
        for ( int x = 2; x <= 11; x++ ){
            if ( paper[y][x] == 0 ) numberOfEmpty++;
            if ( paper[y][x] > maxValue ) maxValue = paper[y][x];
        }
    }
    
    printf("%d\n%d\n", numberOfEmpty, maxValue);
}

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

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




Keitai Message

2006.07.05 23:44  ACM/ICPC

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

[解説]
日常で使う携帯電話の機能を実装する問題なので、面白みがあり、プログラミング入門の問題として良いですね。簡単な問題ですが、ポイントは各ボタンに文字列(例えば、ボタン 2 の場合 "abc")を割り当て、押された回数を対応する文字列の長さで割った余りによって、現在の文字のインデックスを特定します。例えば

22222222 は

a → b → c → a → b → c → a → b

となり、最終的に b を指しますが、これは

押された回数 % 文字列の長さ = 8 % 3 = 2

より、"abc" の 2 番目の文字と示すことができます。
(インデックスが 0 から始まるので、プログラム例では -1 していることに注意して下さい)
従って、連続する文字(数字)の数をカウントしながら、0 が入力されたときに上記の計算をして対応する文字を出力するプログラムを書けばよいわけです。

[プログラム例]

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

using namespace std;

static const string T[10] = {"", ".,!? ", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};

void compute(){
    string line; cin >> line;
    int count = 1;
    char pre = line[0];
    for ( int i = 1; i < line.size(); pre = line[i++] ){
        if ( line[i] == '0' && pre != '0' ){
            cout << T[pre-'0'][(count-1)%T[pre-'0'].size()];
            count = 0;
        }
        else if ( line[i] == pre ) count++;
        else  count = 1;
    }
    cout << endl;
}

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

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

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




Red and Black

2006.07.04 23:50  ACM/ICPC

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

[解説]
2次元グリッドにおける深さ優先探索(DFS)

プログラム例

// @author yutaka C++
#include<iostream>
#define MAX 20

using namespace std;

int row, column, si, sj, sum;
char G[MAX+2][MAX+2];
bool visited[MAX+2][MAX+2];

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};

void recursive( int i, int j ){
    sum++;
    visited[i][j] = true;
    
    int ni, nj;
    for ( int r = 0; r < 4; r++ ){
        ni = i + dx[r];
        nj = j + dy[r];
        if ( G[ni][nj] == '.' && !visited[ni][nj] ) recursive(ni, nj);
    }
}

void compute(){
    sum = 0;
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            visited[i][j] = false;
        }
    }
    
    recursive(si, sj);
    
    cout << sum << endl;
}

bool input(){
    cin >> column >> row;
    if ( row == 0 && column == 0 ) return false;
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            cin >> G[i][j];
            if ( G[i][j] == '@' ){
                G[i][j] = '.';
                si = i; sj = j;
            }
        }
    }
    for ( int i = 0; i < row + 2; i++ ) G[i][0] = G[i][column + 1] = '#';
    for ( int j = 0; j < column + 2; j++ ) G[0][j] = G[row+1][j] = '#';
    
    return true;
}

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

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

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




The Secret Number

2006.07.04 23:48  ACM/ICPC

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

[解説]
Dynamic Programming
上から下、左から右、の順に各セルにおける最適な文字列を計算していけば、現在のセルの値を計算する時に、左のセルと上のセルがすでに最適解となっているので、それらの値の大きい方を選び、現在のセルに対応する文字をくっつけていきます。

[プログラム例]

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

#define MAX 72

using namespace std;

int row, column;
char M[MAX][MAX];
string T[MAX][MAX], secret;

string max( string str1, string str2 ){
    if ( str1.size() == str2.size() ){
        return ( str1 > str2 ) ? str1 : str2;
    } else {
        return ( str1.size() > str2.size() ) ? str1 : str2;
    }
}

void compute(){
    secret = "";
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            if ( isalpha( M[i][j] ) ) continue;
            
            T[i][j] = max( T[i-1][j], T[i][j-1] ) + M[i][j];
            // 最初の 0 を��辰9
            if ( T[i][j][0] == '0' ) T[i][j] = T[i][j].substr(1, T[i][j].size()-1);
            secret = max( secret, T[i][j] );
        }
    }
    
    cout << secret << endl;
}

bool input(){
    cin >> column >> row;
    if ( column == 0 && row == 0 ) return false;
    
    // 番弗踉;
    for ( int j = 0; j <= column; j++ ) { M[0][j] = 'A'; T[0][j] = "";}
    for ( int i = 0; i <= row; i++ ) { M[i][0] = 'A'; T[i][0] = "";}
    
    for ( int i = 1; i <= row; i++ ){
        for ( int j = 1; j <= column; j++ ){
            cin >> M[i][j];
            T[i][j] = "";
        }
    }
    
    return true;
}

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

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

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




Ohgas' Fortune

2006.07.04 23:47  ACM/ICPC

[問題]:ACM/ICPC 2005 Problem A

[プログラム例]

// @author yutaka C++
#include<iostream>
#include<algorithm>

using namespace std;

int getTanri( int current, int years, double ratio, int option ){
    int interest = 0;
    for ( int i = 0; i < years; i++ ){
        interest += (int)(current * ratio);
        current -= option;
    }
    return current + interest;
}

int getFukuri( int current, int years, double ratio, int option ){
    for ( int i = 0; i < years; i++ ){
        current += (int)(current * ratio);
        current -= option;
    }
    return current;
}

void work(){
    int current, years, n;
    cin >> current >> years >> n;
    
    int maximum = 0;
    
    int method, option;
    double ratio;
    for ( int i = 0; i < n; i++ ){
        cin >> method >> ratio >> option;
        if ( method == 0 ){
            maximum = max( maximum, getTanri( current, years, ratio, option ));
        } else {
            maximum = max( maximum, getFukuri( current, years, ratio, option ));
        }
    }
    
    cout << maximum << endl;
}

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

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

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




8クイーン問題 Eight Queens Problem

2006.07.03 03:09  探索 II

8クイーン問題とは、8 × 8 のチェス版に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。(※チェスでは、クイーンは以下のように襲撃することができます)

8queens1.gif

この問題を解くための最も素朴な方法が、8 つのクイーンを全ての組み合わせについて配置し、上記のコンディションを満たすかをチェックする方法です。つまり、8 × 8 = 64 のマスから、8 個選ぶ組み合わせなので、

64C8 = 4,426,165,368 通り

無論、この天文学的な数の組み合わせを全て調べることは現実的ではありません。まず、2つ以上のクイーンが同じ行には配置できないので、1行に1つのクイーンしか配置できないことを考えれば、

88 = 16,777,216 通り

と大幅に組み合わせ数を少なくすることができます。さらに、2つ以上のクイーンが同じ列に配置できないことを考えれば、1 行目は 8 つの候補、2 行目は 7 つの候補、3 行目は 6 つの候補、、、8 行目は 1 つの候補、となるので、

8! = 40,320 通り

と導くことは容易です。

しかし、上記の組み合わせを全て調べるよりも、以下のようにバックトラッキングアルゴリズムを適用すれば、さらに効率的に 8 クイーン問題を解くことができます。

1 行目の任意のコマに、クイーンを配置する
1行目に配置したクイーンによって襲撃されない2行目のコマに、クイーンを配置する
...
全てのクイーンが他のどのクイーンも襲撃しないように、i 個のクイーンを最初の i 行に配置したとすれば、前の i 個のどのクイーンにも襲撃されない (i + 1) 行目のコマに、クイーンを配置する
もしも、そのようなコマが (i + 1) 行目のコマに存在しなければ、i 行目に戻り i 行目に配置するクイーンのための他の襲撃されないコマを探し(もしそのようなコマがなければ、さらに (i - 1) 行目に戻る)、探索を続行します。

このアルゴリズムの実装では、コマ (i, j) が他のクイーンによって襲撃されているか否かを記録するために、以下の配列を用意します。

row[8] row[x] が NOT_FREE ならば、row[x] は襲撃されている
col[8] col[x] が NOT_FREE ならば、col[x] は襲撃されている
dpos[15] dpos[x] が NOT_FREE ならば、dpos[x] は襲撃されている
dneg[15] dnedg[x] が NOT_FREE ならば、dneg[x] は襲撃されている

つまり、row[i]、col[j]、dpos[i+j]、dneg[i-j+N-1] のいづれかが NOT_FREE であれば、コマ (i, j) が襲撃されていることになります。逆に考えれば、row[i]、col[j]、dpos[i+j]、dneg[i-j+n-1] すべてが FREE のとき、クイーンを配置することができます。各配列のインデック(i, j, i+j, i-j+N-1)の関係は下図を参照して下さい。

row: x = i col: x = j
attack1.gif
attack2.gif

dpos: x = i + j dneg: x = i - j + (N - 1)
attack3.gif
attack4.gif

// @author yutaka C++
// N queens problem: 全ての可能な配置と総数を出力
#include<iostream>
using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[2*N-1], dneg[2*N-1];
int counter;

void initialize(){
    for ( int i = 0; i < N; i++ ){ row[i] = FREE, col[i] = FREE; }
    for ( int i = 0; i < 2*N - 1; i++ ) { dpos[i] = FREE; dneg[i] = FREE; }
}

void printBoard(){
    for ( int i = 0; i < N; i++ ){
        for ( int j = 0; j < N; j++ ){
            cout << (( row[i] == j ) ? "Q" : ".");
        }
        cout << endl;
    }
    cout << endl;
}

void recursive( int i ){
    if ( i == N ){ // SUCCESS
        counter++;
        printBoard(); return;
    }
    
    for ( int j = 0; j < N; j++ ){
        // if (i, j) is attacked by other queens, continue
        if ( col[j] == NOT_FREE || dpos[i+j] == NOT_FREE ||
        dneg[i-j+N-1] == NOT_FREE ) continue;
        // put a queen on (i, j)
        row[i] = j; col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
        // try next row
        recursive( i + 1 );
        // remove the queen from (i, j)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
    }
    
    // FAIL
}

main(){
    initialize();
    counter = 0;
    recursive( 0 );
    cout << counter << endl;
}

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

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




Backtracking バックトラック

2006.07.03 03:04  探索 II

とてつもない数の"見込みのある解"の中から、解を探さなければならないというような問題は数多く存在します。これらの問題を解くアルゴリズムは、ある起点から出発し、特定の経路を探索することによって、解を見つけます。

backtracking.gif

しかし、多くの問題では、どのような経路が解へと導くかが不明です。このような問題を解くためには、可能な経路をすべて探索(総当り)する方法が考えられますが、探索しなければならない空間が膨大な場合には、無駄な探索を避けるためのテクニックが必須となります。

バックトラッキング Backtracking は、見込みのあるすべての探索空間を体系的(計画的)に探索する方法です。バックトラッキングでは、今いる地点からこれ以上探索が不可能と分かった時、または問題の定義によってこれ以上探索しても無駄であると断定できる時に、そこで探索を打ち切り、前の地点に戻って探索を続行します。

グラフにおける Depth First Search が、バックトラックアルゴリズムの良い例となります。

バックトラックが適用できる問題の例

  • 8クイーン問題

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

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

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。