ABC380 D問題（Strange Mirroring）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）380 D問題をC++とPythonで解いてみました。ABC380は、2024年11月16日21:00に実施されました。

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

D問題 Strange Mirroring（Difficulty : 849）

問題の詳細は、リンク先をご覧ください。

ABC380 D問題 Strange Mirroring

文字列と変換した文字列のどちらかを選ぶかは、2進数の表現から判定できます。AtCoder Problems による Difficulty は 849 でした。

解答案

$S$ と 大文字小文字を入れ替えた $T$ は、次のように並びます。

• $S$
• $ST$
• $STTS$
• $STTSTSST$
• $STTSTSSTTSSTSTTS$

最後の例について表で順番（10進数および2進数）と文字列を示します。

仮に14番目の文字列が $S$ か $T$ か分からないとします。

• 0-7番目の反転が8-15番目となります。14番目の文字列は、6番目の文字列の入れ替えとなります。
• 0-3番目の反転が4-7番目となります。6番目の文字列は、2番目の文字列の入れ替えとなります。
• 0-1番目の反転が2-3番目となります。2番目の文字列は、0番目の文字列の入れ替えとなります。つまり $S$ の入れ替えです。

結果的に14番目の文字列は入れ替えが3回あることから $T$ になります。

再帰関数の表現と結論

入れ替え回数を返す関数は、再帰関数で書くと以下のコードとなります。

int rec(ll c)
{
	if (c == 0) {
		return 0;
	}
	for (int i = 60; i >= 0; --i) {
		if ((c & (1LL << i)) != 0) {
			c -= (1LL << i);
			break;
		}
	}
	return rec(c) + 1;
};

再帰関数の内容を読むと、2進数表現のビットをカウントしているだけなので、$N$ 番目（$N$ は0からカウントします）の文字列について以下が成り立つことが分かります。

• $N$ を2進数で表現したときに 1 の個数が偶数の場合、$S$
• $N$ を2進数で表現したときに 1 の個数が奇数の場合、$T$

C++ プログラム例（ABC380D）

$q$ 個の $k$ に対して、以下の順番に処理をします。$n$ は文字列 $s$ の長さです。

• c=k/n 番目の文字列に対象の文字が含まれています（19行目）。
• 対象の文字列の d=k%n 番目が対象の文字です（20行目）。
• 数 c を2進数で表現したときに含まれる 1 の個数を bitset で 求めます（21行目）。
  • 奇数の場合、大文字と小文字を入れ替えます。
  • 偶数の場合、そのまま文字を出力します。

以下が、C++プログラムです。

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

typedef long long int ll;

int main()
{
	string s;
	cin >> s;
	int n = (int)s.length();

	int q;
	cin >> q;
	vector<char> result(q);
	for (int i = 0; i < q; ++i) {
		ll k;
		cin >> k;
		--k;
		ll c = k / n;
		ll d = k % n;
		int t = (int)bitset<64>(c).count();
		if (t % 2 == 1) {
			if (isupper(s[d])) {
				result[i] = (char)tolower(s[d]);
			} else {
				result[i] = (char)toupper(s[d]);
			}
		} else {
			result[i] = s[d];
		}
	}

	for (int i = 0; i < q; ++i) {
		cout << result[i] << " \n"[i == q - 1];
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC380D）

Python版も基本的な考え方は同じです。1の個数は、bit_count メソッドでカウントすることができます（12行目）。以下がプログラムです。

"""AtCoder Beginner Contest 380 D"""
s = input()
n = len(s)

q = int(input())
k = list(map(int, input().split()))
result = [''] * q
for i in range(q):
    k[i] -= 1
    c = k[i] // n
    d = k[i] % n
    if c.bit_count() % 2 == 1:
        if s[d].isupper():
            result[i] = s[d].lower()
        else:
            result[i] = s[d].upper()
    else:
        result[i] = s[d]

print(*result)

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

最後に

コンテスト中に（証明はできませんでしたが）法則には気が付き解くことができました。

引き続き ABC の問題を紹介していきます。