ALGORITHM NOTE

パソコン甲子園　2009 本線

algorithm — 2010-01-21T20:44:47+09:00

番号	問題	難易度	分野
問題01	じゃんけん	★	基礎
問題02	旅行はいつ?		基礎
問題03	ブロック	★	グラフ
問題04	病院の部屋番号	★☆	整数
問題05	写真に写っている景色は?	★★	全探索
問題06	ザ・スクエアーズ	★★☆	シミュレーション
問題07	みんなでジョギング	★★☆	整数
問題08	高速バス	★★★	グラフ
問題09	土地分割	★★★	バックトラック
問題10	秋のイルミネーション	★★★	計算幾何学
問題11	パチモンクリーチャー	★★★☆	動的計画法

パチモンクリーチャー

algorithm — 2010-01-21T20:40:33+09:00

パソコン甲子園2009 問題11 パチモンクリーチャー

問題文

X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。

最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Directed Acyclic Graph）の最短コストを求めることになります。下図は、3体の氷のパチクリ、2体の木のパチクリ、3体の土のパチクリ、2体の水のパチクリを含むグリッドをDAGで表したものです。捕まえられないパチクリがいるマスを通っても現在保持しているパチクリの状態に影響はないので、ノード間の距離は対応するマス間のマンハッタン距離（x座標の差とy座標の差の和）となります。スタート地点で選ぶパチクリを変えて（５種類分ありますが、下図では最初に火のパチクリを選んでいます）、動的計画法によってゴールまでの最短コストを求めます。

#include<cstdio>
#include<iostream>
using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++ )
#define MAX 1000
#define INFTY (1<<21)
struct Point{ int x, y; };
int H, W, sy, sx, gy, gx, cnt[5];
Point P[5][MAX];
int D[5][MAX];

inline int mdist(int x1, int y1, int x2, int y2){
    return max(x1, x2) - min(x1, x2) + max(y1, y2) - min(y1, y2);
}

void compute(){
    int opts, optc = INFTY;
    int t;
    rep(s, 5){
        rep(i, 5) rep(j, cnt[i]) D[i][j] = INFTY;
        t = (s+1)%5;
        rep(j, cnt[t]) D[t][j] = mdist(sx, sy, P[t][j].x, P[t][j].y );
        for ( int i = s+1; i < s + 5; i++ ){
            int b = (i)%5;
            int e = (i+1)%5;
            rep(k, cnt[b]) rep(l, cnt[e]) {
                D[e][l] = min(D[e][l], D[b][k] + mdist(P[b][k].x, P[b][k].y, P[e][l].x, P[e][l].y));
            }
        }
	t = (s+4)%5;
        rep(j, cnt[t] ){
            if ( D[t][j] + mdist(gx, gy, P[t][j].x, P[t][j].y ) < optc ){
                optc = D[t][j] + mdist(gx, gy, P[t][j].x, P[t][j].y);
                opts = s;
            }
        }
    }
    if ( optc == INFTY ) cout << "NA" << endl;
    else cout << opts+1 << " " << optc << endl;
}

main(){
    char ch;
    while(cin >> W >> H && W){
        rep(i, 5) cnt[i] = 0;
        rep(y, H) rep(x, W) {
	    cin >> ch;
	    if ( ch == '.' ) continue;
	    if ( ch == 'S' ){
		sy = y; sx = x;
	    } else if ( ch == 'G' ){
		gy = y; gx = x;
	    } else {
		int p = ch -'0' - 1;
		P[p][cnt[p]].x = x;
		P[p][cnt[p]++].y = y;
	    }
        }
        compute();
    }
}

秋のイルミネーション

algorithm — 2010-01-21T20:34:03+09:00

パソコン甲子園2009 問題10 秋のイルミネーション

問題文

凸な四角形がいくつか与えられ、重なったあるいは触れている四角形を１つのグループと見なし、いくつのグループが存在するかを求める問題です。

