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\times {10}^5$
• $1\leqq Q\leqq 2\times {10}^5$
• $1\leqq K_i\leqq {10}^{1}8$

思考の筋道

初期の文字列を $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問題の解説でした！

では、またね。

リンク