ALGORITHM NOTE

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

番号	問題	難易度	分野
問題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;
    }
}

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

パソコン甲子園2009予選 問題07 錬金マスター


レシピの連鎖にサイクルが無いので、再帰で最小コストを求めることができます。

問題の仕様は残念ながら簡単化されていて（難易度調整のためでしょう）、サイズが小さく、作るものも１つ、１つのアイテムを作るレシピはたかだか１つしかないので、メモする（動的計画法にする）必要もないようです。

以下のプログラムは１つのアイテムが複数のレシピを持てるようにしてあります。

名前、値段、レシピのリストを持つ Item クラスを作ります。
getCost( stirng name ) で名前が nameである アイテム item を作る最小のコストを求めます。
最小のコストは以下のうち小さい方になります：

• item のコスト
• item を作るレシピの中でコストが最小のものであるコスト

この問題の仕様ではレシピが１つしかないので、以下のうち小さい方を選べばよい：

• item のコスト
• item をレシピで作る（ある場合は）コスト

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

#define MAX 200

class Item{
    public:
    string name;
    int cost;
    vector<vector<string> > recipes;

    Item(){}
    Item( string name, int cost ): name(name), cost(cost){ recipes.clear(); }

    void addRecipe(vector<string> r ){ recipes.push_back(r);}
};

int n;
map<string, int> N_I;
Item items[MAX];

int getCost( string name ){
    Item item = items[ N_I[name] ];
    int cost = item.cost;

    for ( int i = 0; i < item.recipes.size(); i++ ){
        vector<string> recipe = item.recipes[i];
        int sum = 0;
        for ( int j = 0; j < recipe.size(); j++ ){
            sum += getCost( recipe[j] );
        }
        cost = min( cost, sum );
    }

    return cost;
}

main(){
    int q, cost, nr, k;
    string name, source;
    while( cin >> n && n){
        for ( int i = 0; i < n; i++ ){
            cin >> name >> cost;
            items[i] = Item(name, cost);
            N_I[name] = i;
        }
        cin >> nr;
        for ( int i = 0; i < nr; i++ ){
            cin >> name >> k;
            vector<string> recipe;
            for ( int j = 0; j < k; j++ ){
                cin >> source;
                recipe.push_back(source);
            }
            items[ N_I[name] ].addRecipe(recipe);
        }
        cin >> name;
        cout << getCost( name ) << endl;
    }
}

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

パソコン甲子園2009予選 問題06 高校生一人旅 ~青春の片道切符編~


グラフの最短経路（コスト）を求める問題です。残念ながら典型的な問題です。
ワーシャルフロイドが想定解法なのかもしれませんが、 ダイクストラのアルゴリズムで解きました。

#include<cstdio>
#include<queue>
#include<algorithm>
#define rep(i,b,e) for ( int i = b; i <= e; i++ )
using namespace std;

#define MAX 1000
#define INFTY (1<<21)
int n, C[MAX+1][MAX+1], T[MAX+1][MAX+1];

class State{
    public:
    int p, e;
    State( int p = 0, int e = 0 ): p(p), e(e){}
    bool operator < ( const State &s ) const{
        return e > s.e;
    }
};

int dijkstra( int s, int t, int type ){
    priority_queue<State> PQ;
    bool visited[MAX+1];
    int d[MAX+1];
    rep(i,1,n){
        visited[i] = false;
        d[i] = INFTY;
    }
    PQ.push(State(s, 0));
    d[s] = 0;
    State u;
    while( !PQ.empty() ){
        u = PQ.top(); PQ.pop();
        if ( u.p == t ) return u.e;
        visited[u.p] = true;
        rep(v,1,n){
            if ( C[u.p][v] == INFTY || visited[v] ) continue;
            int cost = C[u.p][v];
            if ( type  ) cost = T[u.p][v];
            if ( d[v] > d[u.p] + cost ){
                d[v] = d[u.p] + cost;
                PQ.push(State(v, d[v]));
            } 
        }
    }
    return -1;
}

main(){
    int k, s, t, cost, tm, q, r;
    while(1){
        scanf("%d %d", &k, &n);
        if ( n == 0 && k == 0 ) break;
        rep(i,1,n) rep(j,1,n) { C[i][j] = T[i][j] = INFTY; }
        rep(i,1,k){
            scanf("%d %d %d %d", &s, &t, &cost, &tm);
            C[s][t] = C[t][s] = cost;
            T[s][t] = T[t][s] = tm;
        }
        scanf("%d", &q);
        rep(i,1,q){
            scanf("%d %d %d", &s, &t, &r);
            printf("%d\n", dijkstra(s, t, r) );
        }
    }
}

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

パソコン甲子園2009予選 問題05 難儀な人たちが座る椅子