２つの四角形が接触しているかどうかを判定するプログラムを使ってグラフをつくり、連結成分の数を深さ優先探索で求めます。四角形Ａのいづれかの辺と四角形Ｂのいづれかの辺が接触している、四角形Ａが四角形Ｂの頂点を含む、または四角形Ｂが四角形Ａの頂点を含む場合、四角形Ａと四角形Ｂが同じグループに属すると判定することができます。

#include<iostream>
#include<cfloat>
#include<cmath>
#include<vector>
using namespace std;
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )
#define EPS (1e-8)

class Point{
    public:
    double x, y;
    
    Point ( double x = 0, double y = 0): x(x), y(y){}
    Point operator + ( Point p ){ return Point(x + p.x, y + p.y); }
    Point operator - ( Point p ){ return Point(x - p.x, y - p.y); }
    Point operator * ( double a ){ return Point(x*a, y*a); }
};
typedef Point Vector;
typedef vector<Point> Polygon;

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double dot( Vector a, Vector b ){ return a.x*b.x + a.y*b.y; }
double cross( Vector a, Vector b ){ return a.x*b.y - a.y*b.x; }

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if ( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS ) return CLOCKWISE;
    if ( dot(a, b) < -EPS ) return ONLINE_BACK;
    if ( norm(a) < norm(b) ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool isIntersect(Point p1, Point p2, Point p3, Point p4){
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
	     ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}

bool isInside(Polygon pol, Point p){
    rep(i, 4){
	if ( ccw(pol[i], pol[(i+1)%4], p ) == COUNTER_CLOCKWISE ) return false;
    }
    return true;
}

bool isIntersectSQ(Polygon p1, Polygon p2 ){
    rep(i, 3) rep(j, 3){
	if ( isIntersect(p1[i], p1[i+1], p2[j], p2[j+1] ) ) return true;
    }
    rep(i, 4) if(isInside(p1, p2[i])) return true;
    rep(i, 4) if(isInside(p2, p1[i])) return true;
    return false;
}

Polygon P[100];
int n, G[100][100];
bool V[100];

void dfs( int u ){
    V[u] = true;
    rep(v, n) if ( G[u][v] && !V[v] ) dfs(v);
}

int compute(){
    rep(i, n) rep(j, n ) G[i][j] = 0;
    rep(i, n) rep(j, n ) if ( isIntersectSQ(P[i], P[j]) ) G[i][j] = 1;
    rep(i, n) V[i] = false;
    int ncomponent = 0;
    rep(i, n){
	if ( V[i] ) continue;
	ncomponent++;
	dfs(i);
    }
    return ncomponent;
}

int main(){
    int N;
    double x, y;
    while( cin >> N && N ){
	rep(i, N){
	    cin >> n;
	    rep(j, n){
		Polygon pol;
		rep(k, 4){
		    cin >> x >> y;
		    pol.push_back(Point(x, y));
		}
		P[j] = pol;
	    }
	    cout << compute() << endl;
	}
    }
    return 0;
}

土地分割

algorithm — 2010-01-21T20:30:53+09:00

パソコン甲子園2009 問題09 土地分割

問題文

X×Y個のマスから成るグリッドで表された分譲地を、長方形の区画に分割する問題です。各区画の大きさ（マスの数）とその区画が含まなければならないマス（看板で示されています）が入力として与えられます。

全ての区画について順番に、要求された大きさの長方形で分譲地を埋めていきます。各区画の長方形の大きさと位置については、すでに決定した他の区画と重ならずかつ分譲地からはみ出さないような全てのパタンについて調べます。この処理は、再帰関数によって実装します。全ての区画について長方形が配置できかつ全てのマスが0以外で埋まっている場合は解としてカウントし、そうでない場合はバックトラックでさらに探索を行います。

#include<iostream>
#include<cassert>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define MAX 10
struct Cell{ int i, j, x, id; };

int H, W, n, b, k, ans, V[MAX+1]; 
Cell P[MAX*MAX], M[MAX][MAX], A[MAX][MAX];

bool placeable(int si, int sj, int r, int c ){
    rep(i, r) rep(j, c){
	int ii = si + i;
	int jj = sj + j;
	if ( ii < 0 || jj < 0 || ii >= H || jj >= W ) return false;
	if ( M[ii][jj].x ) return false;
    }
    return true;
}

void solve(int pos){
    if ( pos >= n ){ 
	rep(i, H) rep(j, W) if ( M[i][j].x == 0 ) return;
	rep(i, H) rep(j, W) A[i][j] = M[i][j];
	ans++;
	return;
    }

    for(int r = 1; r <= P[pos].x; r++){
	if ( P[pos].x % r != 0 ) continue;
	int c = P[pos].x / r;
	rep(di, r) rep(dj, c){
	    int si = P[pos].i - di;
	    int sj = P[pos].j - dj;
	    if ( placeable( si, sj,  r, c ) ){
		rep(i, r) rep(j, c) M[si+i][sj+j] = P[pos];
		solve( pos + 1 );
		rep(i, r) rep(j, c) M[si+i][sj+j].x = 0;
	    }
	}
    }
}

int main(){
    int x;
    while( cin >> W >> H && H && W ){
	cin >> n;
	rep(i, n){
	    cin >> b >> k;
	    P[b-1].x = k;
	}

	rep(i, H) rep(j, W){
	    cin >> x;
	    if ( x ){  P[x-1].i = i; P[x-1].j = j; P[x-1].id = x-1; }
	    M[i][j].x = 0;
	}
	ans = 0;
	solve(0);
	if ( ans == 1 ) {
	    rep(i, H){
		rep(j, W){
		    if ( j ) cout << " ";
		    cout << A[i][j].id+1;
		}
		cout << endl;
	    }
	} else {
	    cout << "NA" << endl;
	}
    }
    return 0;
}

高速バス

algorithm — 2010-01-21T20:26:49+09:00

パソコン甲子園2009 問題08 高速バス

問題文

グラフのノード間（バス停間）の最短経路のコストを求める問題です。ただし、チケットを使った場合はノード間を行き来するコストが半分になります。最初に持っているチケットの数、スタート地点、ゴール地点が与えられたときの最短コストを求めなければなりません。

基本的にはダイクストラのアルゴリズムで解きます。ただし、グラフのノードは、与えられたグラフのノードi（バス停）と残りのチケットの枚数kの組になります。つまり、２次元配列D[i][k]に「k枚のチケットを持ちバス停iにいるスタート地点からの最小コスト」をダイクストラのアルゴリズムで記録します。

#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define MAX 100
#define INFTY (1<<21)
int G[MAX][MAX], c, n, s, d;

int dijkstra(){
    int D[MAX][11];
    bool V[MAX][11];
    rep(i, n) rep(k, c+1) { D[i][k] = INFTY; V[i][k] = false; }
    D[s][c] = 0;
    while(1){
	int u, w, minv = INFTY;
	rep(i, n) rep(k, c+1){
	    if ( !V[i][k] && minv > D[i][k] ){ 
		minv = D[i][k]; u = i; w = k; 
	    }
	}
	if ( minv == INFTY ) break;
	V[u][w] = true;
	rep(v, n){
	    if ( G[u][v] == INFTY ) continue;
	    D[v][w] = min(D[v][w], D[u][w] + G[u][v]);
	    if ( w ) D[v][w-1] = min(D[v][w-1], D[u][w] + G[u][v]/2);
	}
    }
    int minv = INFTY;
    rep(k, c+1) minv = min(minv, D[d][k]);
    return minv;
}

main(){
    int m, a, b, f;
    while( cin >> c >> n >> m >> s >> d && c){
	s--; d--;
	rep(i, n) rep(j, n) G[i][j] = INFTY;
	rep(i, m){
	    cin >> a >> b >> f; a--; b--;
	    G[a][b] = G[b][a] = f;
	}
	cout << dijkstra() << endl;
    }
}

みんなでジョギング

algorithm — 2010-01-21T20:24:52+09:00

パソコン甲子園2009 問題07 みんなでジョギング

問題文

同じスタート地点にいるn人の人がそれぞれ1周di(km)のコースをvi(km/h)で走り続けるとき、全員が再びスタート地点で同時に出会ったときの、それぞれの周回数を求める問題です。

n人をそれぞれ0～n-1の番号iで表すことにします。まず、計算途中でのオーバーフローを避けるために、それぞれのvi/diを約分します。次にvi/di (i = 0 ～ n-1)を通分します。全ての分母diに対する最小公倍数LCMを分母とすると、それぞれの分子はvi×LCM/diとなります。最後に全ての分子をそれらの最大公約数で割ると、最初に全員が出会う周回数となります。最大公約数を求めるためにはユークリッドの互除法を用います。

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ullong;
#define MAX 10

ullong gcd(ullong a, ullong b){
    return ( b == 0 ) ? a : gcd(b, a%b);
}

ullong lcm( ullong a, ullong b ){
    if ( b > a ) swap(a, b);
    return a/gcd(a, b)*b;
}

void compute(int n){
    ullong d1, d2, v1, v2, G;
    pair<ullong, ullong> S[MAX];
    for ( int i = 0; i < n ; i++ ){
	cin >> S[i].first >> S[i].second;
	G = gcd(S[i].first, S[i].second);
	S[i].first /= G;
	S[i].second /= G;
    }

    ullong l = lcm(S[0].first, S[1].first);
    for ( int i = 2; i < n; i++ ) l = lcm(l, S[i].first);
    
    ullong A[MAX];
    for ( int i = 0; i < n; i++ ) A[i] = S[i].second*(l/S[i].first);
    G = gcd(A[0], A[1]);
    for ( int i = 2; i < n; i++ ) G = gcd(G, A[i]);
    for ( int i = 0; i < n; i++ ) cout << A[i]/G << endl;
}

main(){
    int n;
    while( cin >> n && n ) compute(n);
}

ザ・スクエアーズ

algorithm — 2010-01-21T20:21:07+09:00

パソコン甲子園2009 問題06 ザ・スクエアーズ

問題文

グリッドで表された迷路の中にいる人々が、全員脱出するために必要な時間をシミュレーションによって求める問題です。一定時間毎に、グリッドのマスにいる人がある定められたルールに従いマス目間を移動していきます。

問題文に書かれている手順でアルゴリズムを実装します。最初のステップで、各人についてその人の方向を定義されたルールに従い決定します。次のステップにて、各人について現在の方向に動けるか否かを定義されたルールに従い決定し、動ける場合は移動します。

#include<iostream>
#include<string>
#include<cassert>
using namespace std;
#define rep(i,n) for ( int i = 0; i < n; i++ )
#define REP(i, b, e) for ( int i = b; i <= e; i++ )
#define MAX 100
#define LIMIT 180
#define BLOCK '#'
#define SPACE '.'
#define EXIT 'X'
static const string DIR = "ENWS";
static const int di[4] = {0, -1, 0, 1};
static const int dj[4] = {1, 0, -1, 0};
int H, W;
char G[MAX+2][MAX+2];

bool isPerson(char ch){
    rep(d, 4) if ( ch == DIR[d] ) return true;
    return false;
}

int getDirection(char ch){
    rep(d, 4) if ( ch == DIR[d] ) return d;
}

int chengeDirection(){
    int nperson = 0;
    REP(i, 1, H) REP(j, 1, W){
	if ( !isPerson(G[i][j]) ) continue;
	nperson++;
	int curd = getDirection(G[i][j]);
	int v = curd;
	curd = ((curd == 0) ? 3 : curd-1);
	for ( int r = curd; r < curd + 4; r++ ){
	    char ch = G[i+di[r%4]][j+dj[r%4]];
	    if ( ch == SPACE || ch == EXIT ){
		v = r%4;
		break;
	    }
	}
	G[i][j] = DIR[v];
    }
    return nperson;
}

void move(){
    int dir[MAX+2][MAX+2];
    rep(i, H+2) rep(j, W+2 ) dir[i][j] = -1;

    REP(i, 1, H) REP(j, 1, W){
	if ( G[i][j] == SPACE || G[i][j] == EXIT){
	    for ( int r = 0; r < 4; r++ ){
		char target = G[i+di[r]][j+dj[r]];
		if ( isPerson(target) && target == DIR[(r+2)%4] ){
		    dir[i+di[r]][j+dj[r]] = (r+2)%4;
		    break;
		}
	    }
	}
    }

    REP(i, 1, H) REP(j, 1, W){
	if ( !isPerson(G[i][j]) || dir[i][j] == -1) continue;
	int ni, nj;
	ni = i + di[dir[i][j]];
	nj = j + dj[dir[i][j]];

	if ( G[ni][nj] == EXIT ){
	    G[i][j] = SPACE;
	} else if ( G[ni][nj] == SPACE ){
	    G[ni][nj] = G[i][j];
	    G[i][j] = SPACE;
	}
    }
}

int main(){
    while(1){
	cin >> W >> H;
	if ( H == 0 && W == 0 ) break;
	rep(i,H+2) rep(j,W+2) G[i][j] = BLOCK;
	REP(i, 1, H) REP(j, 1, W) cin >> G[i][j];
	int t = 0;
	while(1){
	    if ( t > LIMIT ) break;
	    if( !chengeDirection() ) break;
	    move();
	    t++;
	}
	if ( t > LIMIT ) cout << "NA" << endl;
	else cout << t <<  endl;
    }

    return 0;
}

写真に写っている景色は？

algorithm — 2010-01-21T20:05:08+09:00

パソコン甲子園2009 問題05 写真に写っている景色は？

問題文

数字が書かれたn×n個のマスから成るグリッドにおいて、同じく数字が書かれたm×m個のマスから成るグリッドを0, 90, 180, または270度回転させたパタンに一致する領域を探し、その位置を出力する問題です。

m×mのグリッドを回転しながら、全ての場所について一致しているかを調べていきます。n×nのグリッドにおけるm×mの領域について、上から下、左から右の順番で調べていきます。各領域について、m×mのグリッドを回転させ、重なった部分のマスが全て一致するか（問題の仕様上-1は無視します）をチェックします。

#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )
#define NMAX 200
#define MMAX 100
#define INFTY (1<<21)
int n, m, T[NMAX][NMAX], P[MMAX][MMAX];

void valid(int sx, int sy, int &lx, int &ly ){
    int ax = -1, ay;
    rep(y, m) rep(x, m){
	if ( P[x][y] == -1 ) continue;
	if ( P[x][y] != T[sx+x][sy+y] ) return;
	if ( ax == -1 ) {ay = y; ax = x;}
    }
    if ( ay < ly || (ay == ly && ax < lx) ) {ly = sy+ay; lx = sx+ax; }
}

bool rotate(int sx, int sy){
    int tmp[MMAX][MMAX];
    int ly = INFTY, lx;
    rep(r, 4){
	valid(sx, sy, lx, ly);
	rep(y, m) rep(x, m) tmp[x][y] = P[x][y];
	rep(y, m) rep(x, m) P[y][m-x-1] = tmp[x][y];
    }
    if ( ly == INFTY ) return false;
    cout << lx+1 << " " << ly+1 << endl;
    return true;
}

void compute(){
    rep(y, n-m+1) rep(x, n-m+1) if ( rotate(x, y) ) return;
    cout << "NA" << endl;
}

main(){
    while( cin >> n >> m && n ){
	rep(y, n) rep(x, n) cin >> T[x][y];
	rep(y, m) rep(x, m) cin >> P[x][y];
	compute();
    }
}