fc2ブログ



11パズル

2008.11.21 14:04  パソコン甲子園 2008

問題 パソコン甲子園2008 08

下図のような11パズルを解く最短の手数を求めよ。ただし、20手以内で解けない場合はNAと出力する。

11パズル
入力例
2
1 0 3
4 5 6 7 8
9 0 11
10
0
1 2 3
4 5 6 7 8
9 10 11
0
0
11 10 9
8 7 6 5 4
3 2 1
0
-1

出力例
2
0
NA


解説

幅優先探索では「時間切れ」になってしまいます。
この問題は、両側探索または反復深化等のヒューリスティックを用いた探索でなければ解けません。以下は、反復深化による解法です。

サンプルプログラム

#include
#include

using namespace std;

#define N 5
#define REP(i, n) for ( int i = 0; i < (int)n; i++ )
#define LIMIT 20

static const int T[12][2] = {{-1, -1}, {1, 1}, {1, 2}, {1, 3}, {2, 0}, {2, 1},
			     {2, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 3}};
static const int g[N][N] = {{-1, -1, 0, -1, -1}, {-1, 1, 2, 3, -1},
			    {4, 5, 6, 7, 8}, {-1, 9, 10, 11, -1}, {-1, -1, 0, -1, -1}};

class Puzzle{
    public:
    int C[N][N], mdist; //manhatta distance
    Puzzle(){}

    bool swapAdj( int si, int sj, int ti, int tj ){
	if ( ti < 0 || tj < 0 || ti >= N || tj >= N ) return false;
	if ( C[ti][tj] <= 0 ) return false;
	swap(C[ti][tj], C[si][sj]);
	int tti = T[C[si][sj]][0];
	int ttj = T[C[si][sj]][1];
	mdist -= max(tti, ti)-min(tti, ti) + max(ttj, tj)-min(ttj, tj);
	mdist += max(tti, si)-min(tti, si) + max(ttj, sj)-min(ttj, sj);
	return true;
    }

    bool isGoal(){
	REP(i, N) REP(j, N) if ( g[i][j] != C[i][j] ) return false;
	return true;
    }

    int getMD(){ // get initial manhattan distance
	int sum = 0;
	int ti, tj;
	REP(i, 5) REP(j, 5){
	    if ( C[i][j] <= 0 ) continue;
	    ti = T[C[i][j]][0];
	    tj = T[C[i][j]][1];
	    sum += (max(ti, i)-min(ti, i) + max(tj, j) - min(tj, j));
	}
	return sum;
    }
};

int limit;

bool dfs( int depth, Puzzle P ){
    if ( P.isGoal() ) return true;
    if ( depth + P.getMD() > limit ) return false;

    static const int di[4] = {0, -1, 0, 1};
    static const int dj[4] = {1, 0, -1, 0};

    REP(i, N) REP(j, N){
	if ( P.C[i][j] != 0 ) continue;
	REP(r, 4){
	    Puzzle v = P;
	    if ( !v.swapAdj(i, j, i+di[r], j+dj[r]) ) continue;
	    if ( dfs( depth + 1, v ) ) return true;
	}
    }

    return false;
}

int idp(Puzzle source){
    for ( limit = 0; limit <= LIMIT; limit++ ){
	source.mdist = source.getMD();
	if ( dfs(0, source) ) return limit;
    }
    return INT_MAX;
}

int main(){
    Puzzle P;
    int top;

    while(1){
	cin >> top;
	if ( top == -1 ) break;
	REP(j, N) P.C[0][j] = -1;
	P.C[0][2] = top;
	for(int i = 1; i < N; i++) REP(j, N){
	    if ( (i == 1 || i == 3) && (j == 0 || j == 4 ) ) P.C[i][j] = -1;
	    else if ( i == 4 && j != 2 ) P.C[i][j] = -1;
	    else cin >> P.C[i][j];
	}

	int cost = idp(P);
	if ( cost == INT_MAX ) cout << "NA" << endl;
	else cout << cost << endl;	
    }

    return 0;
}

スポンサーサイト



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

| コメント(0) | トラックバック(0) | ↑ページトップ |




白虎運送

2008.11.19 09:49  パソコン甲子園 2008

問題 パソコン甲子園2008 12

下図に示すように、M本の東西方向の道路、N本の南北の道路からなる格子状の地図において、トラックが始点の交差点から終点の交差点までたどり着くまでの最短時間を求めよ。

