Codeforces School Personal Contest #3 (Winter Computer School 2010/11)

兼 Codeforces Beta Round #45 (ACM-ICPC Rules)

参加してきました。

結果から書くと、3完で、96位/218位(学生/全体)でした。

A→B→D→Cの順番で解いたはずだったんだけどCがWA出して、原因分からずコンテスト終了。

A. Rock-paper-scissors

効率的な実装法を考えていたら3分くらい食った。PCKであったような気するけど思いつかないし思い出せないし、ググってもすぐ見つからないのでしゃーなく全部分岐した。

結局3人ジャンケンなので意外に分岐少なく済んだので、こういうのは考えるより手を動かした方が良い。

#define P "paper"
#define G "rock"
#define C "scissors"
int main(){
    string a,b,c;
    cin >> a >> b >> c;
    if(  a==P && b == G && c == G)cout << "F";
    else if(a==G && b == P && c == G)cout << "M";
    else if(a==G && b == G && c == P)cout << "S";
    
    else if(a==G && b == C && c == C)cout << "F";
    else if(a==C && b == G && c == C)cout << "M";
    else if(a==C && b == C && c == G)cout << "S";

    else if(a==C && b == P && c == P)cout << "F";
    else if(a==P && b == C && c == P)cout << "M";
    else if(a==P && b == P && c == C)cout << "S";
    
    else cout << "?";
    
    cout << endl;
}

6min.

B. Land Lot

なんか木の生え具合が与えられる。

a*bもしくはb*aの領域欲しいけど、カットする木少なくしたい。最小でどれだけ切る必要があるか。

ループ回すだけ。普通のfor書くと絶対バグを生じさせるこの頭の悪さどうにかしたい。

結構デバグでタイムロスした。

int w,h,a,b;
int  data[50][50] = {0};

int solve(){
    int ret = (1<<21);

    for(int Y=0;Y<=h-a;Y++){
        for(int X=0;X<=h-b;X++){
            int count = 0;
            rep(y,a)rep(x,b){
                int yy = Y+y;
                int xx = X+x;
                count += data[yy][xx];
            }
            ret = min(count,ret);
        }
    }
    
    return ret;
}

int main(){

    cin >> h >> w;
    rep(i,h)rep(j,w){
        cin >> data[i][j];
    }
    cin >> a >> b;
    int ret = (1<<21);
    ret = min(solve(),ret);
    swap(a,b);
    ret = min(solve(),ret);
    cout << ret << endl;   
}

22min.

C - The Race

まず問題文を翻訳機に流し込んでもひたすら意味が分からず20分くらい経ったので、今度は英文のままちゃんと読んでいく。

意味は理解できたがどう実装すればいいんだろう・・・。→暗中模索な感じにコード書いては消して書いては消して30分くらい経つ。

机上計算してみるか→各地点到着時に0<=残量<10になるようなaを求める連立不等式か!

で、移項とかするとすごく単純な感じになることが分かる。→実装する

なぜかWA出る(原因が悲しい)→そもそも小数扱った解法の時点でダメなんじゃね!?

法則性を探そうと必死になる。→分からずコンテスト終了。

原因: 誤差っぽい。long doubleにしたら通った!

/* long doubleに 修正後ソース */
const long double EPS = 1e-12;

int sim(long double a,vector<long double>&bw){
	long double r = a;
	rep(i,bw.size()){
		r = r - bw[i] + a;
	}
	return floor(r/10.0);
}

int main(){
	int n;
	cin >> n;
	vector<int> data(n+1);
	
	data[0] = 0;
	rep(i,n)cin >> data[i+1];
	
	vector<long double> bw;
	rep(i,n)bw.push_back( (data[i+1]-data[i])*10 );
	
	long double l = 0 , h = 100000000;
	
	double t = 0;
	
	rep(i,n){
		t += bw[i];
		int a = i+1;
		l = max(l,t/a);
		h = min(h,(t+10)/a);
	}
	
	h -= EPS;
	
	if(sim(l,bw) == sim(h,bw)){
		cout << "unique" << endl;
		cout << data.back()+sim(l,bw) << endl;
	}else{
		cout << "not unique" << endl;
	}
	return 0;
}

WA

D. Permutations

問題文とサンプル出力が分からない。問題をよく読むとよく分かったので実装に取り掛かった。

『1から連続した数字を"1つずつ"含む集合をつくりたい。所属する集合の番号を出力(集合の番号は1からはじまる)。所属しない要素が出たら-1返す。』

が、少々実装に戸惑った。下手にループしまくるとTLEしそうだったのでそれをどうするか考えてた。

結局ハッシュ的な感じに番号毎に配列変数にふり分ければ効率が良いことに気づきそれを実装。

こういうのは見た瞬間に思いつくレベルじゃないときついなあ。

int main(){
    int n; cin >> n;
    
    int c = 0;
    vector<int> data(n);

    vector<int> htn[100001];
    
    rep(i,n){
        int a;
        cin >> a;
        if(a == 1)c++;
        htn[a].push_back(i);
    }
    
    int x = c;
    
    while(c){
        for(int i=1;i<=100000;i++){
            if(htn[i].size()){
                data[htn[i].back()] = c;
                htn[i].pop_back();
            }else{
                break;
            }
        }
        c--;
    }
    if(count(all(data),0)){
        cout << -1;
    }else{
        cout << x << endl;
        rep(i,n){
            if(i)cout << " ";
            cout << data[i];
        }
    }
    cout << endl;
}

43min.

Result

Solved : ooxo----

Place : 96/218(School/CF#45)

Rate : 1607 → 1566 (-41)

まあレート下がったのは妥当かなとは思いますけど、C通せたのにー。。と後悔が残る。

そもそもldouble使わないと通らないコード書くのが悪いのかなー。