ABC380 D問題の解説（Python）

はじめに

この記事では、ABC380のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC380　D – Strange Mirroring

問題

問題

英大小文字からなる文字列 \(S\) が与えられます。

\(S\) に以下の操作を \(10^{100}\) 回繰り返します。

• まず、 \(S\) の大文字を小文字に、小文字を大文字に書き換えた文字列を \(T\) とする。
• その後、 \(S\) と \(T\) をこの順に連結した文字列を新たな \(S\) とする。

\(Q\) 個の質問に答えて下さい。 そのうち \(i\) 個目は次の通りです。

• 全ての操作を終えた後の \(S\) の先頭から \(K_i\)​ 文字目を求めよ。

制約

• \(1 \leqq len(S) \leqq 2×10^5\)
• \(1 \leqq Q \leqq 2×10^5\)
• \(1 \leqq K_i \leqq 10^18\)

思考の筋道

初期の文字列を \(S_0\)、初期の文字列の大文字と小文字を反転した文字列を \(T_0\) と表すことにします。

操作を繰り返すと文字列は次のようになっていきます。

• \(S_0\)
• \(S_0\) \(T_0\)
• \(S_0\) \(T_0\) \(T_0\) \(S_0\)
• \(S_0\) \(T_0\) \(T_0\) \(S_0\) \(T_0\) \(S_0\) \(S_0\) \(T_0\)

操作を行うたび、\(S_0\) や \(T_0\) のグループの数が倍に増えていることがわかります。

さて、\(S\) の先頭から \(K_i\)​ 文字目が何であるかを知るには、次のことが分からなければなりません。

1. \(K_i\)​ 文字目は何グループ目の何番目か
2. そのグループは \(S_0\) なのか \(T_0\) なのか

①について

各グループは当然同じ文字数なので、\(K_i\) をその文字数で割った商と余りを調べることで、\(K_i\)​ 文字目が何グループ目の何番目か分かります。

なお、グループ番号も、各グループ内の番号も、0 始まりとして考えることにします。つまり、1 文字目は 0 グループ目の 0 番目と考えます。

②について

この問題の肝となる部分です。グループが \(S_0\) なのか \(T_0\) なのかをどのように調べればよいでしょうか？

例をもとに考えてみましょう。

反転元をさかのぼることは、なるべく大きな2の累乗を引くことに対応しています。

0 になるまで 2 の累乗を引いていくことで、反転の回数が分かります。
6 – 4 = 2
2 – 2 = 0
この場合の反転回数は2回ですね。

また、上記の式は 6 = 4 + 2 とも書き表せます。この式は10進数を2進数に変形するための式です。

6 を 2進数で表すと 110 になります。このときの 1 の数が反転回数になるということです。

つまり、グループ番号を2進数に直し、1の個数の偶奇を調べれば、そのグループが \(S_0\) か \(T_0\) か分かるということですね。

ここまで分かれば、あとは実装するのみです。

具体例で実験する中で、2進数の背景に気づけるかどうかがポイントでした。

コード

S = input()
Q = int(input())
K = list(map(int, input().split()))

ans = []

for num in K:
    q = (num - 1) // len(S)
    r = (num - 1) % len(S)
    bin_q = bin(q)[2:]
    mirror_count = bin_q.count("1")
    if mirror_count % 2 == 0:
        ans.append(S[r])
    else:
        ans.append(S[r].swapcase())

print(*ans)

以上、ABC380のD問題の解説でした！

では、またね。

リンク