kojingharangの日記

GCJ12 Round1A

02:01 |

間に合わなかったのでpracticeで。

ツイートする

A.Password Problem

02:01 |

• B文字のパスワードをA文字まで打った。i番目の文字が正しく打てている確率はp[i]。以後正しい文字を打てるとして、0〜A文字削除して残りを打つ、あきらめてenterを押して再度全部打つという選択肢がある。残り打鍵数の期待値が一番低いものを計算する問題。

• げげ、ぱっと見て確率DPみたいな感じ？と思ったけど、i番目の文字まで戻ったときに全部合ってる確率だけ分かればよいことが分かった。

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int A, B;
		cin>>A>>B;
		
		double ans = 100000000;
		double co = 1.0;
		
		REP(i, A+1) {
			// co is prod[0, i)
			int bs = A-i;
			double p = (bs*2+B-A+1)*co+(bs*2+B-A+1+B+1)*(1-co);
//			cout<<bs<<" "<<p<<endl;
			ans=min(ans, p);
			if(i<A) {
				double in;
				cin>>in;
				co *= in;
			}
		}
		ans=min(ans, B+2.0); // enter right away
		cout<<"Case #"<<ttt+1<<": "<<setprecision(10)<<ans<<endl;
	}
	return 0;
}

ツイートする

B. Kingdom Rush

02:01 |

• レベルNまでの面があって各面を星１or２でクリアすることができる。各面に対して星１or２でクリアするに当たって必要な所持星数がきまってる。全面を星２でクリアするには最低何回クリアすればいいか。

• 星２の必要星数が少ない順にクリアする。その際、所持星数が足りない場合は星１をクリアすることになる
• 当初、星１の必要星数が少ない順でいいかと思ってたけどsmall通らず。
• しばらくやってわからないのでギブアップして解説をみると、条件を満たす星１の中で星２の必要星数が多い順にクリアするといいらしい
• 例えば (0 1) (0 3) のとき、面１星１→面１星２ではダメで面２星１→面１星２→面２星２でクリアする必要がある

• 想定アルゴリズムが間違ってるっぽい時は、手動で反例を探すか全探索での答えと一致するかチェックしないといけないな...

int f(int N, vector<PII>& a, vector<PII>& b) {
	VI lvl(N);
//	sort(ALL(a));
	sort(ALL(b));
	int cur=0;
	int ok=1;
	int ans=0;
	REP(i, N) {
		REP(ai, N) {
			if(cur >= b[i].first) break;
			// find appropriate star1
			int idx=-1, maxb=-1;
			REP(j, N) {
				if(cur >= a[j].first && lvl[j]==0 && maxb < a[j].second) {
					idx=j;
					maxb = a[j].second;
				}
			}
			if(idx!=-1) {
				cur++;
				lvl[idx]=1;
//				cout<<"use 1 in "<<a[ai].first<<" "<<b[i].first<<endl;
				ans++;
			} else break;
		}
		if(cur < b[i].first) { ok=0; break; }
		cur+=lvl[b[i].second]==1 ? 1 : 2;
		lvl[b[i].second]=2;
	}
	return ok?N+ans:-1;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		vector<PII> a(N), b(N);
		REP(i, N) {
			cin>>a[i].first>>b[i].first;
			a[i].second = b[i].first;
			b[i].second=i;
		}
		int F = f(N, a, b);
//		int Ref = ref(N, a, b);
//		if(F!=Ref) {
//			cout<<"DIFF Case #"<<ttt+1<<" "<<F<<" "<<Ref<<endl;
//		}
		if(F!=-1) cout<<"Case #"<<ttt+1<<": "<<F<<endl;
		else cout<<"Case #"<<ttt+1<<": Too Bad"<<endl;
	}
	return 0;
}

ツイートする