白虎運送
トラックは東西南北方向の交差点に進入できるが、来た方向へはUターンできない。さらに、交差点には信号機がある所があり、各信号機のシグナルは一定の周期で東西ー南北方向に切り替わる(赤と青のみ)。交差点に進入できるのは進行方向の信号機が青の場合である。また、交差点から隣の交差点への移動には一定の時間D分を要するが、渋滞の道路ではさらにd分要する。工事中で通れない道路もある。

N, M <= 20 であり、トラックは100分以内で目的地に到達できるものとする。


解説

最短経路問題なので、ダイクストラのアルゴリズムで解けそうですが、この問題の場合、以下のような状態空間を定義すれば、深さ優先探索で解くことができます。

V[y][x][t][d]: dの方向から交差点(y, x)に時刻tで到達することができれば、V[y][x][t][d] がtrueであるような4次元配列

トラックは100分以内で目的地に到達できるので、t <= 100 であり、メモリも間に合います。
目的地の座標 (y, x) について、Vの値が最初に true となる t の値が答えになります。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 #define REP(i, n) for ( int i = 0; i < (int)n; i++ )
005 #define GMAX 20
006 #define TMAX 100
007 #define INFTY (1<<21)
008 
009 int N, M, D, sy, sx, gy, gx;
010 int G[GMAX][GMAX][GMAX][GMAX], S[GMAX][GMAX];
011 bool V[GMAX][GMAX][TMAX+1][4];
012 
013 static const int dy[4] = {0, -1, 0, 1};
014 static const int dx[4] = {1, 0, -1, 0};
015 
016 bool valid( int y , int x ){
017     return ( 0 <= y && 0 <= x && y < N && x < M );
018 }
019 
020 void dfs( int y, int x, int t, int d ){
021     V[y][x][t][d] = true;
022     
023     int ny, nx, nt;
024     for ( int nd = 0; nd < 4; nd++ ){
025         if ( (d+2)%4 == nd ) continue;
026         
027         ny = y + dy[nd];
028         nx = x + dx[nd];
029         
030         if ( !valid(ny, nx) ) continue;
031         if ( G[y][x][ny][nx] == INFTY ) continue;
032         
033         nt = t + G[y][x][ny][nx];
034         
035         if ( nt > TMAX ) continue;
036         
037         if ( S[ny][nx] > 0 ){
038             if ( nd % 2 == 0 ){
039                 if ( (nt/S[ny][nx])%2 != 1 ) continue;
040             } else {
041                 if ( (nt/S[ny][nx])%2 != 0 ) continue;
042             }
043         }
044         
045         if ( V[ny][nx][nt][nd] ) continue;
046         
047         dfs( ny, nx, nt, nd );
048     }
049 }
050 
051 int compute(){
052     REP(y, N) REP(x, M) REP(t, TMAX+1) REP(d, 4) V[y][x][t][d] = false;
053     REP(d, 4) dfs( sy, sx, 0, d );
054     
055     REP(t, TMAX+1) REP(d, 4) if ( V[gy][gx][t][d] ) return t;
056 }
057 
058 int getNumber( char ch ){ return ch - 'a';}
059 
060 bool input(){
061     cin >> N >> M;
062     if ( N == 0 && M == 0 ) return false;
063     cin >> D;
064     
065     int ny, nx;
066     REP(y, N) REP(x, M){
067         S[y][x] = 0;
068         REP(nd, 4){
069             ny = y + dy[nd];
070             nx = x + dx[nd];
071             if ( valid(ny, nx) ){
072                 G[y][x][ny][nx] = G[ny][nx][y][x] = D;
073             }
074         }
075     }
076     
077     int nsignal, nconst, njam, y1, x1, y2, x2, k, d;
078     char ch, tmp;
079     
080     cin >> nsignal;
081     for ( int i = 0; i < nsignal; i++ ){
082         cin >> ch  >> tmp >> x1 >> k; x1--;
083         S[getNumber(ch)][x1] = k;
084     }
085     
086     cin >> nconst;
087     for ( int i = 0; i < nconst; i++ ){
088         cin >> ch >> tmp >> x1; x1--;
089         y1 = getNumber(ch);
090         cin >> ch >> tmp >> x2; x2--;
091         y2 = getNumber(ch);
092         G[y1][x1][y2][x2] = G[y2][x2][y1][x1] = INFTY;
093     }
094     
095     cin >> njam;
096     for ( int i = 0; i < njam; i++ ){
097         cin >> ch >> tmp >> x1; x1--;
098         y1 = getNumber(ch);
099         cin >> ch >> tmp >> x2 >> d; x2--;
100         y2 = getNumber(ch);
101         G[y1][x1][y2][x2] += d;
102         G[y2][x2][y1][x1] += d;
103     }
104     
105     cin >> ch >> tmp >> sx; sy = getNumber(ch);
106     cin >> ch >> tmp >> gx; gy = getNumber(ch);
107     sx--; gx--;
108     return true;
109 }
110 
111 int main(){
112     while( input() ) cout << compute() << endl;
113     return 0;
114 }

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

