ALGORITHM NOTE

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

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

番号	問題	難易度	分野
問題01	十日市での人気の出典は	☆	基礎
問題02	野球大会	★	ソート
問題03	最大公約数-ユークリッドの互除法	★	整数
問題04	芸術家品川のピンチ	★★☆	シミュレーション
問題05	難儀な人たちが座る椅子	★★☆	シミュレーション
問題06	高校生一人旅～青春の片道切符編～	★★☆	グラフ・最短経路
問題07	錬金マスター	★★★	動的計画法（探索？）
問題08	上司のおごり	★★★	動的計画法
問題09	会津山スキー場の新企画	★★★	動的計画法
問題10	UFO撃墜作戦	★★★☆	計算幾何学・ｼﾐｭﾚｰｼｮﾝ

難易度の差や想定解法などを考えると、 バランスの良い問題セットとは言えませんね。

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

パソコン甲子園2009予選 問題10 UFO 撃墜作戦


計算幾何学＋シミュレーションの問題です。
円と線分の交差判定ができるかが問われています。

少し面倒ですが、円と直線の交点を求めて、 それが有効範囲のレザーの上(線分)にあるかどうかを判定しました。

#include<iostream>
#include<cfloat>
#include<cassert>
#include<cmath>
#include<vector>

using namespace std;

#define EPS (1e-8)
#define equals(a, b) (fabs((a) - (b)) < EPS )
#define dle(a, b) (equals(a, b) || a < b )
static const double PI = acos(-1);

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); }

    double abs() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator == ( const Point &p ) const {
        return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
};

typedef Point Vector;

class Segment{
    public:
    Point p1, p2;
    Segment(Point s = Point(), Point t = Point()): p1(s), p2(t){}
};

typedef Segment Line;

class Circle{
    public:
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0.0): c(c), r(r){}
};

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double abs( Vector a ){ return sqrt(norm(a)); }
Point polar( double a, double r ){ return Point(cos(r)*a, sin(r)*a);}
double getDistance( Vector a, Vector b ){ return abs(a - b); }
double scalar( 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; }

double arg(Vector p){
    return atan2(p.y, p.x);
}

double getDistanceLP(Line s, Point p){
    return abs(cross(s.p2 - s.p1, p - s.p1)/abs(s.p2 - s.p1));
}

bool isIntersect( Circle c1, Line l ){
    double d = getDistanceLP(l, c1.c);
    return ( equals(d, c1.r) || d < c1.r );
}

pair<Point, Point> getCrossPoints(Circle c1, Line l ){
    assert( isIntersect( c1, l ) );
    double d = getDistanceLP(l, c1.c);
    Point v = l.p2 - l.p1;
    if ( cross(l.p2 - l.p1, c1.c - l.p1) > EPS ){
        v = polar(abs(v), arg(v)-acos(-1)/2);
    } else {
        v = polar(abs(v), arg(v)+acos(-1)/2);
    }
    double th = acos(d/c1.r);
    Point v1 = polar(c1.r, arg(v) + th );
    Point v2 = polar(c1.r, arg(v) - th );
    return make_pair(c1.c+v1, c1.c+v2);
}

enum {NON, IN, OUT};

double R;

class UFO{
    public:
    Circle body;
    double v, dx, dy;
    int state;

    UFO( Circle c = Circle(Point(0,0),0), double v=0):body(c), v(v){
        Point ct = Point(0, 0);
        Vector a = ct - body.c;
        dx = v*cos(arg(a));
        dy = v*sin(arg(a));
        state = NON;
    }

    void move(){
        if ( state != NON ) return;
        double pred = getDistance(Point(0, 0), body.c);
        if ( v > pred || equals(v, pred)){ state = IN; return; }
        body.c.x += dx;
        body.c.y += dy;
        double d = getDistance(Point(0, 0), body.c);
        if ( R > d || equals(R, d) ) state = IN;
    }
};

#define MAX 100

UFO U[MAX];
int n;

void attack( Point p1, Point p2){
    Line l = Line(p1, p2);
    for ( int i = 0; i < n; i++ ){
        if ( U[i].state != NON ) continue;
        if ( !isIntersect(U[i].body, l) ) continue;
        pair<Point, Point> pp = getCrossPoints(U[i].body, l);
        if ( equals( arg(p2 - p1), arg(pp.first - p1)) && 
             getDistance(p1, pp.first) > R ) U[i].state = OUT;
        if ( equals( arg(p2 - p1), arg(pp.second - p1)) && 
             getDistance(p1, pp.second) > R ) U[i].state = OUT;
    }
}

int simulate(){
    while(1){
        int life = 0;
        for ( int i = 0; i < n; i++ ) {
            U[i].move();
            if ( U[i].state == NON ) life++;
        }
        if ( life == 0 ) break;

        int target = -1;
        double md = FLT_MAX;
        for ( int i = 0; i < n; i++ ){
            if ( U[i].state != NON ) continue;
            double d = getDistance(Point(0, 0), U[i].body.c);
            if ( d < md ){
                md = d;
                target = i;
            }
        }
        attack(Point(0, 0), U[target].body.c);
    }

    int cnt = 0;
    for ( int i = 0; i < n; i++ ) if ( U[i].state == IN ) cnt++;
    return cnt;
}

