AtCoder

ABC295 D問題(Three Days Ago)を解く

AtCoder_ABC295_D

AtCoder が提供しているABC(AtCoder Beginner Contest)295 のD問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Three Days Ago(Difficulty : 939)

問題はリンク先をご覧ください。

ABC295 D問題 Three Days Ago

数字が表れる頻度回数のパリティを使って解くことができました。AtCoder Problems による Difficulty は 939 でした。

解答案

コンテスト中には、TLE(Time Limit Exceeded)判定のプログラムしか書くことができませんでした。

基本的な考え方は、以下です。

  • 0から9が現れる頻度回数を求めるために累積和を求める(10-16行目)。
  • 区間 [left, right) において、0から9が現れる回数がすべて偶数の場合に [left, right) は、「嬉しい列」となります(22-30行目)。
  • すべての区間について調べて、「嬉しい列」の個数を出力する(34行目)。

以下のプログラムは、3つある入力例に対して、すべて正しい解答を出力しました。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	string s;
	cin >> s;
	vector<vector<int>> sum(10, vector<int>(s.length() + 1, 0));
	for (int i = 0; i < s.length(); ++i) {
		int temp = s[i] - '0';
		for (int j = 0; j < 10; ++j) {
			sum[j][i + 1] = sum[j][i] + (j == temp);
		}
	}

	ull result = 0;
	for (int left = 0; left < s.length(); ++left) {
		for (int right = left + 2; right <= s.length(); right += 2) {
			bool happy = true;
			for (int i = 0; i < 10; ++i) {
				if ((sum[i][right] - sum[i][left]) % 2 != 0) {
					happy = false;
					break;
				}
			}
			if (happy) {
				++result;
			}
		}
	}

	cout << result << endl;

	return 0;
}

    制約から文字列 S の長さの最大値は、5 × 105 です。計算量は、文字列の長さの2乗になるため、25 × 1010 となります。確かに間に合いません(108 程度が上限)。

    パリティを使った改善版

    以下は、公式解説を参考にしました。

    結局、累積和を使って、[left, right) において、0から9が現れる回数がすべて偶数であることを確認していました。この場合、具体的な頻度の回数ではなく、パリティ(偶数で0、奇数で1となるビット)さえ分かれば判断ができます。パリティは各数字で1ビットなので、0から9までの数字の出現頻度を10ビットのパリティ(0から1023)で表現できます。

    それぞれの数字列の数字 s[i] について、10ビットパリティ p[i] が対応します。このとき、p[i] = p[j] が成り立てば、[i, j) が「嬉しい列」となります。

    「嬉しい列」の組み合わせの数は、p[i] として現れる10ビットパリティの頻度をカウントすれば、計算可能です。

    C++ プログラム例(ABC295D)

    上で考察したことをプログラムに変換しました。p[i + 1] は、p[i] から 1 ビットしか変化しません。これは s[i] が表す数字のパリティが反転するだけです(17行目)。

    10ビットパリティの頻度は map コンテナ m でカウントします(14、18行目)。最終的には、m の頻度から解答を求めています(23行目)。

    最終的な、C++ プログラムは以下となります。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef unsigned long long int ull;
    
    int main()
    {
    	string s;
    	cin >> s;
    
    	vector<int> p(s.length() + 1);
    	p[0] = 0;
    	map<int, ull> m;
    	++m[p[0]];
    	for (int i = 0; i < s.length(); ++i) {
    		int num = s[i] - '0';
    		p[i + 1] = p[i] ^ (1 << num);
    		++m[p[i + 1]];
    	}
    
    	ull result = 0;
    	for (auto e : m) {
    		result += e.second * (e.second - 1) / 2;
    	}
    
    	cout << result << endl;
    
    	return 0;
    }

    AC(Accepted=正しいプログラム)と判定されました。

    Python プログラム例(ABC295D)

    Python では、defaultdict を使いました。C++ のプログラムを移植しました。

    """AtCoder Beginner Contest 295 D"""
    from collections import defaultdict
    
    s = input()
    p = [0] * (len(s) + 1)
    p[0] = 0
    m = defaultdict(int)
    m[p[0]] += 1
    for i, ch in enumerate(s):
        num = int(ch)
        p[i + 1] = p[i] ^ (1 << num)
        m[p[i + 1]] += 1
    
    result = 0
    for v in m.values():
        result += v * (v - 1) // 2
    
    print(result)

    こちらも「AC」と判定されました。

    最後に

    コンテストで提出したプログラムは、時間が間に合いませんでしたが、累積和を使って、区間に入っている個数が2で割り切れるかを確認することはできていました。

    公式解説で、パリティに注目すれば解けることが分かりました。元の累積和のプログラムよりもすっきり書けました。勉強になりました。

    引き続き ABC に挑戦して、解説記事を書いていくつもりです。

    COMMENT

    メールアドレスが公開されることはありません。 が付いている欄は必須項目です

    CAPTCHA