| コメント(0) | トラックバック(0) | ↑ページトップ |




パソコン甲子園2008

2008.11.19 09:33  パソコン甲子園 2008

パソコン甲子園2008本線問題

番号問題難易度点数
01 三目並べ 30
02 鶴ヶ城 20
03 ゴールドバッハ予想 20
04 会津地鶏 ★☆ 20
05 投石おみくじ ★★ 20
06 探索 40
07 便利なのはどこ? ★★☆ 40
08 11パズル ★★★☆ 70
09 おおきくなあれ ★★★ 70
10 鶴ヶ城駐車場 ★★★ 90
11 デブンイレブン ★★★ 90
12 白虎運送 ★★★☆ 90


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

| コメント(0) | トラックバック(0) | ↑ページトップ |




ビーカー

2008.09.16 21:55  パソコン甲子園 2008


問題 パソコン甲子園2008 10



いろいろな容量のビーカーがあります。はじめに、その中の一番容量が大きなビーカーに水を満タンに注ぎます。次に、以下のルールに従いビーカーの水を他のビーカーに写し変えていきます:

  • ビーカーに入っている水は、残さずに全て他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せない場合は、複数のビーカーに分けて移すことができる


  • ビーカーに水を入れるとき、満タンになるまで水を注がなければならない。また、水をこぼしてはならない。


  • 複数のビーカーから同じビーカーに一度に水を注いではならない。

  • 同じビーカーには一度しか水を注いではならない。



このルールに従ったとき、すべてのビーカーに水を注ぐことができるかどうかを判定して下さい。ビーカーの数 n は 1 以上 50 以下です。



解説

問題が分かりづらいですが、「すべてのビーカーに水を注ぐことができるか」というのは「水を移し変える一連の操作の過程で、すべてのビーカーが使われたか」を意味します。

うまく枝を刈りながらバックトラックを行います。

再帰関数の構造

pour() は注ぐビーカー(source)を選び searchTarget() で注がれるビーカー(target)を決定します。searchTarget() が成功したら、さらに pour() を呼び出します。

サンプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 50
005 #define NOT_USED 0
006 #define USED 1
007 #define ISFULL 2
008
009 bool searchTarget(int, int, int, int );
010 bool pour(int, int);
011
012 int size, C[MAX], state[MAX];
013
014 bool searchTarget( int volume, int source, int startt, int nfilled, int remain ){
015 if ( volume == 0 ){
016 state[source] = USED;
017 if( pour(nfilled, remain) ) return true;
018 state[source] = ISFULL;
019 return false;
020 } else if ( volume < 0 || startt < 0 || remain < volume ) return false;
021
022 for ( int i = source - 1; i >= 0; i-- ){
023 if ( state[i] == ISFULL ) break;
024 if ( state[i] == NOT_USED && C[i] > volume ) return false;
025 }
026
027 int pre = -1;
028 for ( int target = startt; target >= 0; target-- ){
029 if ( state[target] >= 1 || C[target] > volume ) continue;
030 if ( pre == C[target] ) continue; // pre 彫髏オッ椎タ彫ネ彫キ彫ソ彫竰、ホ彫マ彫ケ彫ヌ彫ヒ懲・・勅ヌ綴、長、槌、彫、k
031 state[target] = ISFULL;
032 if ( searchTarget( volume - C[target], source, target-1, nfilled+1, remain-C[target] ) ) return true;
033 state[target] = NOT_USED;
034 pre = C[target];
035 }
036 return false;
037 }
038
039 bool pour( int nfilled, int remain ){
040 if ( nfilled == size ) return true;
041
042 for ( int source = size-1; source >= 1; source-- ){
043 if ( state[source] == ISFULL ) {
044 if ( searchTarget( C[source], source, source-1, nfilled, remain )) return true;
045 }
046 }
047
048 return false;
049 }
050
051 bool judge(){
052 sort( C, C + size );
053 int remain = 0;
054 for ( int i = 0; i < size; i++ ) {
055 state[i] = NOT_USED;
056 remain += C[i];
057 }
058 state[size-1] = ISFULL;
059 remain -= C[size-1];
060 return pour( 1 , remain );
061 }
062
063 int main(){
064 while ( cin >> size && size ) {
065 for ( int i = 0; i < size; i++ ) cin >> C[i];
066 if ( judge() ) cout << "YES" << endl;
067 else cout << "NO" << endl;
068 }
069 return 0;
070 }



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

