パソコン甲子園 2009 本線

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

パチモンクリーチャー

パソコン甲子園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();
    }
}

秋のイルミネーション

パソコン甲子園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;
}

土地分割

パソコン甲子園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;
}

高速バス

パソコン甲子園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;
    }
}

みんなでジョギング

パソコン甲子園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);
}

ザ・スクエアーズ

パソコン甲子園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;
}

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

パソコン甲子園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();
    }
}

病院の部屋番号

パソコン甲子園2009 問題04 病院の部屋番号

問題文

4と6の数字を使わない数字の列S = {1, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 15, ...} のn番目の数を求めよという問題です。ただし、nの値は最大1,000,000,000です。

nの値が非常に大きいため、数列を生成して解くことはできません。4と6の2つの数字を用いてはいけないので、10 – 2 = 8 進数でnを表せばよいことになります。ただし、基数変換後の数の各桁の数字をdとすると、dが0～3の場合はそれぞれ0～3、dが4の場合はd+1(4の分)= 5、dが5以上の場合はd+2(4と6の分)に変換して出力します。文字列”01235789”のd番目の文字を返す関数を定義しても良いでしょう。

#include<iostream>
using namespace std;

int getValue(int x){
    if ( x == 4 ) return 5;
    return (x < 4) ? x : x+2;
}

void convert( int n ){
    if ( n == 0 ) return;
    convert( n/8 );
    cout << getValue(n%8);
}

main(){
    int n;
    while( cin >> n && n ) { convert(n); cout << endl; }
}

ブロック

パソコン甲子園2009 問題03 ブロック

問題文

2次元グリッド（配列）上に迷路を作り、スタートのマスからゴールのマスまでの道があるかどうかを判定する問題です。各マスには色がつけられ、色が同じマス間を上下左右の方向に移動することができます。

深さ優先探索または幅優先探索によって解くことができます。以下に示す解答プログラムでは深さ優先探索を実装しています。深さ優先探索は、一度訪問したマスを二度訪問しないように注意しながら、再帰的に隣接するマスを訪問していくアルゴリズムです。プログラムの関数dfsに示すように、グリッドにおける探索の問題では、現在地からのx方向及びy方向への移動距離を示すdx[4]、dy[4]を宣言しておくと、グリッドのマス間の移動の記述を簡潔に記述することができます。

#include<iostream>
using namespace std;
#define MAX 100
static const int dx[4] = {1, 0, -1, 0};
static const int dy[4] = {0, -1, 0, 1};

int w, h, sx, sy, gx, gy, G[MAX+2][MAX+2];
 
bool dfs( int x, int y, int color ){
    if ( color == 0 || G[x][y] != color ) return false;
    if ( x == gx && y == gy ) return true;
    G[x][y] = 0;
    for ( int r = 0; r < 4; r++ ){
	if ( dfs(x + dx[r], y + dy[r], color) ) return true;
    }
    return false;
}

main(){
    int n, c, d, px, py, ww, hh;
    while( cin >> w >> h && w ){
	cin >> sx >> sy >> gx >> gy >> n;
	for ( int y = 0; y < h+2; y++ )
	    for ( int x = 0; x < w+2; x++ ) G[x][y] = 0;
	for ( int i = 1; i <=n; i++ ){
	    cin >> c >> d >> px >> py;
	    if ( d == 0 ) { ww = 4; hh = 2; }
	    else { ww = 2; hh = 4; }
	    for ( int y = 0; y <= hh-1; y++ )
		for ( int x = 0; x <= ww-1; x++ ) G[px+x][py+y] = c;
	}
	if ( dfs(sx, sy, G[sx][sy]) ) cout << "OK" << endl;
	else cout << "NG" << endl;
    }
}

旅行はいつ？

パソコン甲子園2009 問題02 旅行はいつ？

問題文

1カ月に得られるお小遣いMと使うお金Nの組を12カ月分入力し、目的の金額Lに達するために必要な月数tを求める問題です。

合計金額Sが目的の金額Lに達したとしても12カ月分（i: 1～12）のMとNの組を読み込まなければならないことに注意しながら、(M - N)の合計金額Sが目的の金額Lに達する月tを求めます。tの初期値を0とし、SがL以上でかつtが0（初期値から未だ変更されていないことを示す）のとき、tに現在の月iを代入します。

#include<iostream>
using namespace std;

main(){
    int L, M, N;
    while( cin >> L && L ){
	int t = 0, S = 0;
	for ( int i = 1; i <= 12; i++ ){
	    cin >> M >> N; 
	    S += M - N;
	    if ( S >= L && t == 0 ) t = i;
	}
	if ( S < L ) cout << "NA" << endl;
	else cout << t << endl;
    }
}

じゃんけん

パソコン甲子園2009 問題01 じゃんけん

問題文

５人がじゃんけんをしたときのそれぞれの手（グー、チョキ、パーをそれぞれ1～3で表します）を入力し、それぞれの人の勝ち・負け・引き分け（それぞれ1～3で表します）を判定する問題です。

様々なアルゴリズムが考えられる興味深い問題の１つです。ここでは、２重ループを使ったアルゴリズムで解きました。各人について他の４人に対する勝ち・負けの数をそれぞれ数え、「勝ちが1つ以上でかつ負けが0」の場合は勝ち（1）、「負けが1つ以上でかつ勝ちが0」の場合は負け（2）、その他の場合は引き分け（3）、と判定することができます。２人に対する勝敗判定については、1（グー）→ 2 （チョキ）→ 3（パー）→ 1（グー）・・・という関係があるので、Ａ君の手をa、Ｂ君の手をbとすれば、a%3 が b-1 に等しいとき、Ａ君がＢ君に勝ったと判定することができます。ここで、a%3はaを3で割った余りを示します。

データセットごとに処理しなければならない入力については、一人目の手を読み込みそれが0でない場合処理を行うという繰り返し構造とし、処理の最初に残りの４人分の手を読み込むとう手順で記述すると良いでしょう。

#include<iostream>
using namespace std;
#define N 5

main(){
    int T[N];
    while( cin >> T[0] && T[0] ){
	for ( int i = 1; i < N; i++ ) cin >> T[i];
	for ( int i = 0; i < N; i++ ){
	    int w = 0, l = 0;
	    for ( int j = 0; j < N; j++ ){
		if ( T[i]%3 == T[j]-1 ) w++;
		if ( T[j]%3 == T[i]-1 ) l++;
	    }
	    if ( w && !l ) cout << 1 << endl;
	    else if ( l && !w ) cout << 2 << endl;
	    else cout << 3 << endl;
	}
    }
}