R1A,R1Bオチ

今日R1AとR1B参加してきましたが二落ちでした。。。

結果 A-small A-large B-small B-large C-small C-large score
R1A    o      TL       *       *       *       *      6
R1B    o       o       *       *       *       *      20

Cは参加できないのでコレでGCJ敗退です…Japanか来年頑張ります…
今回はとりあえずR1A-AとR1B-Aを解説したいと思います。多分。

R1A-A

R1Aは全体的に例年より難しかったそうです。
で僕がなんとかsmallを通した問題がコレ。概要は以下。

今日D回ゲームをやった。そして今までに合計でG回ゲームをやっている。
結果は勝ちか負けしかなく、計算機で勝率を見ると今までの勝率Pg％と今日の勝率Pd％が奇跡的にどちらも整数だった。
今現在、DやGの値は忘れてしまったが、自分が今日の間に全部でN回ゲームが出来ることが分かっている。
このときPgやPdの値は正しいものか？それともこの計算機は壊れているか？
※G≧D、D>0、N≧D

とりあえずなんの参考にもならないけど僕のコード

int main() {
	int T; cin >> T;
	for (int t=1; t<T+1; t++) {
		int N, Pd, Pg; cin >> N >> Pd >> Pg;
		int d, g;
		bool flag=false;
		for (d=1; d<=N; d++) {
			int Wd=d*Pd;
			if (Wd%100!=0) continue;
			else break;
			for (g=100; g>d; g--) {
				int Wg=g*Pg;
				if (Wg%100!=0) continue;
				if (g-Wg/100>=d-Wd/100&&Wg/100>=Wd/100) {
					flag = true;
					break;
				} else if (g-Wg/100<d-Wd/100&&Wg/100<Wd/100){
					break;
				}
			}
			if (flag) break;
		}
		if (flag) cout << "Case #" << t << ": Possible" << endl;
		else cout << "Case #" << t << ": Broken" << endl;
	}
}

さて、僕はいわゆる全探索で奇跡的にsmallをとおしてしまったけどコレにはもっといい解法がある。今回はその方法を解説し、largeも通るコードを掲載（とある人のコード拝借m(_ _)m）しようとおもう。

まず僕はしなかったがまずありえない場合をある程度除外できる。
・Pg=0の時、Pdは0でないと定義的にありえない
・Pg=100の時、Pdは100でないと定義的にありえない
そして、ここまで場合分けした後でそれ以外について次が言える

(D×Pd) mod 100 = 0

であるから、Dが最小の時だけ考えればいい。Pdと100の最小公倍数をPdで割った値をここでDとすると(D×Pd)がPdと100の最小公倍数となりこの等式が成立する。そしてこの時のDは最小のはず(∵最小公倍数以下のPdと100の公倍数はない)
現実的にはなるべく手間は省きたいので100をPdと100の最大公約数でわって先ほどと同じDの値を求めることになる。これは最大公約数をgcdなどとしてPdと100に関する等式、そして最小公倍数との式を導けば自明であると思う。

そしてこの時このDがNより大きいとおかしいということになる。結果次のように書けばいい。

int main(){
    int T;
    scanf("%d",&T);
    for(int ix=1;ix<=T;ix++){
        long long N,PD,PG;
        scanf("%lld%lld%lld",&N,&PD,&PG);
        bool pos;
        if(PG==0){
            if(PD==0) pos=true;
            else pos=false;
        }else if(PG==100){
            if(PD!=100) pos=false;
            else pos=true;
        }else{
            if((long long)(100/__gcd((long long)100,PD))<=N) pos=true;
            else pos=false;
        }
        if(pos) printf("Case #%d: Possible\n",ix);
        else printf("Case #%d: Broken\n",ix);
    }
}

R1B-A

これは自力でとけたので他人のコードを拝借するような真似は(ry

問題の概要はコチラ

あるゲームの各チームのレート(RPI)を次のように定義した。
　RPI=0.25*WP+0.5*OWP+0.25*OOWP
この時各々の値は以下のように定める。
・WPはそのチームの全体の勝率
・OWPはあるチームをAとおくと、そのAと戦ったチームのAとの戦績を除いたWPの平均
・OOWPはそのチームと戦ったチームのOWPの平均
試合結果からRPIを計算せよ。

ほぼ読解力の問題。OWPの概念が難しい。
ともかく読解すると後は意外に単純な実装でいける。

というわけで答えは以下。

int main() {
	int T; cin >> T;
	for (int ix=1; ix<=T; ix++) {
		int N; cin >> N;
		ves sc(N);
		for (int i=0; i<N; i++)	cin >> sc[i];
		vector<double> team(N, 0.0), owp(N);
		for (int i=0; i<N; i++) {
			double won=0, game=0, awp=0.0;
			int c=0;
			for (int j=0; j<N; j++) {
				if (sc[i][j] == '1') won++;
				else if (sc[i][j] == '.') continue;
				double w=0, g=0;
				for (int k=0; k<N; k++) {
					if (k==i) continue;
					else if (sc[j][k]=='1') w++;
					else if (sc[j][k]=='.') continue;
					g++;
				}
				c++;
				awp += w/g;
				game++;
			}
			owp[i] = awp/c;
			team[i] += won/game*0.25+awp/c*0.5;
		}
		printf("Case #%d:\n",ix);
		for (int i=0; i<N; i++) {
			double aowp=0;
			int c=0;
			for (int j=0; j<N; j++) {
				if (sc[i][j]=='.') continue;
				aowp += owp[j];
				c++;
			}
			team[i] += aowp/c*0.25;
			printf("%g\n", team[i]);
		}
	}
}