| コメント(1) | トラックバック(0) | ↑ページトップ |




こだわり

2008.09.15 13:58  パソコン甲子園 2008

問題 パソコン甲子園2008 09

厚さが異なる n 冊の本を、 k 段の本棚に入れるとき、本棚の最小の幅を求めて下さい。

pck200809.gif
出典:パソコン甲子園2008

入力例
3 9
500
300
800
200
100
600
900
700
400
4 3
1000
1000
1000
0 0

出力例
1800
1000

解説

Partition Problem といいます。

[この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。]

出題者が求めた解法は、動的計画法または二分法だと思います。
ここでは、動的計画法でこの Partition Problem を解きます。


Partition Problem とは、n 個の数からなる数列

S = {s1, ..... sn}

を k 個の部分に分割するときに、各部分の数字の和をできるだけ均等にする、という問題です。厳密に言えば、各部分の数字の和の最大値を最小にするような分割を行います。

例えば、k が 3 の場合、数列

5 3 8 2 1 6 9 7 4



5 3 8 | 2 1 6 | 9 7 4

と 3 つに分割することができます(これは最適な解ではありません)。
この場合は各部分の合計は、16, 9, 20 となり、その最大は 20 となります。
ところが、同じ数列を

5 3 8 | 2 1 6 9 | 7 4

と分割すれば、各部分の合計は 16, 18, 11 となり、その最大が 18 となります。そしてこれが最適解となります(最大値が 18 を下回る分割方法はない)。

仮にこの問題を nCk の組み合わせで総当たりに計算しても、本棚の厚みを少しづつ増やしていく方法で反復的に計算しても、その計算量は膨大になります。

では、動的計画法で解いてみましょう。
まず、以下のデータを用意します。

S : 入力の数列である1次元配列 (最初の要素をS[1]とします)
P : P[i] = P[i-1] + S[i] であるような、1次元配列
P[i] には、最初の要素S[1] から S[i] までの合計が記録されています。
M : M[i][j] が 1 から i 番目までの要素を使い S を j 以下の部分に分割したときの最適解(部分の最大値の最小値)を示す2次元配列

(1) j = 1 の場合、1 ~ i までの要素を 1 個に分割するので、
M[i][1] = P[i] (i = 1,,,n)
となります。

(2) i = 1 の場合、1 つの要素を j 個に分割するので、
M[1][j] = S[1] (j = 1,,,k)
となります。

(3) 2 <= i, 2 <= j の場合 M[i][j] は
x が 1 から i-1 について、S[1] ~ S[i] を S[1] ~ S[x] と S[x+1] ~ S[i] の2つの部分に分けたとき、M[x][j-1] と P[i] - P[x] の大きい方が最小になるような x での最小値になります。ここで、M[x][j-1] は、1 から x 番目までの要素を使い S を j-1 個の部分に分割したときの最適解、
P[i] - P[x] は、x+1 から i 番目までの要素を1つの部分とした場合の合計値

を示します。上記のデータを例にとると、M[i][j]は以下のようになります。
123
1555
2855
31688
418108
519118
625169
7341815
8412216
9452518

例えば i = 6, j = 3 の場合は以下の組み合わせが考えられますが、この中で最適なものを選びます。


絵を準備。。。

サンプルプログラム

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

| コメント(0) | トラックバック(0) | ↑ページトップ |




デブンキー一家の大活躍

2008.09.15 13:46  パソコン甲子園 2008

問題 パソコン甲子園2008 08

