11パズル

問題 パソコン甲子園2008 08

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

入力例

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;
}

白虎運送

問題 パソコン甲子園2008 12

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

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

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

解説

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

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

トラックは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 }

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

ビーカー

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

こだわり

問題 パソコン甲子園2008 09

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


出典：パソコン甲子園２００８
入力例

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

(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] の２つの部分に分けたとき、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]は以下のようになります。

	1	2	3
1	5	5	5
2	8	5	5
3	16	8	8
4	18	10	8
5	19	11	8
6	25	16	9
7	34	18	15
8	41	22	16
9	45	25	18

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


絵を準備。。。

サンプルプログラム

#include<iostream>
#include<algorithm>
using namespace std;

#define NMAX 100
#define KMAX 100
static const int INFTY = (1<<21);

// n >= k
int compute( int n, int k, int S[NMAX+1] ){

    int M[NMAX+1][KMAX+1], D[NMAX+1][KMAX+1];
    int P[NMAX+1];

    P[0] = 0;
    for ( int i = 1; i <= n; i++ ) P[i] = P[i-1] + S[i];

    for ( int i = 1; i <= n; i++ ) M[i][1] = P[i];
    for ( int j = 1; j <= k; j++ ) M[1][j] = S[1];

    for ( int i = 2; i <= n; i++ ){
        for ( int j = 2; j <= k; j++ ){
            M[i][j] = INFTY;
            for ( int x = 1; x <= i-1; x++ ){
                int maximum = max( M[x][j-1], P[i] - P[x] );
                if ( M[i][j] > maximum ){
                    M[i][j] = maximum;
                    D[i][j] = x;
                }
            }
        }
    }
    return M[n][k];
}

int main(){
    int n, k, S[NMAX+1];
    while(1){
            cin >> k >> n;
            if ( k == 0 && n == 0 ) break;
            for ( int i = 1; i <= n; i++ ) cin >> S[i];
            cout << compute(n, k, S) << endl;
    }
    return 0;
}

デブンキー一家の大活躍

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

ふしぎな虫

問題 パソコン甲子園2008 07

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

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


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

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


出典：パソコン甲子園２００８

与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい（不可能な場合は 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 }

テトリス

問題 パソコン甲子園2008 06

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

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




出典（パソコン甲子園２００８）

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

出力例
2

解説

２次元配列で盤面を表現することもできますが、ここでは整数型の１次元配列（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 とはならないので、このブロック片の上にブロックが置かれます。

ブロックを置いた後に、ブロック片が５つ並んでいる場所、つまり 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 }