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;
}