難儀な人たちが座る椅子

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