AtCoder Beginner Contest 354
結果
A - Exponential Plant : AC(12:43)(1ペナ)
B - AtCoder Janken 2 : AC(9:29)
C - AtCoder Magics : AC(41:21)
D - AtCoder Wallpaper : 提出無し
A - Exponential Plant
植物が発芽してから$${i}$$日目には$${2^i}$$cm伸びる
植物の高さが$${H}$$cmを超えるのは何日目か求める問題
自分の回答
int main() {
int64_t H;
cin >> H;
int64_t sum = 0, r = 1;
for(int i = 0; i < 1000; i++){
sum += r;
if(sum > H){
printf("%d\n", i + 1);
return 0;
}
r *= 2;
}
}そのまま
forの回数が足りなくてWA
公式解説
int main(){
int h;
cin >> h;
int ans = 0;
int now = 0;
while (now <= h) {
now += 1 << ans;
ans++;
}
cout << ans << endl;
}https://atcoder.jp/contests/abc354/editorial/10035より
そうか1を日数分左シフトしたのがその日の伸び数か
なるほど
B - AtCoder Janken 2
$${N}$$人のAtCoderユーザーがいて、それぞれユーザー名は$${S_{i}}$$、レートは$${C_{i}}$$である
ユーザーにユーザー名の辞書順に$${0}$$から$${N-1}$$の番号を付ける
全員のレートを足し、それを$${N}$$で割った余りの番号のユーザーを求める問題
自分の回答
int main() {
int N;
cin >> N;
vector<pair<string, int>> A(N);
int sum = 0;
for(int i = 0; i < N; i++){
string s;
int c;
cin >> s >> c;
sum += c;
A[i] = {s, c};
}
sort(A.begin(), A.end());
printf("%s\n", A[sum % N].first.c_str());
}そのまま
公式解説
省略
C - AtCoder Magics
カードゲームのカードが$${N}$$枚あり、それぞれ強さは$${A_{i}}$$、コストは$${C_{i}}$$である
$${1}$$枚カードを選び、そのカードより強さが高くコストの小さいカードがあった時、選んだカードを廃棄する
この操作ができなくなるまで繰り返したとき、残るカードの枚数と番号を求める問題
自分の回答
int main() {
int N;
cin >> N;
vector<pair<pair<int64_t, int64_t>, int>> A;
for(int i = 0; i < N; i++){
int a, c;
cin >> a >> c;
A.push_back({{a, c}, i + 1});
}
sort(A.begin(), A.end());
set<int> ans;
int64_t minn = A[N - 1].first.second;
for(int i = N - 1; i >= 0; i--){
auto [p, n] = A[i];
auto [a, c] = p;
if(minn >= c){
ans.insert(n);
}
minn = min(minn, c);
}
printf("%d\n", ans.size());
for(int x : ans){
printf("%d ", x);
}
printf("\n");
}自身より強さの高いカードの中に自身よりコストの小さいカードが一枚でもあればいいから強さの降順に見て行って今まで見てきた中で最もコストの小さい値を持ってそれと比較していけばいい
公式解説
省略
D - AtCoder Wallpaper
あるパターンの繰り返しな壁紙がある
左下の頂点が$${(A,B)}$$、右上の頂点が$${(C,D)}$$な長方形における黒色の領域の面積を$${2}$$倍した値を求める問題
自分の回答
2倍のあたりから二次元累積和な臭いしかしなかったけど各辺がパターンの端かの場合分けを上手くまとめたり一括で計算する方法を思いつかなかった
前に類題見た覚えがあるけどちゃんと解法覚えられてなかったな
公式解説
using i64 = long long;
constexpr int mass[2][4] = {
{2, 1, 0, 1},
{1, 2, 1, 0}
};
// mass[i][j] : 長方形 [[j, j + 1], [i, i + 1]] の面積 x 2
constexpr i64 inf = 4000000000ll;
int main() {
// 入力
i64 a, b, c, d;
cin >> a >> b >> c >> d;
// 計算
i64 ans = 0;
for (int fy = 0; fy < 2; ++fy) {
for (int fx = 0; fx < 4; ++fx) {
const i64 x1 = (a - fx + 3 + inf) / 4, x2 = (c - fx + 3 + inf) / 4;
const i64 count_x = x2 - x1; // x 方向の個数
const i64 y1 = (b - fy + 1 + inf) / 2, y2 = (d - fy + 1 + inf) / 2;
const i64 count_y = y2 - y1; // y 方向の個数
ans += count_x * count_y * mass[fy][fx];
}
}
// 出力
cout << ans << endl;
}https://atcoder.jp/contests/abc354/editorial/10004より
これはパターンの各マスが何回入っているかを計算する方法か
A,B,C,Dよりも小さい座標となる点をinfとして
infからCまででmass[i][j]が出てくる回数-infからAまででmass[i][j]が出てくる回数でAからCまででx軸方向におけるmass[i][j]が出てくる回数になるからそれをy軸でも計算して掛ければ長方形内でmass[i][j]が出てくる回数になる
この方向でも考えてはいたけど結局どうすればまとめられるかがわからなかったけどこれで良かったのか