n 個の都市がり、それらが m 本の橋で繋がっています。各橋の維持費(コスト)が決められています。どの都市にでも行くことができるように橋を残しつつ、橋の維持費の合計が最小になるように、いくつかの橋を壊したときの、維持費の合計を求めて下さい。


解説

重み付きグラフの最小全域木を求める問題です。サンプルは Prim のアルゴリズムで解きました。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define REP(i, e) for ( int i = 0; i < e; i++ )
004 #define MAX 100
005 static const int INFTY = (1<<21);
006 int G[MAX][MAX], n;
007
008 int prim(){
009 int P[MAX], D[MAX];
010 bool V[MAX];
011 REP(i, n) { D[i] = INFTY; V[i] = false;}
012 D[0] = 0;
013 P[0] = -1;
014 int cost = 0;
015 while(1){
016 int u;
017 int minv = INFTY;
018 REP(i, n) if ( !V[i] && D[i] < minv ){
019 minv = D[i]; u = i;
020 }
021 if ( minv == INFTY ) break;
022 V[u] = true;
023 if ( P[u] != -1 ) cost += G[u][P[u]];
024
025 REP(v, n){
026 if ( G[u][v] != INFTY && !V[v] ){
027 if ( D[v] > G[u][v] ){
028 P[v] = u;
029 D[v] = G[u][v];
030 }
031 }
032 }
033 }
034 return cost;
035 }
036
037 int main(){
038 int m, s, t, c;
039 while( cin >> n >> m && n){
040 REP(i, n) REP(j, n) G[i][j] = INFTY;
041 for ( int i = 0; i < m; i++ ){
042 cin >> s >> t >> c;
043 G[s][t] = G[t][s] = c;
044 }
045 cout << prim() << endl;
046 }
047 }

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

| コメント(0) | トラックバック(0) | ↑ページトップ |




ふしぎな虫

2008.09.15 13:10  パソコン甲子園 2008

問題 パソコン甲子園2008 07

いくつかの玉のような形をした体節でつながっている不思議な虫がいます。体節は赤(r)、緑(g)、青(b)のいづれかの色をもっています。この虫が、以下の条件のもとで1秒ごとに体節の色を変えます:


  • 色が変わるのは、隣合っている色違いの2つの体節のペア 1 組のみ。

  • そのようなペアは、2 つの体節の色のどちらでもない色に同時に変わる。


この虫の色の変化を、2 秒後まですべて表したものが以下の図です。

pck200807_2.gif
出典:パソコン甲子園2008


与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい(不可能な場合は NA と出力して下さい)。

入力例
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0

出力例
5
7
1
6
NA
8
0
4


解説

状態空間における幅優先探索で解きます。
ここでは、状態を r, g, b からなる文字列(そのまま)で表します。
状態を保存するためにハッシュ法を用いるのが良いでしょうが、
STL の map を使うと実装が楽になります(速度は落ちるでしょう)。

サンプルプログラム

001 #include<iostream>
002 #include<queue>
003 #include<map>
004 using namespace std;
005 #define INFTY (1<<21)
006
007 bool isSameColor( string state ){
008 for ( int i = 1; i < state.size(); i++ ){
009 if ( state[i-1] != state[i] ) return false;
010 }
011 return true;
012 }
013
014 char getColor( char c1, char c2 ){
015 if ( c1 == 'g' ) return (c2=='r' ? 'b' : 'r');
016 else if ( c1 == 'b' ) return (c2=='r' ? 'g' : 'r');
017 else if ( c1 == 'r' ) return (c2=='b' ? 'g' : 'b');
018 }
019
020 int bfs(string s){
021 queue<string> Q;
022 map<string, bool> V;
023 map<string, int> D;
024
025 Q.push(s);
026 V[s] = true;
027 D[s] = 0;
028 string u, v;
029
030 while(!Q.empty()){
031 u = Q.front(); Q.pop();
032 if ( isSameColor(u) ) return D[u];
033 for ( int i = 1; i < u.size(); i++ ){
034 if ( u[i-1] != u[i] ){
035 v = u;
036 v[i-1] = v[i] = getColor(u[i-1], u[i]);
037 if ( !V[v] ){
038 V[v] = true;
039 D[v] = D[u] + 1;
040 Q.push(v);
041 }
042 }
043 }
044 }
045
046 return INFTY;
047 }
048
049 int main(){
050 string initial;
051 while( cin >> initial ){
052 if ( initial == "0" ) break;
053 int cost = bfs( initial );
054 if ( cost == INFTY ) cout << "NA" << endl;
055 else cout << cost << endl;
056 }
057 return 0;
058 }


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

