AtCoder

ABC380 D問題(Strange Mirroring)を解く

AtCoder_ABC380_D

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進数)と文字列を示します。

0123456789101112131415
0000000100100011010001010110011110001001101010111100110111101111
STTSTSSTTSSTSTTS

例えば、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 の問題を紹介していきます。

COMMENT

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

CAPTCHA