はまやんはまやんはまやん

hamayanhamayan's blog

Long Long String [第五回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202012-open/tasks/past202012_j

解説

https://atcoder.jp/contests/past202012-open/submissions/22292068

このような問題を初見で解くのはかなり難しい。
今回の問題で重要なのが「やや再帰的な構造を持っている」という部分である。

やや再帰的な構造

ab2で考えてみる。

1手目 a
2手目 ab
3手目 ababab

長さだけを見て考えると、a-zの場合は長さが+1されていて、数字の場合はx+1倍されている。
この数字の場合に再帰的な構造が隠れている。
3手目がabababとなっているが、[2手目][2手目][2手目]の状態になっている。
3手目のある文字は必ず2手目のどこかの文字になっていることになる。
つまり、うまい事計算をすることで、1つ前の手番、再帰的により範囲の狭い部分として考えることができる。

もっと具体的に考える

感覚的な話になるので、もう少し具体的に説明する。
サンプル1で考えよう。ab2c1の6文字目を考えてみる。
あらかじめ、各手番の文字数をカウントしておこう。

1手目 1
2手目 2
3手目 6
4手目 7
5手目 14

文字列全体5手目から話を始めよう。5手目の6文字目は何だろう?
5手目は14文字であるが、数字で作られた文字列なので再帰性を持っている。
具体的には[4手目:1~7][4手目:8~14]となっていて、4手目の何番目かに対応づけることができる。
今回は前半部分に該当するので、「5手目の6文字目」→「4手目の6文字目」と範囲を狭めることができた。

次に4手目だが、7文字目が追加された形になるので、[3手目:1~6][文字]となっている。
6文字目なので、「4手目の6文字目」→「3手目の6文字目」と範囲を狭めることができた。

3手目は、数字で作られた文字列なので再帰性を持っている。
[2手目:1~2][2手目:3~4][2手目:5~6]となっていて、3番目の2手目に対応付けられる。
2手目で見ると6文字目は2文字目に当たるので、「3手目の6文字目」→「2手目の2文字目」と範囲を狭めることができた。

2手目は、2文字目が追加された形になるので、[1手目:1][文字]となっている。
求めたいのは2文字目であるので、この時追加された文字が答えである。
よってbが答え。

一般的な実装に落とし込む

先ほどの例と全く同じことを実装する。

  1. 長さを求める
  2. 手番が多い方から再帰的に手番を減らしていき、文字列追加に対応付けることができたらそれが答え

実装がかなり簡潔なので、上記の例を参考にして読み解いてみてほしい。
考え方を理解する必要があるので大変だが頑張って。
数字で作られた文字列でどのグループに属するかというのを計算するのに剰余を使っている。
1手前の長さで剰余を取れば、1手前で言うと何番目かが得られる寸法である。
0-indexedでないとうまく動かないのでインクリメント/デクリメントで調整している。

string S; ll X;
int N;
ll MA = 1e16;
//---------------------------------------------------------------------------------------------------
ll len[201010];
char solve() {
    len[0] = 0;
    rep(i, 0, N) {
        if ('a' <= S[i] && S[i] <= 'z') len[i + 1] = len[i] + 1;
        else len[i + 1] = min(MA, len[i] * (S[i] - '0' + 1));
    }

    rrep(i, N, 1) {
        if ('a' <= S[i - 1] && S[i - 1] <= 'z') {
            if (X == len[i]) return S[i - 1];
        }
        else {
            X--;
            X %= len[i - 1];
            X++;
        }
    }

    return S[0];
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> X;
    N = S.length();
    cout << solve() << endl;
}