kojingharangの日記

TCO Round1B 500 EllysFigurines

05:12 |

• 15x15 以内の白黒ビットマップが与えられる。１回に 1～R 行または 1～C 列分、白にできる。最小何回で全部白にできるか。

• 全然思いつかない
• dp[x][y][w][h] で [x,x+w) x [y,y+h) を白にする最小回数？とか思って書いてみる
• バグってるうちに終了
• そもそもこれはだめだ（領域を分断すると本来１回で消せても２回以上に分割されちゃうことがある）

• あとで
• 消す行たち(最大2**15 通り)を決めると黒が残ってる列が決まって、それらを左から順に消してけば回数が出る
• 気が付かなかった。。

• ↓あとで(accepted in practice room)

class EllysFigurines {
	public:
	int getMoves(vector<string> B, int R, int C) {
		int W=B[0].size();
		int H=B.size();
		int ans = 1<<30;
		REP(bit, 1<<H) {
			int lans=0;
			int rmy[20]={};
			int rest[20]={};
			REP(y, H) {
				if((bit>>y)&1) {
					lans++;
					REP(i, R) if(y+i<H) rmy[y+i]=1;
				}
				if(!rmy[y]) REP(x, W) if(B[y][x]=='X') rest[x]=1;
			}
			REP(x, W) {
				if(rest[x]) {
					lans++;
					x+=C-1;
				}
			}
			ans=min(ans, lans);
		}
		return ans;
	}
};

ツイートする

TCO Round1B 1000 EllysReversals

05:12 |

• あとで

• 最大50文字の文字列が最大50個ある。どれかの文字列の先頭の偶数文字を逆順にする作業を 0 回以上行う。
• 同じ文字列が２つ出てきたらそれらは消される。最後に残る文字列の最小個数を求める問題。

• 先頭から２文字ずつのグループに分けると、グループ内の順序とグループの順序は任意に動かせる
• （任意のグループを先頭に持ってきたり元の位置に戻したりできるので）
• ので、ある文字列について何回か作業したときにできる文字列の代表を求める（辞書順最小のものとか）
• 各文字列の代表の個数が奇数個のものだけ 1 個ずつ残るのでその和が答え。

• ↓あとで(accepted in practice room)

class EllysReversals {
	public:
	int getMin(vector <string> W) {
		int N=W.size();
		map<string, int> hi;
		REP(i, N) {
			vector<string> ww;
			REP(j, W[i].size()/2*2) {
				string ss;
				ss.PB(W[i][j]);
				ss.PB(W[i][j+1]);
				j++;
				sort(ALL(ss));
				ww.PB(ss);
			}
			sort(ALL(ww));
			string sn;
			FOR(e, ww) sn+=*e;
			if(W[i].size() & 1) sn+=W[i][W[i].size()-1];
			hi[sn]++;
		}
		cout<<hi<<endl;
		int ans = 0;
		FOR(e, hi) if(e->second & 1) ans++;
		return ans;
	}
};

ツイートする