最近だめだこれ〜
うーん
— ボンド@競プロ (@bond_cmprog) May 31, 2020
Bondo416さんのAtCoder Beginner Contest 169での成績：2077位
パフォーマンス：1217相当
レーティング：1243→1241 (-2) :(#AtCoder https://t.co/9wJNwlJ2XK
A - Multiplication 1
を出力
提出コード
void solve(){ int a, b; cin >> a >> b; cout << a * b << endl; }
B - Multiplication 2
結構難しい
0が含まれてたら答えが0になるのに注意
それ以外は順に掛け算をしていく
オーバーフローはで判定できる
提出コード
void solve(){ int N; cin >> N; vector<ll> a(N); bool zero = false; REP(i,N){ cin >> a[i]; if(a[i] == 0) zero = true; } if(zero){ cout << 0 << endl; return; } ll ans = 1; REP(i,N){ if(ans > LINF / a[i]){ cout << -1 << endl; return; } ans *= a[i]; } cout << ans << endl; }
C - Multiplication 3
doubleやlong doubleだと誤差で落ちる（本番はlong doubleでも通ったらしい）
小数点以下2桁までしかないので、stringなどで受け取って100倍にしてかけたあと100で割って切り捨てればいい
提出コード
void solve(){ ll A; cin >> A; string b; cin >> b; ll B = 0; ll cur = 100; REP(i,b.size()){ if(b[i] == '.') continue; B += cur * (b[i] - '0'); cur /= 10; } ll ans = A * B / 100; cout << ans << endl; }
D - Div Game
素因数分解をする
各素因数を1個、2個、…と取っていくのが最適
提出コード
vector<pair<long long, long long> > prime_factorize(long long n) { vector<pair<long long, long long> > res; for (long long p = 2; p * p <= n; ++p) { if (n % p != 0) continue; int num = 0; while (n % p == 0) { ++num; n /= p; } res.push_back(make_pair(p, num));//p^num } if (n != 1) res.push_back(make_pair(n, 1)); return res; } void solve(){ ll N; cin >> N; auto res = prime_factorize(N); ll ans = 0; for(auto x : res){ int cur = 1; while(x.second > 0 && x.second >= cur){ x.second -= cur; ans++; cur++; } } cout << ans << endl; }
E - Count Median
中央値になる最大と最小の区間を求める
AとBをそれぞれソートをすると番目の最小は
となる
同様に最大はとなるので
が答え
偶数の時も殆ど同様で、が答えになる
最小と最大の間は全部作れるいつものあれ
本番はimosっぽくやってWA取れなかったけど素直にソートで良かったね…
提出コード
void solve(){ ll N; cin >> N; vector<ll> A(N), B(N); REP(i,N) cin >> A[i] >> B[i]; sort(A.begin(), A.end()); sort(B.begin(), B.end()); if(N & 1){ ll a = A[N/2]; ll b = B[N/2]; cout << b - a + 1 << endl; } else{ ll a = A[N/2-1] + A[N/2]; ll b = B[N/2-1] + B[N/2]; cout << b - a + 1 << endl; } }
F - Knapsack for All Subsets
解説AC
部分集合Tについての部分集合をUとする
とし、
を満たす
を選ぶ時には
1. UにもTにも入れる
2. Tにのみ入れる
3. UにもTにも入れない
の3通りがある
dp[i][j] := i番目を見ているときにUの和がjのときの場合の数と定義する
そうすると、Uに入れるときのみ、dp[i][j] += dp[i][j-A[i]]のように遷移し
Uに入れないときは2. と 3. の2通りあるため、dp[i+1][j] += 2 * dp[i][j]と遷移できる
using mint = Fp<MOD2>; void solve(){ int N, S; cin >> N >> S; vector<int> A(N); REP(i,N) cin >> A[i]; vector<vector<mint>> dp(N+10, vector<mint>(S+10)); dp[0][0] = 1; REP(i,N){ REP(j,S+1){ dp[i+1][j] += dp[i][j] * 2; if(j - A[i] >= 0) dp[i+1][j] += dp[i][j-A[i]]; } } cout << dp[N][S] << endl; }
