AtCoder が提供しているABC(AtCoder Beginner Contest)380 D問題をC++とPythonで解いてみました。ABC380は、2024年11月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Strange Mirroring(Difficulty : 849)
問題の詳細は、リンク先をご覧ください。
文字列と変換した文字列のどちらかを選ぶかは、2進数の表現から判定できます。AtCoder Problems による Difficulty は 849 でした。
解答案
$S$ と 大文字小文字を入れ替えた $T$ は、次のように並びます。
- $S$
- $ST$
- $STTS$
- $STTSTSST$
- $STTSTSSTTSSTSTTS$
最後の例について表で順番(10進数および2進数)と文字列を示します。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
S | T | T | S | T | S | S | T | T | S | S | T | S | T | T | S |
例えば、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 の問題を紹介していきます。