Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-12-11SRM526 Div1(Practice)

SRM526 Div1 250 DucksAlignment

| 14:27 | SRM526 Div1 250 DucksAlignment - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM526 Div1 250 DucksAlignment - SRM diary(Sigmar) SRM526 Div1 250 DucksAlignment - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

何かえらく実装が重いような・・・

ある列かある行に寄せる必要があるので全探索する

後は歯抜けになったところを適当に詰める必要がある

これは本当に適当に詰めればいい

よほど変な実装をしなければ同じ解になるはず・・である


ソースコード

自分のポリシー的には絶対にやってはいけないレベルの冗長なコードを書いてしまった

少なくとも行と列は回転などを使って同じコードを使いまわすべきである

class DucksAlignment {
public:
	int minimumTime(vector <string> grid) {
		int res;
		int h=grid.size(), w=grid[0].size();

		int col[52]={0}, row[52]={0};
		int cnt=0;
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(grid[i][j]=='o') {
					row[i]=1; col[j]=1;
					cnt++;
				}
			}
		}

		int rinc=1000000000;
		for(int i=0; i+cnt<=h; i++) {
			int trow[52];
			memcpy(trow, row, sizeof(trow));
			int tinc=0;
			for(int j=0; j<i; j++) {
				if(row[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(trow[k]==0) {
						trow[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			for(int j=i+cnt; j<h; j++) {
				if(row[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(trow[k]==0) {
						trow[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			rinc=min(rinc, tinc);
		}

		int cinc=1000000000;
		for(int i=0; i+cnt<=w; i++) {
			int tcol[52];
			memcpy(tcol, col, sizeof(tcol));
			int tinc=0;
			for(int j=0; j<i; j++) {
				if(col[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(tcol[k]==0) {
						tcol[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			for(int j=i+cnt; j<w; j++) {
				if(col[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(tcol[k]==0) {
						tcol[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			cinc=min(cinc, tinc);
		}

		res=1000000000;
		for(int i=0; i<w; i++) {
			int tres=0;
			for(int j=0; j<h; j++) {
				for(int k=0; k<w; k++) {
					if(grid[j][k]=='o') tres+=abs(i-k);
				}
			}
			res=min(res, tres+rinc);
		}

		for(int i=0; i<h; i++) {
			int tres=0;
			for(int j=0; j<h; j++) {
				for(int k=0; k<w; k++) {
					if(grid[j][k]=='o') tres+=abs(i-j);
				}
			}
			res=min(res, tres+cinc);
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111211