Hatena::ブログ(Diary)

kitayuta.inspect

2012/03/16

第11回日本情報オリンピック本選に行ってきました

今更感がありますが書いていたので公開します。

100 + 100 + 100 + 100 + 10 の 410点(/500点) で銅賞でした。やったねたえちゃん

問題の解法

本選で出題された問題はここにあります。

その自分の解法を書いておきます。ちなみにソースコードは回収を忘れて消滅しました。ざんねん。

1 JJOOII(JJOOII)

見た瞬間、kについてパパッと二分探索して、オワリッ!とか思って即実装し、当然のごとく入力例で落ちて20分くらい無駄にするとかいうことをやっていて悲しみを感じました。こういうの意図的になくさないといけないですね。

圧縮ぽいことをすると簡潔に解けるようですが、愚直に前からカウンタを加算したり現在のモードを切り替えたりなどしつつ処理していきました。アルゴリズムというほどのものでもないので詳細は省略します。

2 たのしいカードゲーム (Card Game is Fun)

見た瞬間はDPかなーと思いましたが(DP解もあるようです)、普通に解けました。

ブルーノk枚目から山を作っていく時、このカードの並びをB_kとします。この時、得点の最大値はアンナの持っているカードに部分列として含まれるB_kの接頭辞のうち最長のものの長さで、これは難しそうに見えますが貪欲に先頭から処理していくことで¥mathcal{O}(A)で計算できます。

k1からBまでを動くので、計算量のオーダーは全体で¥mathcal{O}(AB)で、これが満点解法です。

3 夜店 (Night Market)

y_1からy_kまでを花火の前に、y_{k+1}からy_Nまでを花火の後に遊ぶ夜店の候補とすると、このときの楽しさの最大値はナップザック問題を解くことで得られます。

これをkの値を1からN-1まで変化させて愚直に解こうとするとO(N^{2}T)となって部分点しか取れませんが、y_1からy_kまでの楽しさの最大値、y_{k+1}からy_Nまでの楽しさの最大値は、それぞれ左から、右からナップザック問題を一回解くだけで全てのkに対して求まります。なので、これらを全て求めた後kを動かして足し算の最大値を求めると答えが¥mathcal{O}(NT)で得られます。これで満点解法です。

4 釘 (Nails)

id:kyuridenamida に釘を打ち込む問題らしいです。

この問題でぼくと同じ解法をしている人が見当たらないので詳しめに説明します。

与えられる輪ゴムそれぞれに対し、輪ゴムを掛ける正三角形の一番上に来る頂点に、この輪ゴムが一番上から数えて(つまり絶対的な位置で)何段目までカバーするかを記録しておきます。

この処理の後、全ての釘に対して自分に輪ゴムが掛かっているかを判定します。この時、ある釘をカバーしている正三角形の上に来る頂点の候補は何個かに絞られます。下の図だと、黒丸が調べる対象の点で、赤線で囲まれた点が頂点の候補です。

f:id:kita_yuta:20120215220718j:image

この点の情報は配列に入れるために直角三角形状に整形していて、この時さっきの黒丸および赤線は下図のようになります。

f:id:kita_yuta:20120215220759j:image

この赤線内に含まれる頂点のうち、何段目までカバーするかの最大値が黒丸の段以上であれば黒丸には輪ゴムがかかっているはずなので、次の問題は赤線に含まれる要素のうち最大のものを求めることです。

これを愚直に計算すると¥mathcal{O}(N^4)で点数が取れませんが、全ての点に対して順番に最大値を求めていくので、これは動的計画法で計算することができます。¥mathcal{O}(N^2)で、これで満点解法です。動的計画法に気づかなくても二次元のセグメントツリーを実装することで¥mathcal{O}(N^{2}(¥log N)^{2})で計算できますが、明らかに実装が重くなるでしょう。

5 JOI 国のお祭り事情 (Festivals in JOI Kingdom)

10点解法でした。秋葉さんのスライド¥mathcal{O}(QM¥log N)アルゴリズムと全く同じなので自分の解法は省略します。満点解法はLCA(最近共通祖先)を使用しますが、これを求めるアルゴリズムを数日前に知ったのに使えなくて残念でした。

10点解法ではDijkstraを改造して使いましたが、個人的にこういう既存のアルゴリズムを改造するような問題は好きです。

