カード

パソコン甲子園 2006 カード

問題はこちら

連鎖行列積問題の解法と同様に動的計画法で解きます。

例えば、下図のように５枚のカードの山があるとします。



まず最初に、隣り合う２組の山を重ねるときの最小のコストを計算します（j = 1）。
i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。

つぎに、隣り合う３組の山を重ねるときの最小のコストを計算します(j = 2)。
i = 1, 2, 3 について計算します。

つぎに、隣り合う４組の山を重ねるときの最小のコストを計算します(j = 3)。
i = 1, 2 について計算します。

同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。
i = 1 について計算します。


各 j の値での最小コストの計算方法を考えます。
例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります：

• カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+1)
• カードの山[1,2]とカードの山[3,4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+2)
• カードの山[1,2,3]とカードの山[4]をそれぞれ重ねるのに要した最小コスト　＋　それら２つの山を重ねるコスト　(k = i+3 = i+j)

#include<iostream>
using namespace std;
#define MAX 100
#define INFTY (1<<24)

struct Card{ int top, bottom; };

Card C[MAX+1];
int N;

int getCost(){
    int cost[MAX+1][MAX+1];
    for ( int i = 1; i <= N; i++ ){
        for ( int j = 1; j <= N; j++ ) cost[i][j] = INFTY;
    }
    for ( int i = 1; i <= N; i++ ) cost[i][i] = 0;

    for ( int j = 1; j <= N-1; j++ ){
        for ( int i = 1; i <= N-j; i++ ){
            for ( int k = i+1; k <= i+j; k++ ){
                int mul = C[i].top * C[k-1].bottom * C[k].top * C[i+j].bottom;
                cost[i][i+j] = min( cost[i][i+j], cost[i][k-1] + cost[k][i+j] + mul );
            }
        }
    }

    return cost[1][N];
}

main(){
    cin >> N;
    for ( int i = 1; i <= N; i++ ) cin >> C[i].top >> C[i].bottom;
    cout << getCost() << endl;
}

Discrete Speed

Discrete Speed
ダイクストラのD。
「現在の場所、前にいた場所、速度」のノードでグラフを作りました。

#include<iostream>
#include<cstdio>
#include<queue>
#define rep(i, n) for ( int i = 0; i < n; i++ )
using namespace std;
#define MAX 30
#define VMAX 30
#define INFTY (1 << 21)

class State{
    public:
    int pos, from, v;
    double cost;
    
    State( int pos=0, int from=0, int v=0, double cost=0): pos(pos), from(from), v(v), cost(cost){}

    bool operator < ( const State &s) const{
        return cost > s.cost;
    }
};

int n, m, s, g, D[MAX+1][MAX+1], C[MAX+1][MAX+1];

void dijkstra(){
    priority_queue<State> PQ;
    double cost[MAX][MAX][VMAX+1];
    bool visited[MAX][MAX][VMAX+1]; // pos, from, v

    rep(i, n) rep(j, n) rep(k, VMAX+1) {
        cost[i][j][k] = INFTY;
        visited[i][j][k] = false;
    }

    for ( int v = 0; v < n; v++ ){
        if ( D[s][v] == INFTY ) continue;
        cost[v][s][1] = D[s][v]/1.0;
        PQ.push( State(v, s, 1, D[s][v]/1.0) );
    }

    State u, v;

    while( !PQ.empty() ){
        u = PQ.top(); PQ.pop();
        visited[u.pos][u.from][u.v] = true;
        if ( u.pos == g && u.v == 1 ) {
            printf("%.12lf\n", cost[u.pos][u.from][u.v] );
            return;
        }
        for ( int v = 0; v < n; v++ ){
            if ( D[u.pos][v] == INFTY ) continue;
            for ( int nv = u.v-1; nv <= u.v+1; nv++ ){
                if ( visited[v][u.pos][nv] || nv > C[u.pos][v] || v == u.from ) continue;
                double c = cost[u.pos][u.from][u.v] + 1.0*D[u.pos][v]/nv;
                if ( cost[v][u.pos][nv] > c ){
                    cost[v][u.pos][nv] = c;
                    PQ.push( State(v, u.pos, nv, c) );
                }
            }
        }
    }

    cout << "unreachable" << endl;
}

