A. Boboniu Likes to Color Balls
を使って回文を作るには全ての個数が偶数か、一つだけ奇数であればいい
できる操作を考えると、2回操作をするとその偶奇が元の状態に戻ることがわかる
したがって、操作を行わないもしくは、操作を1回やって回文を作れるかどうかを判定する
提出コード
void solve(){ ll r, g, b, w; cin >> r >> g >> b >> w; int odd = 0; if(r & 1) odd++; if(g & 1) odd++; if(b & 1) odd++; if(w & 1) odd++; if(odd <= 1){ cout << "Yes" << endl; return; } if(r > 0 && g > 0 && b > 0){ r--, g--, b--, w += 3; } odd = 0; if(r & 1) odd++; if(g & 1) odd++; if(b & 1) odd++; if(w & 1) odd++; if(odd <= 1){ cout << "Yes" << endl; } else cout << "No" << endl; }
B. Boboniu Plays Chess
こどふぉにありがちっぽいやつ
最初一回通ったマス跨げないかと思ってた
実際は跨ぐことができるので初期地点の横方向を全部埋めて端から縦方向を埋めていく
他の人のコード見たら簡潔な実装で出来るっぽくて無駄なことしてた
提出コード
void solve(){ int n, m, sx, sy; cin >> n >> m >> sx >> sy; vector<vector<bool>> used(n+1, vector<bool>(m+1)); vector<P> ans; int x = sx, y = sy; ans.emplace_back(x, y); used[x][y] = true; while(y < m){ y++; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } while(y > 1){ y--; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } int p = 0; for(;y<=m;y++){ if(y > 1) ans.emplace_back(x,y); used[x][y] = true; if(p == 0){ while(x-1 >= 1){ x--; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } while(x+1 <= n){ x++; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } } else{ while(x+1 <= n){ x++; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } while(x-1 >= 1){ x--; if(!used[x][y]) ans.emplace_back(x, y); used[x][y] = true; } } p = 1 - p; } for(auto [x, y] : ans) cout << x << " " << y << endl; }
C. Boboniu and Bit Operations
想定解が頭良かった
最初はに対してminになるを全探索してそのbitwise ORかなーって思ったけど落ちるケースがありそう
制約的にが通りそうなのでDPをする
i番目まで見たときにkが作れるかどうかでDP
提出コード
void solve(){ int n, m; cin >> n >> m; vector<int> a(n), b(m); REP(i,n) cin >> a[i]; REP(i,m) cin >> b[i]; vector<vector<bool>> dp(n+1, vector<bool>(512+10)); dp[0][0] = true; REP(i,n){ REP(j,m){ REP(k,512){ if(dp[i][k]){ dp[i+1][k|(a[i]&b[j])] = true; } } } } REP(i,512){ if(dp[n][i]){ cout << i << endl; return; } } }
D. Boboniu Chats with Du
貪欲でも通ると思うんだけど実装が悪かったのか通らなかった
コンテスト終わってからちらっと見かけた方針で書いたら一発で通って反省
をとに分ける
後者のものを何個取るかで全探索を行い、そのmaxを出力すればいい
後者のものを個取った時、取れる前者の個数は、個となる
そのため、両者とも降順にソートをしておき、前者のものは予め累積和をとっておき、個の和をそれぞれで求めればいい
提出コード
void solve(){ ll n, d, m; cin >> n >> d >> m; vector<ll> a, b; REP(i,n){ ll num; cin >> num; if(num <= m) a.emplace_back(num); else b.emplace_back(num); } sort(a.rbegin(), a.rend()); sort(b.rbegin(), b.rend()); vector<ll> cum(n+1); REP(i,n){ if(i < size(a)) cum[i+1] = cum[i] + a[i]; else cum[i+1] = cum[i]; } ll ans = cum[n]; ll sum = 0; for(int i=1;i<=size(b);i++){ int cnt = n - (i - 1) * (d + 1) - 1; if(cnt < 0) break; if(i > 0) sum += b[i-1]; chmax(ans, sum + cum[cnt]); } cout << ans << endl; }