2011/12/20

Excel(VBAなし)で情報オリンピック予選問題(Brainf*ckもあるよ)

(この記事はCompetitive Programming Advent Calendarの20日目の記事として書かれたものです。)

今年の情報オリンピック予選に参加された方なら知っていらっしゃると思いますが、競技規則が今年から変わり、Excelなどの表計算ソフトが使用可能になりました。ならExcel使って解くっきゃないでしょ、と思うのは私に限ったことではないと思います。さすがに予選をそれで通過することができるとは(時間的な問題で)思いませんでしたし、またExcelだけ使って解くのは許されるのかというのは微妙な感じなので、予選後にやってみました(ちなみに予選本番はC++で解きました)。予選問題一覧はこちら。解いていない方はぜひやってみてください。問題の解説は23日頃に出るそうです。

とりあえず予選通過出来ればいいんじゃない?ということで、おそらく4問完答すれば予選通過のボーダーは超えると思い、1,2,3,4番だけを解きました。本当は5,6番もやりたかったのですが、それなりに大変そうで時間もなかったので許してください。さすがにこれだけだとボリュームが足りないので、Brainf*ckインタープリタも書いてみました。

VBAを使ったらVBを使ったのと大体同じになり面白くないので、VBAは一切使っていません

問題1 ランチ (Lunch)

問題文はこちらです。

Excelによる解答はこちらです。

ただ単純に最小値をいろいろすればいいだけです。MIN関数を使ったりするとできます。

入力をInputの下に貼り付けるとOutputの下に結果が現れます。他の問題も同様です。

f:id:kita_yuta:20111220214538p:image

問題2 サッカー (Soccer)

問題文はこちらです。

Excelによる解答はこちらです。

問題文の通り点数を計算して、それぞれのチームの順位を求めれば終わりです。

入力は空白で区切られているのでそれを4つの数値にパースしなければならず、標準の関数ではうまい方法がなくなかなか大変でした。また、スコアの計算式も長ったらしいものになっています。順位の計算についてはRANK関数を使うと簡潔に書けました(手抜き感…)。

Ai,Bi,Ci,Diの部分がパースした4つの数値で、Awin,Bwin,evenはそのゲームの結果、ForAi,ForBi,ForCi,ForDiは入力処理用のデータ、Scoreはそれぞれのチームのスコアです。

f:id:kita_yuta:20111220214539p:image

問題3 最高のピザ (Best Pizza)

問題文はこちらです。

Excelによる解答はこちらです。

トッピングをk種類載せた時の最大の1ドルあたりカロリーは、トッピングをカロリーの高い順にk種類取ることにより達成でき、kを0からNまで動かした時の最大のものが答えになります。トッピングをカロリーの高い順に取るためにはトッピングをソートしておくのがよいでしょう。

ソートの処理をどうするかが一番悩みました。挿入ソートなどを実装することもおそらくできますが、値が指定範囲の中で何番目に大きいかを求めるLARGE関数を使えば楽に実装できました。あとはそこまで煩雑ではありませんでした。

Sortedはトッピングをソートしたもの、Calsはトッピングをk種類取った時の1ドルあたりカロリーを表します。

f:id:kita_yuta:20111220221656p:image

問題4 パスタ (Pasta)

問題文はこちらです。

Excelによる解答はこちらです。

i-1日目,i日目に特定のパスタを食べるときの、i日目までのパスタの食べ方の場合の数を動的計画法で求めることにより解くことができます。

動的計画法は表を埋めていく作業のようなものだから、Excelとは比較的親和度が高そうに思えます。実際、漸化式を普通にプログラミングする場合より単純にしてやる必要がありましたが、自然な感じに書けました。

Pastaはk日目に食べることになっているパスタの種類(未定の場合は0とする)を表し、その左の表で動的計画法を実行しています。

f:id:kita_yuta:20111220223210p:image


問題1から4までを予選における入力データでテストしてみたところ、C++で書いたものと全て一致しました。めでたしめでたし。

Brainf*ckインタープリタ

Excelによる実装はこちらです(少々動作が重いです)。

Brainf*ckインタープリタです。コード長は1000B、メモリ数は100、ステップ数は2048までです(改造すれば増やせます)。ステップ数を稼ぐのには、Excelシート自体を大きくしなくても、シートStepsの「(Copy→)」のところに2051行目の値をコピーしてやることで可能です。試していませんが循環参照を使ってがんばることもできるかもしれません。コードから脱出するか、EOFになってからさらに読み込もうとするかのどちらかで停止します。

