kmjp's blog

競技プログラミング参加記です

yukicoder : No.200 カードファイト!

想定解フローなの…?
http://yukicoder.me/problems/297

問題

A君はA枚のカードを持ち、それぞれの強さはB[i]である。
C君はC枚のカードを持ち、それぞれの強さはD[i]である。

2人はN回試合を行う。
試合では両者手持ちのカードを1枚場にだし、その強さを競う。
当然強いカードの方が勝つ。

場に出したカードは以後使えない。
ただし手持ちのカードがなくなると、自分のカードを回収して再度すべて使うことができるようになる。

C君がA君の望むカードを出してくれる場合、A君は最大何回勝利できるか。

解法

想定解はフローらしいが…。

自分は別解法で解いた。
基本アプローチは、A君が勝てるならギリギリ勝てる組み合わせ、どうせ勝てないならA君は弱いカード、C君は強いカードを消費するようにすればよい。

具体的には、以下の処理を試合毎に繰り返せばよい。

  • A君が勝てる場合、A君は勝てるうち最弱のカードをだし、C君はそれに負ける最強のカードを消費する。
  • どうカードを出しても勝てない場合、A君は最弱、C君は最強のカードを消費する。
int N,A,C;
vector<int> BB,DD,B,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	FOR(i,A) cin>>x, BB.push_back(x);
	cin>>C;
	FOR(i,C) cin>>x, DD.push_back(x);
	
	int ret=0;
	while(N--) {
		if(B.empty()) B=BB;
		if(D.empty()) D=DD;
		sort(B.begin(),B.end());
		sort(D.begin(),D.end());
		int win=0;
		FOR(x,B.size()) {
			for(y=D.size()-1;y>=0;y--) if(B[x]>D[y]) {
				ret++;
				win=1;
				B.erase(B.begin()+x);
				D.erase(D.begin()+y);
				break;
			}
			if(win) break;
		}
		if(!win) {
			B.erase(B.begin());
			D.erase(D.begin()+D.size()-1);
		}
	}
	
	cout<<ret<<endl;
}

まとめ

フローを思いつけと言われると★4だけど、貪欲で通るので★3でもいいかなぁ。
N,A,Cが大きいと分からないけどね。