うーん安定の水パフォ真ん中
Eに時間かけ過ぎちゃった
Bondo416さんのAtCoder Beginner Contest 159での成績:1166位
— ボンド@競プロ (@bond_cmprog) 2020年3月22日
パフォーマンス:1423相当
レーティング:1249→1268 (+19) :)#AtCoder https://t.co/o0DtNZyuPA
A - The Number of Even Pairs
Aにしては難しいね
を出力する
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl; }
B - String Palindrome
愚直に回文判定していけばいい
for回したけどreverseしたやつが一致するかで判定できるの天才じゃない?
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int N = S.size(); string T = S.substr(0, (N-1)/2); string U = S.substr((N+3)/2-1); bool ok = true; for(int i=0;i<N/2;i++){ if(S[i] != S[N-i-1]) ok = false; } for(int i=0;i<(N-1)/2;i++){ if(T[i] != T[(N-1)/2 - i - 1]) ok = false; if(U[i] != U[(N-1)/2 - i - 1]) ok = false; } if(ok) cout << "Yes" << endl; else cout << "No" << endl; }
C - Maximum Volume
だいたいこういうのは正方形とか立方体とか同じやつかければ大きくなる
なのでを出力すればいい
ちゃんと証明するなら解説の相加相乗平均使えば良いね
ついこの間誤差で殺されたばかりだからビクビクしながら投げたけど大丈夫だった
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); double L; cin >> L; printf("%.12lf\n", (L / 3) * (L / 3) * (L / 3)); }
D - Banned K
これ4800人も解けるのかあというお気持ち
愚直に毎回計算していると間に合わなさそうなので高速化を考える
一先ずN個のときの場合の数baseとして求めておくと
を除いた場合の数は
(は数列に出てくるの個数)
で求められる
何故かmodを取る使命感に駆られて1WA生やしました(?)
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); map<int, ll> mp; REP(i,N){ cin >> A[i]; mp[A[i]]++; } ll base = 0; for(auto x : mp) base += x.second * (x.second - 1) / 2; REP(i,N){ ll tmp = mp[A[i]]; ll ans = base; ans -= tmp * (tmp - 1) / 2; tmp--; ans += tmp * (tmp - 1) / 2; cout << ans << endl; } }
E - Dividing Chocolate
これ難しいね
最初区間にどんどん分けられていくから金塊ゲーム思い出して見に行ってた
Hの制約が小さいのでHはbit全探索できる
その状態でWをどこで切るかは貪欲に切っていけばいい
あとはこれを実装するだけなんだけど結構しんどい
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int H, W, K; cin >> H >> W >> K; vector<string> S(H); REP(i,H) cin >> S[i]; vector<vector<int>> cum(H+1, vector<int>(W+1)); REP(i,H) REP(j,W){ cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + (S[i][j] == '1'); } int ans = INF; REP(i, 1<<(H-1)){ vector<int> h; REP(j,H-1) if((i >> j) & 1) h.push_back(j+1); h.push_back(H); int cnt = (int)h.size() - 1; int preW = 0; bool ok = true; for(int j=1;j<=W;j++){ int preH = 0; int tmp = 0; for(auto x : h){ chmax(tmp, cum[x][j] - cum[preH][j] - cum[x][preW] + cum[preH][preW]); preH = x; } if(tmp > K){ if(j == 1){ ok = false; break; } if(preW == W-1 && j == W){ ok = false; break; } preW = j - 1; j--; cnt++; } } int tmp = 0; int preH = 0; for(auto x : h){ chmax(tmp, cum[x][W] - cum[preH][W] - cum[x][preW] + cum[preH][preW]); preH = x; } if(tmp > K) ok = false; if(ok){ chmin(ans, cnt); } } cout << ans << endl; }
F - Knapsack for All Segments
見た目と制約がDPと言っているんだけどFを見たのが終了10分前なので間に合わず
結構全完している人も多かったからちゃんと通しておきたい
おわりに
Dで謎の1WA生やしたのが本当によくわからない(何が見えていたんだろう)
Eでbit全探索に気づいてからも実装に時間かけ過ぎちゃったのが良くなかったかな