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; }