main(){
    double x, y, r, v;
    while( cin >> R && R ){
        cin >> n;
        for ( int i = 0; i < n; i++ ){
            cin >> x >> y >> r >> v;
            U[i] = UFO(Circle(Point(x, y), r), v);
        }
        cout << simulate() << endl;
    }
}

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

パソコン甲子園2009予選 問題09 会津山スキー場の新企画


典型的な動的計画法の問題です。

マス(y, x)にたどり着く場合の数は、以下のものの合計になります：

• マス(y-1, x) (そこが移動可能なマスの場合)
• マス(y-1, x-1) (そこが移動可能なマスの場合)
• マス(y-1, x+1) (そこが移動可能なマスの場合)
• マス(y-2, x) (そこがジャンプ台の場合)

ただし、 y が増えていく方向に（順番に）計算を行います。
例えば、マス（y, x）が移動可能な場所であれば、
マス(y+1, x)
マス(y+1, x-1)
マス(y+1, x+1)
にそれぞれ マス(y, x)の値を加算していきます（移動可能な場合のみ）。

#include<iostream>
using namespace std;
#define rep(i,s,e) for ( int i = s; i <= e; i++)
#define MAX 15
#define TREE 1
#define JUMP 2
#define SNOW 0
int X, Y;
int G[MAX+2][MAX+2];

int compute(){
    int T[MAX+2][MAX+2];
    rep(y,0,Y+1) rep(x,0,X+1) T[y][x] = 0;

    rep(x,1,X){
        if ( G[0][x] == TREE || G[0][x] == JUMP ) continue;
        int s = -1, t = 1;
        if ( 0 == Y-1 ) s = t = 0;
        rep(dx,s,t){ // G[0][x] == SNOW
            if ( G[1][x+dx] == SNOW ) T[1][x+dx]++;
            if ( G[1][x+dx] == JUMP && dx == 0 ) T[1][x+dx]++;
        }
    }

    rep(y,1,Y-1) rep(x,1,X){
        if ( G[y][x] == SNOW ){
            int s = -1, t = 1;
            if ( y == Y-1 ) s = t = 0;
            rep(dx,s,t){
                if ( G[y+1][x+dx] == SNOW ) T[y+1][x+dx] += T[y][x];
                if ( G[y+1][x+dx] == JUMP && dx == 0 ) T[y+1][x+dx] += T[y][x];
            }
        } else if ( G[y][x] == JUMP ){
            if ( G[y+2][x] != TREE ) T[y+2][x] += T[y][x];
        }
    }

    int sum = 0;
    rep(y,Y,Y+1) rep(x,1,X) sum += T[y][x];
    return sum;
}

main(){
    while( cin >> X >> Y && X && Y ){
        rep(y,0,Y-1) rep(x,0,X+1) G[y][x] = TREE;
        rep(y,Y,Y+1) rep(x,0,X+1) G[y][x] = SNOW;
        rep(y,0,Y-1) rep(x,1,X) cin >> G[y][x];
        cout << compute() << endl;
    }
}

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

パソコン甲子園2009予選 問題08 上司のおごり


典型的な動的計画法の問題です。

K[i] を i 番目の金額、
Tⁱ[j] を i 番目までの金額を使って j を払えるかのフラグとする （1の場合に払えるものとする）と、

T⁰[j] を 0 で初期化し、
Tⁱ[j] = T^i-1[j] | T^i-1[j - K[i]]

となります。

あとは、i が素数で T[i] が 1 である i の最大値を求めます。

#include<iostream>
using namespace std;
#define KMAX 30
#define VMAX 1000000

int K[KMAX], T[VMAX+1];

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;
    for ( int i = 3; i*i <= n; i += 2 ){
        if ( !prime[i] ) continue;
        for ( int j = i + i; j <= n; j += i ) prime[j] = false;
    }
}

main(){
    bool prime[VMAX + 1];
    eratos( VMAX, prime );

    int k, v;
    while( cin >> k >> v && k && v ){
        for ( int i = 0; i < k; i++ ) cin >> K[i];
	
        for ( int j = 0; j <= v; j++ ) T[j] = 0;
        for ( int j = K[0]; j <= v; j += K[0] ) T[j] = 1;
        T[0] = 1;
        for ( int i = 1; i < k; i++ ){
            for ( int j = K[i]; j <= v; j++ ){
                T[j] = (T[j] | T[j-K[i]]);
            }
        }
        int ans = -1;
        for ( int i = v; i >= 2; i-- ){
            if ( prime[i] && T[i] ) { ans = i; break; }
        }
	
        if ( ans == -1 ) cout << "NA" << endl;
        else cout << ans << endl;
    }
}

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