TopCoder Open 2011 Qual 3

TopCoder

本番は参加していないのでPractice.

Result

248.06 / 445.38 / 616.35

Easy AllButOneDivisor

問題概要

n個の整数divisorsが与えられる。
これらのうち、ちょうどn-1個の倍数となっているような整数を求めよ。
複数あるときはそのうち最小のものを、存在しない場合は-1を返せ。

方針

倍数にしない整数を一つ決めて、残りの数のLCMを取る。
更にそれが、倍数にしない数で割り切れなければそれは答えの候補。


これをn通り試して最小のものを取ればよい。

ソースコード
class AllButOneDivisor {
	public:
	int getMinimum(vector <int> divisors) 
	{
		int n=divisors.size(), ans=inf;
		rep(i,n){
			int t=1,cnt=0;
			rep(j,n)if(i!=j)t=t*divisors[j]/__gcd(t,divisors[j]);
			rep(j,n)if(t%divisors[j]==0)cnt++;
			if(cnt==n-1)ans=min(ans,t);
		}
		return ans==inf?-1:ans;
	}
};

Medium CoinMachinesGame

問題概要

いくつかのゲームがあり、それぞれプレイするのにneed[i]のお金が必要。
プレイ後にはgive[i]のお金が戻ってくる。
お金をcoinsだけもっているとき、最大で何回ゲームをプレイできるか。
同じゲームを何回プレイしてもよい。


coins≦10^9

方針

1ゲーム後に実質的に消費するのはneed[i]-give[i]枚のコイン。


ゲームi,jのどちらもプレイできるとき、
need[i]-give[i]≦need[j]-give[j]ならば、ゲームjをするかわりにゲームiをしたとしても、（残ってるお金はiをプレイした場合のほうが多いので）遊べるゲームの数は減らない。
したがってneed[i]-give[i]が最小になるiからgreedyにプレイできるだけプレイするのが最適。


coinsの枚数が多いので、そのゲームで何回遊べるかは、
coinsからneed[i]を引いてから割り算することで速く計算する。

ソースコード
class CoinMachinesGame {
	public:
	int maxGames(int coins, vector <int> need, vector <int> give) 
	{
		int n=need.size(), ans=0;
		pair<int,pi> p[100];
		rep(i,n)p[i]=mp(need[i]-give[i],mp(need[i],give[i]));
		sort(p,p+n);
		
		while(1){
			int i,t;
			for(i=0;i<n;i++)if(p[i].second.first<=coins)break;
			if(i>=n)break;
			t=(coins-p[i].second.first)/p[i].first;
			coins-=t*p[i].first; ans+=t;
			//cerr<<t<<" "<<coins<<endl;
			while(coins>=p[i].second.first)ans++, coins-=p[i].first;
		}
		return ans;
	}
};

Hard AllButOneDivisor

問題概要

各成分が0または1の行列が与えられる。
この行列について

  • i行目以上の0,1を全て入れ替える
  • i行目以下の0,1を全て入れ替える
  • j列目とそれより左の0,1を全て入れ替える
  • j列目とそれより右の0,1を全て入れ替える

操作ができるとする。


この操作を好きなだけ行った後にできる、0の長方形のうち面積が最大のものの面積を求めよ。

方針

「操作」はi列目だけの0,1を反転させる、j列目だけの0,1を反転させると読み替えてよい。


ある長方形が作れるかを考える。
長方形の一列目と二列目は、全く同じか、二列目が一列目を反転させたものでなくてはならない。
一列目と三列目、四列目……についても同じ。


全ての長方形についてこれを判定して、作れるかどうかを見てやればよい。

ソースコード
class ComplementMachine2D {
	public:
	int largestSubmatrix(vector <string> matrix) 
	{
		int h=matrix.size(), w=matrix[0].size(), ans=max(h,w);
		ll bit[50]={};
		rep(i,h)rep(j,w)if(matrix[i][j]=='1')bit[i]^=1ll<<j;
		
		rep(b,h)rep(l,w)for(int r=l+1;r<w;r++){
			ll mask=(1ll<<r-l+1)-1;
			ll ptn=bit[b]>>l&mask,ptn2;
			int t=b+1;
			for(;t<h;t++){
				ptn2=bit[t]>>l&mask;
				if(ptn!=ptn2&&ptn!=(~ptn2&mask))break;
			}
			ans=max(ans,(t-b)*(r-l+1));
		}
		return ans;
	}
};