【c++】ABC353 A-D問題解説【ACコード付き】

AtCoder Beginner Contest 353

B問題までの2完10分。
レートは331から380の49アップとなった。

C,D問題は翌日に解いたものになります。

A - Buildings

ビルがN個並んでいる。一番左のビルより高いビルの中で、一番左側にあるビルの場所を出力せよ。という問題。

左側2番目のビルから順番に探索し、一番左のビルより高いビルを見つけたらその場所を出力すればいい。もし一番左のビルより高いビルがなかったら-1を出力する。

int N;
int A[100009];

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++)
	{
		if (A[1] < A[i])
		{
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

B - AtCoder Amusement Park

K人乗りのアトラクションにN人グループ並んでいる。前から順にグループを乗せていき、乗れないグループまで来たらアトラクションを出発させ、次のK人乗りのアトラクションにグループを乗せていく。何回アトラクションを出発させたらNグループ全員をアトラクションに乗せられるか。という問題。

NもKも10^2以下と制約が軽いので、何も考えずループを回す。

現在のアトラクションの空席数をcurrent_emptyで記憶しておきながらNグループ全て終わるまでループを回しながら、何回アトラクションを出発させたか（何回current_emptyを初期化したか）を覚えておけばOK。

最後のお客さんの出発をお忘れなく。

using namespace std;

int N, K;
int A[109];

int main()
{
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];
	int count = 0;
	int current_empty = K;
	for (int i = 1; i <= N; i++)
	{
		if (current_empty >= A[i])
		{
			current_empty -= A[i];
		}
		else
		{
			current_empty = K;
			count++;
			current_empty -= A[i];
		}
	}
	if (current_empty != K) count++;
	cout << count << endl;
	return 0;
}

C - Sigma Problem

ちょっと特殊な問題なので、問題文を読んだ方が早いかもです。

10^8を超えないもの同士の足し算の10^8余りは、和が10^8を超えたら10^8を1回引くのと同義であることを利用して解く問題。

余りを気にせず全ての数A1~ANがN-1回足しておいて、後半でいくつのペアが10^8を超えるか、つまり合計から10^8が何回引かれたかをしゃくとり法で求めます。

本番中はソートして数えるまでは思いついたのですが、しゃくとり法を思い出すことができず、二分探索で模索したらWAでした。O(logN)とO(1)の差を痛感。。

long long N;
long long A[300009];
long long R[300009];
vector<long long> Q;

const long long INF = 1e8;

int main()
{
	cin >> N;
	long long total = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> A[i];
		Q.push_back(A[i]);
		total += A[i] * (N - 1);
	}
	// 昇順に並べる
	sort(Q.begin(), Q.end());
	// しゃくとり法
	for (int i = 0; i < N - 1; i++)
	{
		if (i == 0) R[i] = 0;
		else R[i] = R[i - 1];
		// ギリギリまで増やす
		while (R[i] < N - 1 - i && Q[R[i]] + Q[N - 1 - i] < INF) R[i]++;
		total -= INF * ((N - 1 - i) - R[i]);
		if (R[i] == N - 1 - i) break;
	}
	cout << total << endl;
	return 0;
}

D - Another Sigma Problem

この問題はC問題と違い、総計から余りを求める問題なので、計算各所で余りを計算しながら進むことが許されている。

それぞれのA1からANまでの与えられる数が右辺に来る時と左辺に来る場合をそれぞれ別に足し合わせている。

右辺に来る時は単純で、i-1回足される。
左辺に来る時はペアの右辺の桁の数によって総計に加える数が変わるので、入力を受け取るときに何桁の数がいくつずつあるかをカウントしておく。

const long long INF = 998244353;

long long N;
long long A[200009];
long long digits[200009];
long long dig_mul[19];

int main()
{
	cin >> N;
	long long total = 0;
	for (int i = 0; i <= 10; i++) digits[i] = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> A[i];
		digits[to_string(A[i]).size()]++; 
		total += A[i] * (i - 1);
		total %= INF;
	}
	// 10から10^9まで事前に計算しておく
	dig_mul[0] = 1;
	for (int i = 1; i <= 10; i++)
	{
		dig_mul[i] = 10 * dig_mul[i - 1];
		dig_mul[i] %= INF;
		digits[i] %= INF;
	}
	for (int i = 1; i <= N - 1; i++)
	{
		digits[to_string(A[i]).size()]--; 
		A[i] %= INF;
		for (int j = 1; j <= 10; j++)
		{
			long long tmp = digits[j] * dig_mul[j];
			tmp %= INF;
			total += A[i] * tmp;
			total %= INF;
		}
	}
	cout << total << endl;
	return 0;
}