| コメント(0) | トラックバック(0) | ↑ページトップ |




テトリス

2008.09.15 11:48  パソコン甲子園 2008

問題 パソコン甲子園2008 06

テトリスをシミュレーションして下さい。盤面の大きさは横 5 コマで、落ちてくるブロックはすべて直線状で、横向き、縦向きの2種類があり、長さは 1 から 5 までの 5 種類です(全部で10種類)。

いくつかのブロックを落としていき、全てブロックで埋まった横一列は削除され、その列の上にあったブロックたちはそのままの形で下へ落ちます。最後に残るブロックのコマ数を求めて下さい。

pck200806_1.gif

pck200806_2.gif
出典(パソコン甲子園2008)


入力例
4
1 4 1
1 3 1
2 2 4
2 3 5
0

出力例
2


解説

2次元配列で盤面を表現することもできますが、ここでは整数型の1次元配列(stack)で盤面を表します。
stack[i] には盤面の下から i 行目のブロック片の状態を記録します。各行のブロック片の状態を整数で表すために、ブロック片の並びをビットとみなします。ブロック片がある状態を 1 ない状態を 0 とします。例えば、ある行のブロック片

■□■■□



10110(2進数)

と表されるので、22(10進数)となります。

例えば、盤面が

5□□□■□
4□□□■□
3■□■■■
2■■■□□
1■□■■□

の状態ならば、スタックの中身は

stack = {22, 28, 23, 2, 2}

となります。

このstackに、同様に整数で表されたブロックを落としていきます。
例えば、上記の盤面にブロック

■■■□□

を落とすと

5□□□■□
4■■■■□
3■□■■■
2■■■□□
1■□■■□

となります。
ここで、ブロックが置かれる位置は、ブロックを上から落としたときに、すでにあるブロック片にひっかかる直前の位置です。
この位置は、stack の頂点から下に向かってブロックの値とスタックの値の論理積をとり、論理積が0とならない直前の位置となります。

例えば、今落したブロック
■■■□□
と、stack[5] のブロック片
□□□■□
との論理積(28 & 2)は 0 となるので、すり抜けます。

例えば、ブロック
■■■□□
と、stack[3] のブロック片
■□■■■
との論理積(23 & 2)は 0 とはならないので、このブロック片の上にブロックが置かれます。

ブロックを置いた後に、ブロック片が5つ並んでいる場所、つまり stack の要素が 31 の場所を消していきます。

便宜上、stack[0] を 31 とします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 5000
004
005 class Tetoris{
006 public:
007 int stack[MAX+1], top;
008 Tetoris(){ stack[0] = 31; top = 0; }
009
010 void insert( int o, int p, int q ){
011 int value = (o == 1 ? (((2 << p-1)-1) << (q-1)) : (1 << (q-1)));
012 int target = getTarget( value );
013 for ( int i = target; i < target + ((o == 2) ? p : 1); i++ ){
014 if ( i > top ){
015 stack[i] = value;
016 top = i;
017 } else {
018 stack[i] += value;
019 }
020 }
021
022 while( erase());
023 }
024
025 bool erase(){
026 for ( int i = 1; i <= top; i++ ){
027 if ( stack[i] == 31 ){
028 for ( int j = i+1; j <= top; j++ ) stack[j-1] = stack[j];
029 top--; return true;
030 }
031 }
032 return false;
033 }
034
035 int getResult(){
036 int sum = 0;
037 for ( int i = top; i >= 1; i-- ){
038 int val = stack[i];
039 while( val ){
040 if ( val%2 ) sum++;
041 val /= 2;
042 }
043 }
044 return sum;
045 }
046
047 int getTarget( int value ){
048 int target = top;
049 while( (stack[target] & value) == 0 ) target--;
050 return target + 1;
051 }
052 };
053
054 int main(){
055 int n, o, p, q;
056 while( cin >> n && n ){
057 Tetoris tetoris;
058 for ( int i = 0; i < n; i++ ) {
059 cin >> o >> p >> q;
060 tetoris.insert(o, p, q);
061 }
062 cout << tetoris.getResult() << endl;
063 }
064 return 0;
065 }




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

| コメント(2) | トラックバック(0) | ↑ページトップ |