Google Code Jam 2009:Round2 Problem A. Crazy Rows

行列を隣り合った行の入れ替えによって下三角行列に変形する問題。

以前他のところで見た気がする。何かの解説記事かな？
上から順番に見て、条件を満たしていない行があれば、条件を満たす一番近い行と置き換える。
これを全部の行に行えばおｋ

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define rep(i,a,b) for(int i=a;i<b;i++)

using namespace std;

int solve(int no)
{
	int N;
	cin >> N;
	
	int a[100];
	rep(i,0,N) {
		string str;
		cin >> str;
		int pos = -1;
		rep(j,0,N) {
			if(str[j]=='1') pos = j;
		}
		a[i] = pos;
	}
	
	int cnt = 0;
	rep(i,0,N) {
		int pos = -1;
		rep(j,i,N) {
			if(a[j]<=i) {
				pos = j;
				break;
			}
		}
		cnt += pos - i;
		int tmp = a[pos];
		for(int j=pos;j>i;j--) {
			a[j] = a[j-1];
		}
		a[i] = tmp;
	}
	cout << "Case #" << no << ": " << cnt << endl;
}

int main()
{
	int T;
	cin >> T;
	rep(no,0,T) {
		solve(no+1);
	}
	return 0;
}