AtCoder Beginner Contest 354
C問題までの3完20分。
レートは380から442の62アップとなった。
D, E問題は翌日に解いたものになります。
無事茶色に入ることができたので、noteの方でも入茶記事を書こうと思います。
A - Exponential Plant
毎晩$2^i$ずつ伸びる植物がある。高橋くんの身長 $H$ cmを超えるのは何日目の朝か。この植物は0日目には0cmであったとする、という問題。
植物が発芽してからの1日ごとの朝の高さは1cm,3cm,7cm,15cm,31cm,63cm となる。つまりx日後の植物の高さを$f(x)$とすると、
$$
f(x) = 2^x - 1
$$
と表すことができる。
long long N;
int main()
{
cin >> N;
long long height = 1;
for (int i = 1; i <= N;i++)
{
height *= 2;
height += 1;
if (height > N)
{
cout << i + 1 << endl;
return 0;
}
}
cout << 2 << endl;
return 0;
}
B - AtCoder Janken 2
$N$人のユーザー名とレート(整数)が与えられる。
全員のレートの総和を$T$とし、ユーザー辞書順に並び替えた時、$T$ $mod$ $N$ 番目に並んでいた人が勝者とする。勝者のユーザー名を出力せよ、という問題。ただし、先頭の人が0番目から始まることに注意。
全員を辞書順にソートすればOK。
int N;
int C[109];
vector<string> S(109);
vector<pair<string, int>> member;
int main()
{
cin >> N;
int total = 0;
for (int i = 1; i <= N; i++)
{
cin >> S[i] >> C[i];
member.push_back(make_pair(S[i], C[i]));
total += C[i];
}
sort(member.begin(), member.end());
int mod = total % N;
cout << member[mod].first << endl;
return 0;
}
C - AtCoder Magics
強さとコストが整数で定義されているカードを$N$枚所持している。カード$i$の強さは$A_{i}$で、コストは$C_{i}$である。
$A_{x} > A_{y}$ かつ $C_{x} < C_{y}$を満たすカードは弱いので捨てることにした。最終的に残るカードの集合を出力してください。
int N;
int A[200009];
int C[200009];
vector<pair<int, int>> cards;
bool trash[200009];
int main()
{
cin >> N;
int count_cards = N;
for (int i = 1; i <= N; i++) trash[i] = false;
for (int i = 1; i <= N; i++)
{
cin >> A[i] >> C[i];
cards.push_back(make_pair(C[i], i));
}
sort(cards.begin(), cards.end());
int highest_card = 0;
for (int i = 0; i < N; i++)
{
int idx = cards[i].second;
if (highest_card > A[idx])
{
count_cards--;
trash[idx] = true;
}
else highest_card = A[idx];
}
cout << count_cards << endl;
bool tmp = false;
for (int i = 1; i <= N; i++)
{
if(trash[i] == false)
{
if (tmp) cout << " ";
cout << i;
tmp = true;
}
}
cout << endl;
return 0;
}
D - AtCoder Wallpaper
説明が難しいので問題文は割愛。
白と黒で塗り分けられている図形があるので、指定範囲の黒の面積を求めよ、という問題。
解説Youtubeを見て累積和で解いたらシンプルさに驚いた。
この問題のポイントは以下の二つ。
- 第一象限で考える(並行移動可能なので)
- 原点を含む長方形に帰着させる
long long A, B, C, D;
// 原点を左下、(a, b)を右上とした長方形の中の黒い面積を求める関数
long long ft_area(long long a, long long b)
{
long long ra = a % 4; // x 軸方向は4の倍数で繰り返される
long long rb = b % 2; // y 軸方向は2の倍数で繰り返される
// 繰り返し部分の面積を足す
a -= ra;
b -= rb;
long long res = a * b;
// 繰り返し部分からはみ出た部分を足す(黒面積の2倍した値を足すことに注意)
// 縦方向にははみ出てもmax1マス
if (rb == 1) res += a;
// 横方向にははみ出てもmax3マス
if (ra >= 1)
{
res += b * 3 / 2;
if (rb) res += 2;
}
if (ra >= 2)
{
res += b * 3 / 2;
if (rb) res += 1;
}
if (ra >= 3) res += b / 2;
return res;
}
int main()
{
cin >> A >> B >> C >> D;
// 第一象限へ移動
A += 1e9;
B += 1e9;
C += 1e9;
D += 1e9;
long long ans = ft_area(C, D) - ft_area(A, D) - ft_area(C, B) + ft_area(A, B);
cout << ans << endl;
}
コンテスト中は以下のような形でゴリゴリの条件分岐で実装して、WAが出まくっていました。(これはACコードではありません)
long long A, B, C, D;
int main()
{
// 入力
cin >> A >> B >> C >> D;
// 4つの列に分割して考える
A += 1e9;
B += 1e9;
C += 1e9;
D += 1e9;
long long height = D - B;
long long row = C - A;
float area1 = 0;
float area2 = 0;
float area3 = 0;
float area4 = 0;
float sum_column_area = 0;
float total_area = 0;
// 1列目
area1 += (height / 2) * 1.5;
if (height % 2 != 0)
{
if (D % 2 != 0) area1 += 1;
else area1 += 0.5;
}
// 2列目
area2 += (height / 2) * 1.5;
if (height % 2 != 0)
{
if (D % 2 != 0) area2 += 0.5;
else area2 += 1;
}
// 3列目
area3 += (height / 2) * 0.5;
if (height % 2 != 0)
{
if (D % 2 != 0) area3 += 0;
else area3 += 0.5;
}
// 4列目
area4 += (height / 2) * 0.5;
if (height % 2 != 0)
{
if (D % 2 != 0) area4 += 0.5;
else area4 += 0;
}
// 4列の合計
sum_column_area = area1 + area2 + area3 + area4;
// 4列セットがいくつあるか
total_area += sum_column_area * (row / 4);
if (row % 4 == 0)
{
cout << total_area * 2 << endl;
return 0;
}
// セットにならない部分
long long l = A % 4;
long long r = B % 4;
if (l > r) r += 4;
for (int i = l + 1; i <= r; i++)
{
// cout << total_area << " " << i << endl; // 検証用
if (i % 4 == 1) total_area += area1;
if (i % 4 == 2) total_area += area2;
if (i % 4 == 3) total_area += area3;
if (i % 4 == 0) total_area += area4;
}
long long ans = total_area * 2;
cout << ans << endl;
return 0;
}
E - Remove Pairs
表と裏に整数が書かれているカードが$N$枚テーブルに置いてある。表面同士、もしくは裏面同士に同じ数が書かれたカードのペアをお互いが取っていき、ペアが取れなくなった方が負け、というゲームで二人が勝つために最適な操作を選ぶ時、先行と後攻のどちらが勝つかを求める問題。
これは本番中にD問題と思ってずっと取り組んでいた。bit全探索ということはわかっていたのに、なぜかうまくいかなかった。真相は闇の中。。(下のコードはACです、ご安心を。)
int N;
int A[19];
int B[19];
bool dp[1 << 18];
int main()
{
// 入力
cin >> N;
for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
// 動的計画法
for (int k = 0; k < (1 << N); k++)
{
bool now = false;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i; j++)
{
if (!((k >> i) & 1)) continue;
if (!((k >> j) & 1)) continue;
if (A[i] == A[j] || B[i] == B[j])
{
int pre = (k & ~(1 << i) & ~(1 << j));
if (dp[pre] == false) now = true;
}
}
}
dp[k] = now;
}
// 出力
if (dp[(1 << N) - 1]) cout << "Takahashi" << endl;
else cout << "Aoki" << endl;
return 0;
}