毎日ABC day21【c++】ABC326 A-C問題解説【ACコード付き】

AtCoder Beginner Contest 326

A - 2UP3DOWN

2フロア上、または3フロア下までは階段を、それ以外にはエレベーターを使用するルールがある。$X$ 階から $Y$ 階への移動にはどちらを使用するか、という問題。

シンプルな条件分岐で実装できる。

int main()
{
	int X, Y;
	cin >> X >> Y;
	if (Y - X >= -3 && Y - X <= 2) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

B - 326-like Numbers

3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しい数の中で、$N$ 以上の最小の数を出力せよ、という問題。

Nから1つずつインクリメントしながら、条件を満たした数がきたら出力する。

int main()
{
	int N;
	cin >> N;
	for (int i = N; i <= 919; i++)
	{
		int d1 = i / 100;
		int d2 = (i - 100 * d1) / 10;
		int d3 = i % 10;
		if (d1 * d2 == d3)
		{
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

C - Peak

$N$ 個のプレゼントがそれぞれ座標 $A_i$に置かれている。

数直線上の長さ $M$ の半開区間 $[x,x+M) $にあるプレゼントを全て受け取れる時、最大の受け取れるプレゼント数を求めよ。

最初は座標 $x$　までに受け取れるプレゼント数を累積和で記憶しておく方式を利用しようとしたが、座標の制限が $10^9$ あることに気づいて断念。

プレゼントの個数 $N$ は $10^5$までの制約なので、queueに1つずつプレゼントを追加していき、もし $[x,x+M) $から外れるプレゼントはqueueから外していく方式で実装した。ボトルネックはソートとなり計算量 $O(NlogN)$ 程度である。

int main()
{
	// 入力
	int N, M;
	cin >> N >> M;
	vector<int> boxes(N);
	for (int i = 0; i < N; i++) cin >> boxes[i];
	// 昇順でソート
	sort(boxes.begin(), boxes.end());
	long long ans = 0;
	queue<int> q;
	int count_box = 0;
	for (int i = 0; i < N; i++)
	{
		q.push(boxes[i]);
		count_box++;
		while (boxes[i] - M + 0.1 > q.front())
		{
			q.pop();
			count_box--;
		}
		if (count_box > ans) ans = count_box;
	}
	cout << ans << endl;
	return 0;
}