AtCoder Beginner Contest 328

A - Not Too Hard

$N$ 個の問題があるので、$X$ 点以下の点数の問題の合計点を求めよ。

int main()
{
	int N , X;
	cin >> N >> X;
	int S[10];
	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		if (S[i] <= X) ans += S[i];
	}
	cout << ans << endl;
	return 0;
}

B - 11/11

$N$ 月までのそれぞれの月に $D_{i}$ 日ある暦がある。$i$月⚪$j$日と記述するときに、$i , j$が1つの数字のみから表されるのは1年で何回あるか。

int main()
{
	int N;
	cin >> N;
	int D[109];
	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> D[i];
		if (i < 10)
		{
			if (i <= D[i]) ans++;
			if (i * 10 + i  <= D[i]) ans ++;
		}
		else
		{
			if (i / 10 == i % 10)
			{
				int tmp = i / 10;
				if (tmp <= D[i]) ans++;
				if (tmp * 10 + tmp  <= D[i]) ans ++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

C - Consecutive

長さ $N$ の文字列 $S$ 列が与えられる。右端と左端のペアが $Q$ 個与えられるので、指定の範囲に連続するアルファベットのペアがいくつあるか、それぞれ出力せよ、という問題。

$Q$ 個のペアに対して毎度計算していくと計算量が膨大になってしまうため、累積和の考えを利用して、事前にどの場所まででいくらのペアができるかをdp配列に記憶しておき、右端から左端のペアの数を引くだけで計算できるようにしておく。

int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> dp(N + 1, 0); 
    for (int i = 1; i < N; i++) {
        dp[i] = dp[i - 1];
        if (S[i] == S[i - 1]) {
            dp[i]++;
        }
    }
    dp[N] = dp[N - 1];
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
		// 0インデックスに変更
        l--;
        r--;
        int result = dp[r] - dp[l];
        cout << result << endl;
    }
    return 0;
}