シートMainは入出力用のフロントエンドです。Code部にBrainf*ckのコード(><+-.,[]以外が入っていても問題ありません)、Input部に入力を入れます。2048ステップ以内に終了するとSuccessfully finishedとなりOutputに出力がなされますが、終了していない場合Not finished yetが表示され出力はまだされません。その場合は上記のようにステップ数を稼いでください。

はろーわーるど!

f:id:kita_yuta:20111221021055p:image

シートCodeProcはコードの整形およびカッコの対応づけをしています。Useの横にあるのがBrainf*ckで使用可能な文字群で、下では0から255にかけて順に、そのASCIIコードに対応する文字が><+-.,[]以外である場合にその文字をSUBSTITUTE関数で取り除いていき、その成果である整形されたコードが左上のCodeに入ります。Stackはカッコの対応付けをする際の[の位置を積むスタックで、[がくると要素がpushされ、]がくると要素がpopされます。Stackの横の各列でカッコの対応付けのための他の処理をしています。ちなみにF列とH列は同じ内容になっていますが、これは後で[の位置から]を、]の位置から[を検索するという二種類の検索をしなければならず、どちらにもVLOOKUP関数を使えるようにするためです。

f:id:kita_yuta:20111221021056p:image

シートStepsではBrainf*ckのコードを上から下へ1ステップずつ実行していきます。atはコードの中でどの位置にいるかを示し、ptrはポインタで、Inputはそのステップ時点での残りのInput、Outputはそのステップ時点ですでに出力されているOutputです。その右に1から100まで並んでいるのは100個のメモリを表します。それぞれのセルで前の状態から現在の状態を計算していっています。

f:id:kita_yuta:20111221021057p:image

実用的なプログラミングExcelが足りてない点

  • 計算した結果を破棄できないのが辛いです。変数への再代入もできないし(循環参照使えばいいようには思いますが、邪道感がしますし、仕様で32768回しかループ回せないらしいです)、ガーベジコレクションもない。
  • 複数個の値の計算をするためには計算式をコピーしなければならず、あまりエレガントでないと思います。
  • 一つのセルには一つのデータしか保存できず(カンマでつないだりする方法はあるが)、また自分以外のセルに値を代入したりすることができない(つまり副作用がない)ので、ある処理をするためにはそれぞれのセルで独立に処理しなくてはならず非効率です。
  • 複数の異なる計算式の内部で同じ処理をするのにコピーしなければならなかったりするのは面倒なので、関数を作成する関数とかが欲しいです。
  • こんなことやりたいなら素直にVBA使えって話があるし、あまり便利になりすぎてもEsolang感が減ってしまうのでまあこれはこれでいいのかもしれないですね。
  • 実はこれらのことは半分くらい下の東京大学の先生の論文(?)でも言及されています。

あとがきのような

2011/10/03

Google Code Jam Japan 予選

id:tozangezanに勝ったかなーと思ってたらC-largeが落ちてしまったので人権がない。このままだとTシャツ危うい。

41pt,1:59:50,165位だった。一応通った。

A カードシャッフル

最初に解いた。AOJ0513と同じ解法で解こうとする(こういう人は多かったんじゃないだろうか)。最初に[1,M]という区間を持っておいて、カードがカットされるたびに適当に分割していく。ゴリゴリ実装。つらい。40分くらいかかってしまった。

//include等省略
int main(){
    int T;
    scanf("%d",&T);
    for(int ix=1;ix<=T;ix++){
        int M,C,W;
        scanf("%d%d%d",&M,&C,&W);
        vector<pair<int,int> > pas;
        pas.push_back(make_pair(1,M));
        for(int i=0;i<C;i++){
            int A,B;
            scanf("%d%d",&A,&B);
            B=A+B-1;
            vector<int> sumfir(pas.size()),sumend(pas.size());
            sumfir[0]=1;
            for(int j=1;j<sumfir.size();j++){
                sumfir[j]=sumfir[j-1]+(pas[j-1].second-pas[j-1].first+1);
            }
            sumend[0]=pas[0].second-pas[0].first+1;
            for(int j=1;j<sumfir.size();j++){
                sumend[j]=sumend[j-1]+(pas[j].second-pas[j].first+1);
            }
            int atA,atB;
            for(int i=0;i<pas.size();i++){
                if(sumfir[i]<=A&&A<=sumend[i]){
                    atA=i;
                }
                if(sumfir[i]<=B&&B<=sumend[i]){
                    atB=i;
                }
            }
            vector<pair<int,int> > now;
            if(atA==atB){
                now.push_back(make_pair(pas[atA].first+(A-sumfir[atA]),pas[atA].first+(B-sumfir[atA])));
            }else{
                now.push_back(make_pair(pas[atA].first+(A-sumfir[atA]),pas[atA].second));
                for(int i=atA+1;i<atB;i++){
                    now.push_back(pas[i]);
                }
                now.push_back(make_pair(pas[atB].first,pas[atB].first+(B-sumfir[atB])));
            }
            for(int i=0;i<atA;i++){
                now.push_back(pas[i]);
            }
            if(sumfir[atA]!=A) now.push_back(make_pair(pas[atA].first,pas[atA].first+(A-sumfir[atA]-1)));
            if(sumend[atB]!=B) now.push_back(make_pair(pas[atB].first+(B-sumfir[atB]+1),pas[atB].second));
            for(int i=atB+1;i<pas.size();i++){
                now.push_back(pas[i]);
            }
            pas=now;
        }
        int su=0;
        for(int i=0;i<pas.size();i++){
            su+=pas[i].second-pas[i].first+1;
            if(W<=su){
                printf("Case #%d: %d\n",ix,pas[i].second-(su-W));
                break;
            }
        }
    }
}

実はもっと頭の良い解法があって(競技終わってから知った)、カットの操作の逆を後ろから順に行うことを考えればよい。実装はずっと楽になる。

//include等省略
int main(){
    int T;
    scanf("%d",&T);
    for(int ix=1;ix<=T;ix++){
        int M,C,W;
        scanf("%d%d%d",&M,&C,&W);
        vector<int> as(C),bs(C);
        for(int i=0;i<C;i++){
            scanf("%d%d",&as[i],&bs[i]);
        }
        int now=W;
        for(int i=C-1;i>=0;i--){
            if(now<=bs[i]){
                now=as[i]+now-1;
            }else if(now<=bs[i]+as[i]-1){
                now-=bs[i];
            }
        }
        printf("Case #%d: %d\n",ix,now);
    }
}

B 最高のコーヒー

1日目の方から飲むコーヒーを決定していくのではなく、K日目の方から飲むコーヒーを決定することを考える。貪欲法で解くことができる。こっちも区間っぽいものを扱うので慎重に実装しなくてはならないけどそれほど大変でもなかった。priority_queueを使ってなかったりするので少し頭が悪い。

逆から貪欲が思いついたのは自分にしては頭いいなーと思った。運が良かっただけなような気もする。

ところでAとBは区間ゲー/逆からゲーでなんか被ってる感がある。


int main(){
    int T;
    scanf("%d",&T);
    for(int ix=1;ix<=T;ix++){
        int N;
        ll K;
        scanf("%d%lld",&N,&K);
        set<ll> kuk;
        vector<ll> cs(N),ts(N),ss(N);
        for(int i=0;i<N;i++){
            ll c,t,s;
            scanf("%lld%lld%lld",&c,&t,&s);
            kuk.insert(t);
            cs[i]=c;
            ts[i]=t;
            ss[i]=s;
        }
        vector<ll> kukan;
        kukan.push_back(0);
        for(set<ll>::iterator it=kuk.begin();it!=kuk.end();it++){
            kukan.push_back(*it);
        }
        ll ret=0;
        for(int i=kukan.size()-1;i>=1;i--){
            vector<pair<ll,ll> > lar;
            for(int j=0;j<ts.size();j++){
                if(ts[j]>=kukan[i]){
                    lar.push_back(make_pair(ss[j],j));
                }
            }
            sort(ALL(lar),greater<pair<ll,ll> >());
            ll rem=kukan[i]-kukan[i-1];
            for(int j=0;j<lar.size();j++){
                if(rem>0){
                    ll ncoff=min(rem,cs[lar[j].second]);
                    ret+=ncoff*ss[lar[j].second];
                    cs[lar[j].second]-=ncoff;
                    rem-=ncoff;
                }
            }
        }
        printf("Case #%d: %lld\n",ix,ret);
    }
}

ちなみに逆からじゃなく前からの貪欲でも解けるらしい。

C ビット数

一番時間がかかった。たぶんこの問題に90分くらい掛けている。

11...11というビットパターンになる数のうち、N以下で最大の物をlarとすると、f(lar)+f(N-lar)が最大のf(a)+f(b)となる。

証明(もどき):

例えば、larとN-larをビット列で表すと
lar   -> 1111111111
N-lar -> 0100101101
のようになる。ここで、(a,b)の候補となるのは、(larのビットのうちいくつかを除いたもの,
そのビットをN-larに足しあわせたもの) の全体である。
しかし、例えば上のlarの下から5番目のものをlarから除き、それをN-larに足しあわせたものは
lar'   -> 1111101111
N-lar' -> 0100111101
となり、f(a)+f(b)の値は変わらない。また、一番下のビットについてこの操作を行ったときには
lar''   -> 1111111110
N-lar'' -> 0100101110
となってf(a)+f(b)の値は減少してしまう。
このように、どのビットに対してこの操作を行ってもf(a)+f(b)は増加しない(要出典)ので、f(lar)+f(N-lar)が最大となる。

実際は競技中はこの解法を思いついて合ってる気がして、そしてsmallが通ったので証明はあまり考えなかった。

しかし、largeは__builtin_popcount()をlong long intに対して使っていたので、オーバーフローして不正解だった。__builtin_popcountll()というのがあるらしいので、それを使うと正解した(競技後に)。

正解するコードは

//include等省略

int main(){
    int T;
    scanf("%d",&T);
    for(int ix=1;ix<=T;ix++){
        ll N;
        scanf("%lld",&N);
        int lar;
        for(int i=0;i<63;i++){
            if(N>=((ll)1<<i)-1) lar=i;
        }
        printf("Case #%d: %d\n",ix,lar+__builtin_popcountll(N-(((ll)1<<lar)-1)));
    }
}

2011/02/18

JOI本選

JOI(日本情報オリンピック)の本選に参加してきました。参加記を書きます。文章力ないのでほとんど箇条書きでいきます。グダグダです。

まずは結果

20 + 0 + 0 + 0 + 6 = 26 でBランク。つまり落ちました。

できごと

零日目
  • SRMなんてなかったんや。
一日目
二日目午前
  • 寝る→起きる→飯
  • 競技開始
競技中
  • 1番はTKC(Top Kaisei Coder:うちの学校の部で行ったコンテスト)の問題と同じだった。運がいい。これは解法知らなかったら満点は取れていなかったかもしれない。とりあえずTKCの問題を作ったid:tozangezanに感謝。
  • 三十分くらいしてからジャッジにかけてAC
  • 2,3,4,5ととりあえず問題文を見る
  • 2は見て無理そうな気がした
  • 3はダイクストラとか使うのかなーという気がしたけどなんか難しそうだし流す
  • 4も思いつかない
  • 5を見て解けそうな気がしてくる。
  • 十分くらい(?)考えてGreedyな部分点解法を思いつく。その解法を改善してオーダーを下げられないかを数十分考える。
  • この時点で多分90分以上過ぎている。
  • 埒が開かないのでとりあえず4を見る。x成分とy成分は独立なことに気付いて解けそうな気がしてくる
  • なぜか二分探索を書き始める。混沌としている。実は二分探索なんかしなくても解けたし、ぼくが考えた解法は部分点解法だった。
  • 一応出来た気がするけどバグがあるので直そうとするが直らない。
  • とりあえず5の部分点解法を実装する。ジャッジに掛けたらAC
  • すでに終了まで一時間を切っている
  • 2,3を軽く読み直した気がする
  • 4のデバッグなのかどうかよく分からない作業を続ける。
  • 終了。
二日目午後
  • 終わったなー、と思いながら飯を食う。エビチリ。辛い
  • 問題解説はじまる
  • QBさんが大活躍
  • iwiwiさんが蟻本の宣伝をする。いい時代らしい。
  • iwiwiさんに蟻本にサインしてもらう http://movapic.com/kitayuta/pic/3325618
  • OBの人とかと話す。平均レーティングがやばそうだった。

感想・反省

  • くやしいです!!!
  • 全体的に考えていて楽しい問題が多かったと思う。
  • 4時間ちゃんと集中できたしそれはよかった。
  • 3ができなかったのがアホすぎる
  • 分からない問題を粘るのは大切だけどそれは試験中にやるものではない。
  • 毎度のことだが、一回思い込んでしまうとそれ以外の解法とかを思いつかなくなるのはよくない。
  • もっとこういう試験的なもの(プログラミングコンテストに限らず)に慣れないといけない。
  • そして問題が解き足りない。

これから

  • 問題を解こう。まだ量が足りない。
  • 今回の結果は割とひどかったけど、競技プログラミングの楽しさを再確認した。モチベーションが湧いてきた。
  • 解説きいてたらこのくらいの問題だったらちゃんと解けそうな気がした。根拠はないけど。
  • 来年は合宿に行って日本代表になります。
  • まずはとりあえず早くDiv1に上がって黄コーダーを目指そう(TopCoderのはなし)

なんかアドバイスとかあったらください!問題解けとかでもいいです。

おまけ

準急伝説 http://togetter.com/li/101707

2011/02/15

人材募集企画を解いた

http://okajima.air-nifty.com/b/2011/01/2011-ffac.html を解きました。締切りが過ぎたようなので一応上げておきます。社会人ではないので公式に応募はしていません。

問題1

与えられた関数がどのような働きをするか考える問題。実際に計算させてみた。

整数を超えない最大の2の累乗数(こんな単語あるのか?)だと思う。自分より下のビットを埋めている感じ。

問題

ぷよぷよ連鎖の過程を出力していく問題。実装するだけだが大変。かかった時間は、書くのに30分程度、デバッグなどに30分強。だめぽ。

読み込みの処理がちょっとアレだが気にしない。

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
using namespace std;
vector<string> puyos;
int w,h;
int ve[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void umel(int y,int x,char se){
    puyos[y][x]='S';
    for(int i=0;i<4;i++){
        int ny=y+ve[i][0],nx=x+ve[i][1];
        if(0<=nx && nx<w && 0<=ny && ny<h && puyos[ny][nx]==se){
            umel(ny,nx,se);
        }
    }
}
int main(){
    char t[10];
    while(scanf("%[ A-Z]\n",t)!=-1){
        puyos.push_back(string(t));
    }
    h=puyos.size();
    w=puyos[0].size();
    for(int y=0;y<h;y++){
        printf("%s\n",puyos[y].c_str());
    }
    printf("\n");
    for(int ix=1;;ix++){
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                char nowc=puyos[i][j];
                if(nowc!=' '){
                    umel(i,j,nowc);
                    int num=0;
                    for(int ky=0;ky<h;ky++){
                        for(int kx=0;kx<w;kx++){
                            if(puyos[ky][kx]=='S')num++;
                        }
                    }
                    if(num>=4){
                        for(int ky=0;ky<h;ky++){
                            for(int kx=0;kx<w;kx++){
                                if(puyos[ky][kx]=='S')puyos[ky][kx]=' ';
                            }
                        }
                        vector<vector<char> > tates(w);
                        for(int ky=h-1;ky>=0;ky--){
                            for(int kx=0;kx<w;kx++){
                                if(puyos[ky][kx]!=' ') tates[kx].push_back(puyos[ky][kx]);
                            }
                        }
                        for(int ky=0;ky<h;ky++){
                            for(int kx=0;kx<w;kx++){
                                puyos[ky][kx]=' ';
                            }
                        }
                        for(int kx=0;kx<w;kx++){
                            for(int ky=0;ky<tates[kx].size();ky++){
                                puyos[h-ky-1][kx]=tates[kx][ky];
                            }
                        }
                        goto EXIT;
                    }else{
                        for(int ky=0;ky<h;ky++){
                            for(int kx=0;kx<w;kx++){
                                if(puyos[ky][kx]=='S')puyos[ky][kx]=nowc;
                            }
                        }
                    }
                }
            }
        }
EXIT:   ;
        bool isera=false;
        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                if(puyos[y][x]!=' ')isera=true;
            }
        }
        if(!isera)break;
        for(int y=0;y<h;y++){
            printf("%s\n",puyos[y].c_str());
        }
    }
}

似た問題がhttp://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2206&lang=jpにあります。