面倒なシミュレーションの問題です。

A, B, C, D それぞれの国の人の座り方をシミュレートする関数、setLeft, setB, setC, setD を素直に作りました。

椅子の状態を保持する配列（ここでは配列C）の先頭と末尾に番兵として'X'などを入れておくと実装が楽になるかと思います。

setD で使う getDist(int p, int d) は、p 番目の椅子から d 方向 （正が右、負が左）への空席の数を返します。

問題原文にある、椅子のサイズは大きすぎると思うのですが・・・ミスプリントでしょうね（AOJでは修正されています）。

#include<iostream>
using namespace std;
#define rep(i,s,e) for ( int i = s; i <= e; i++ )
#define MAX 10000
#define INFTY 1000000
char C[MAX+2];
int n, m;

void setLeft(char ch){
    for ( int i = 1; ; i++ ) if ( C[i] == '#' ) { C[i] = ch; return; }
}

void setB(){
    for ( int i = n; i >= 1; i-- ){
        if ( C[i] == '#' && C[i-1] != 'A' && C[i+1] != 'A' ){
            C[i] = 'B'; return;
        }
    }
    setLeft('B');
}

bool isEmpty(){
    rep(i,1,n) if ( C[i] != '#' ) return false;
    return true;
}

void setC(){
    if ( isEmpty() ){ C[n/2+1] = 'C'; return; }
    rep(i,1,n){
        if ( C[i] == '#' ) continue;
        if ( C[i+1] == '#' ) { C[i+1] = 'C'; return; }
        if ( C[i-1] == '#' ) { C[i-1] = 'C'; return; }
    }
}

int getDist( int p, int d){
    int cur = 0;
    while( C[p+cur+d] == '#' ) cur += d;
    if ( C[p+cur+d] == 'X' ) cur = d*INFTY;
    return (cur<0)?-1*cur:cur;
}

void setD(){
    if ( isEmpty() ){ C[1] = 'D'; return; }
    int d, mi, md = -1;
    rep(i,1,n){
        if ( C[i] != '#' ) continue;
        d = min(getDist(i, 1), getDist(i, -1));
        if ( d > md ) { md = d; mi = i;	}
    }
    C[mi] = 'D';
}

main(){
    char ch;
    while( cin >> n >> m && n && m ){
        rep(i,0,n+1) C[i] = '#';
        C[0] = C[n+1] = 'X';
        rep(i,1,m){ 
            cin >> ch;
            if ( ch == 'A' ) setLeft('A');
            else if ( ch == 'B' ) setB();
            else if ( ch == 'C' ) setC();
            else if ( ch == 'D' ) setD();
        }
        rep(i,1,n) cout << C[i];
        cout << endl;
    }
}

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

パソコン甲子園2009予選 問題04 芸術家品川のピンチ


少し面倒なサイコロ（立方体）回転シミュレーションの問題です。

x軸、y軸、z軸を中心に回転させるメソッドを定義した Cubeクラスを作り、 与えられたサイコロの中でユニークなものの数を数えます。

サイコロiとサイコロjが等しいかどうかは、 サイコロjの向きを固定し、サイコロiを回転させて、全ての向き（２４通り）についてjと比較し、１つでも一致すれば、等しいと判断します。

#include<iostream>
#include<string>
#include<cassert>
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define REP(i, s, e) for ( int i = s; i <= e; i++ )
using namespace std;
#define MAX 100

class Cube{
    public:
    string f[6];
    Cube(){}
    void roll_z(){ roll(1, 2, 4, 3);}
    void roll_y(){ roll(0, 2, 5, 3);}
    void roll_x(){ roll(0, 1, 5, 4);}
    void roll(int i, int j, int k, int l){
        string t = f[i]; f[i] = f[j]; f[j] = f[k]; f[k] = f[l]; f[l] = t;
    }
};

Cube C[MAX];
int n;

bool eq( Cube c1, Cube c2 ){
    rep(i, 6) if ( c1.f[i] != c2.f[i] ) return false;
    return true;
}

bool equal( Cube c1, Cube c2 ){
    rep(i, 6){
        rep(j, 4){
            if ( eq(c1, c2) ) return true;
            c1.roll_z();
        }
        if ( i % 2 == 0 ) c1.roll_y();
        else c1.roll_x();
    }
    return false;
}

main(){
    while( cin >> n && n ){
        rep(i, n) rep(j, 6) cin >> C[i].f[j];
        int cnt = 0;
        REP(i,0,n-1) {
            bool hasSame = false;
            REP(j, i+1, n-1){
                if ( equal(C[i], C[j] ) ) hasSame = true;
            }
            if ( !hasSame ) cnt++;
        }
        cout << n - cnt << endl;
    }
}

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