main(){
    int x, y, d, c;
    while( cin >> n >> m && n  ){
        cin >> s >> g; s--; g--;
        rep(i, n) rep(j, n) { D[i][j] = C[i][j] = INFTY; }
        rep(i, m){
            cin >> x >> y >> d >> c; x--; y--;
            D[x][y] = D[y][x] = d;
            C[x][y] = C[y][x] = c;
        }
        dijkstra();
    }
}

Verbal Arithmetic

Verbal Arithmetic
バックトラックで解いてみました。 適当な枝刈りをすれば手元で１０秒くらいorz。

優れた解法はlaycurseさんのブログを参照。

#include<iostream>
#include<string>
using namespace std;
#define MAX 12

int N, L[26], R[26], LT[26][10], RT[26][10];
string S[MAX];
int num[26];
bool used[10];
int cnt, MDL[26], MDR[26];

void setValue( string str, int a[] ){
    for ( int i = str.size()-1, p = 1; i >= 0; i--, p *= 10 ){
        a[str[i] - 'A'] += p;
    }
}

bool zeroCheck(){
    for ( int i = 0; i < N; i++ ){
        if ( S[i].size() > 1 && num[S[i][0]-'A'] == 0 ) return false;
    }
    return true;
}

void rec( int cur, int left, int right ){
    if ( cur == 26 ){
        if ( left == right && zeroCheck() ) cnt++;
        return;
    }

    if ( left + MDL[cur] < right ) return;
    if ( right + MDR[cur] < left ) return;
    
    if ( L[cur] + R[cur] == 0 ){ rec( cur+1, left, right ); return; }

    for ( int d = 9; d >= 0; d-- ){
        if ( used[d] ) continue;
        used[d] = true;
        num[cur] = d;
        rec( cur+1, left + L[cur]*d, right + R[cur]*d );
        used[d] = false;
    }
}

void makeMD(){
    int md = 0;
    MDL[25] = 9*(L[25]);
    MDR[25] = 9*(R[25]);
    for ( int i = 24; i >= 0; i-- ){
        MDL[i] = MDL[i+1] + (L[i])*9;
        MDR[i] = MDR[i+1] + (R[i])*9;
    }
}

main(){
    while ( cin >> N && N ){
        for ( int i = 0; i < 26; i++ ) { L[i] = R[i] = 0;}
        for ( int i = 0; i < N; i++ ) {
            cin >> S[i];
            if ( i == N-1 ) setValue( S[i], R );
            else setValue( S[i], L );
        }

        makeMD();

        for ( int i = 0; i <= 9; i++ ) used[i] = false;
        cnt = 0;
        rec(0, 0, 0);
        cout << cnt << endl;
    }
}

How Many Islands?

How Many Islands?
パソコン甲子園に同じような問題が出題されていたような...

#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define MAX 50

int W, H, G[MAX][MAX];

void dfs( int i, int j){
    G[i][j] = 0;
    static const int di[8] = {0, -1, -1, -1, 0, 1, 1, 1};
    static const int dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    rep(r, 8){
        int ni = i + di[r];
        int nj = j + dj[r];
        if ( ni < 0 || nj < 0 || ni >= H || nj >= W ) continue;
        if ( G[ni][nj] ) dfs(ni, nj);
    }
}

main(){
    while( cin >> W >> H && W && H ){
        rep(i, H) rep(j, W) cin >> G[i][j];
        int cnt = 0;
        rep(i, H) rep(j, W) if ( G[i][j] ){ cnt++; dfs(i, j); }
        cout << cnt << endl;
    }
}

Next Mayor

Next Mayor

#include<iostream>
using namespace std;
#define MAX 50

int n, p, B[MAX], t;

main(){
    while( cin >> n >> p && n && p ){
        for ( int i = 0; i < n; i++ ) B[i] = 0;
        int cur = 0;
        for(t = p; ; cur = (cur+1)%n){
            if ( p ) { 
                B[cur]++; p--;
                if ( p == 0 && B[cur] == t ){
                    cout << cur << endl; break;
                }
            } else { 
                p  = B[cur]; B[cur] = 0; 
            }
        }
    }
}

ACM-ICPC 国内予選 2009

番号	問題	難易度
A	Next Mayor	★
B	How Many Islands?	★
C	Verbal Arithmetic	★★☆
D	Discrete Speed	★★★
E	Cards	★★★☆
F	Tighten Up!	★★★★☆