読者です 読者をやめる 読者になる 読者になる

Croc Champ 2013 - Round 2 (Div. 2 Edition)

Div2だけど1位とれて嬉しい(小並感)
Div2E本番中に通せたの初めてな気が。mathのおかげ

A. やるだけ __gcd()使おう

int n;
int a[100010];
int g;

int main(){
    cin >> n;
    rep(i, n){
	cin >> a[i];
	if(!i) g = a[i];
	else g = __gcd(g, a[i]);
    }
    rep(i, n){
	if(g % a[i] == 0){
	    cout << a[i] << endl;
	    return 0;
	}
    }
    cout << "-1" << endl;
    return 0;
}

B. 連続したものを数える

int n, k;
string s;
vector<int> inv;

int main(){
    cin >> n >> k >> s;
    int crt = 0;
    rep(i, n){
	if(s[i] == '.'){
	    if(crt) inv.pb(crt);
	    crt = 0;
	}else{
	    crt++;
	}
    }
    if(crt) inv.pb(crt);
    rep(i, inv.size()){
	if(inv[i] >= k){
	    cout << "NO" << endl;
	    return 0;
	}
    }
    cout << "YES" << endl;
    return 0;
}

C.
自分 相手
1 1
1 0
0 1
0 0
となる所がこの順に有効なのでgreedyする

int n;
string s, t;
int a, b, c;
int p, q, now;

string win(){
    if(p > q) return "First";
    else if(p < q) return "Second";
    else return "Draw";
}

int main(){
    cin >> n >> s >> t;
    rep(i, n * 2){
	if(s[i] == '1' && t[i] == '1') ++a;
	else if(s[i] == '1' && t[i] == '0') ++b;
	else if(s[i] == '0' && t[i] == '1') ++c;
    }
    p = (a + 1) / 2;
    q = a - p;
    now = a;
    if(now & 1){
	if(c){
	    --c;
	    ++q;
	    ++now;
	}
	else if(b){
	    --b;
	    ++now;
	}else{
	    cout << win() << endl;
	    return 0;
	}
    }
    while(now < n * 2){
	rep(i, 2){
	    if(i == 0){
		if(b){
		    --b;
		    ++p;
		    ++now;
		}
		else if(c){
		    --c;
		    ++now;
		}else{
		    cout << win() << endl;
		    return 0;
		}
	    }else{
		if(c){
		    --c;
		    ++q;
		    ++now;
		}
		else if(b){
		    --b;
		    ++now;
		}else{
		    cout << win() << endl;
		    return 0;
		}
	    }
	}
    }
    cout << win() << endl;
    return 0;
}

D. DP? うまくできるらしいけどわからない。

E. math
n = (a + b + c) ^ 3 - a ^ 3 - b ^ 3 - c ^ 3 = 3(a + b)(b + c)(c + a)より、
p = a + b, q = b + c, r = c + aと置けば
pqr = n / 3かつ、(p + q + r) / 2 = a + b + cよりp, q, rの組にa, b, cが一意に対応。
a, b, c > 0に注意すればp, q, rが三角形を成すことがわかる。

ll ans;
ll n;
vector<ll> vec;

void pr(){
    for(ll i = 1; i * i <= n; ++i) if(n % i == 0) vec.pb(i);
}


int main(){
    cin >> n;
    if(n % 3){
	cout << "0\n";
	return 0;
    }
    n /= 3;
    pr();
    rep(i, vec.size()){
	ll v = vec[i];
	ll d = n / v;
	for(int j = vec.size() - 1; j >= 0; --j){
	    if(d % vec[j]) continue;
	    ll p = d / vec[j];
	    if(v + vec[j] <= p) break;
	    if((v + vec[j] + p) % 2 == 0 && v + p > vec[j] && vec[j] + p > v){
		ans++;
	    }
	}
    }
    cout << ans << endl;
    return 0;
}