AtCoder Beginner Contest 338

A - Capitalized?

与えられる文字列$S$が先頭文字が大文字、それ以外が小文字で構成されているかを判定する問題。

cctypeライブラリに含まれるisupper関数、islower関数を使用して大文字と小文字の判定をすると楽に実装できる。もちろん自分で条件を書いてもOK.

string S;

int main()
{
	cin >> S;
	if (!isupper(S[0]))
	{
		cout << "No" << endl;
		return 0;
	}
	for (int i = 1; i < S.size(); i++)
	{
		if (!islower(S[i]))
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

B - Frequency

英小文字からなる文字列$S$が与えられる。一番出現回数の多い文字を求めよ、という問題。

アルファベットそれぞれをカウントする用の配列を用いて実装した。

後から見返すと、mode_countやmode_alphaなどの変数を置かずに実装もできたし、その方がシンプルだった。

string S;
int alpha_count[26];

int main()
{
    cin >> S;
    for (int i = 0; i < S.size(); i++) {
        alpha_count[S[i] - 'a']++;
    }
    
    int mode_count = -1;
    int mode_alpha = -1;
    
    for (int i = 0; i < 26; i++)
    {
        if (alpha_count[i] > mode_count)
        {
            mode_count = alpha_count[i];
            mode_alpha = i;
        }
    }
    
    cout << char('a' + mode_alpha) << endl;
    return 0;
}

C - Leftover Recipes

$N$個の材料が$Q_{i}$グラムずつあり、1人前作るの$A$と$B$が存在する。に材料が$A_{i}$、$B_{i}$グラム必要な料理が存在する。最大何人前の料理を作ることができるか。

最初はA,Bの組み合わせを全探索し、その後にその組み合わせで料理が作れるかを判定していたが、それだと3重ループになってしまって実行時間に間に合わなかった。

Aをx人数分作る、と決めるとBの料理が何人分作れるか必然的に決まってくるので、片方の料理の人数分を固定して探索する方に方向転換し、2重ループに修正したらACした。

int N;
long long Q[19];
long long A[19];
long long B[19];

int main()
{
    // 入力
    cin >> N;
    long long max_Q = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> Q[i];
        max_Q = max(max_Q, Q[i]);
    }
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];
    
    // Aをx個作る時、Bは最大いくら作れるか
    long long ans = 0;
    for (int i = 0; i <= max_Q; i++)
    {
        long long max_y = 1e18;
        for (int j = 1; j <= N; j++)
        {
            if (Q[j] < A[j] * i)
            {
                max_y = -1e18;
            }
            else if (B[j] > 0)
            {
                long long tmp = (Q[j] - A[j] * i) / B[j];
                max_y = min(max_y, tmp);
            }
        }
		ans = max(ans, i + max_y);
    }
    cout << ans << endl;
    return 0;
}

// TLEのコードです
int N;
int Q[19];
int A[19];
int B[19];

int main()
{
	// 入力
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> Q[i];
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) cin >> B[i];
	int max_Aonly = 100000000;
	int max_Bonly = 100000000;
	// 検証用
	cout << max_Aonly << endl;
	cout << max_Bonly << endl;
	// Aだけ、Bだけでmax何人分作れるかを確認
	for (int i = 1; i <= N; i++)
	{
		if (A[i] == 0) continue;
		int tmp = Q[i] / A[i];
		max_Aonly = min(max_Aonly, tmp);
	}
	for (int i = 1; i <= N; i++)
	{
		if (B[i] == 0) continue;
		int tmp = Q[i] / B[i];
		max_Bonly = min(max_Bonly, tmp);
	}
	// 検証用
	cout << max_Aonly << endl;
	cout << max_Bonly << endl;
	// max_Aonly + max_Bonlyが最大値。その範囲の中で片方固定して回してみる
	int ans = 0;
	// Aの回数を固定してBを回していく
	for (int i = 1; i <= max_Aonly; i++)
	{
		for (int j = 1; j <= max_Bonly; j++)
		{
			for (int k = 1; k <= N; k++)
			{
				if (Q[k] < A[k] * i + B[k] * j) break;
				if (k == N) ans = max(ans, i + j);
			}
		}
	}
	cout << ans << endl;
	return 0;
}