土地分割

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

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!	★★★★☆