ABC285 C問題の考え方

ABC285 C - abc285_brutmhyhiizp の考え方を書きました。

問題の概要

下のように、自然数Nとアルファベット大文字からなる文字列を対応付けるとします。

 1 ->  A
 2 ->  B
 3 ->  C
   ...
26 ->  Z
27 -> AA
28 -> AB
   ...

アルファベット大文字からなる文字列（以下、S）が与えられるので、Nを逆算してください。

制約

• 1 <= N <= 10^16

「実際に数えてみる」では間に合わない

まずは、問題をそのままコードにするとどうなるかを考えてみます。
これは

A, B, C, ..., Z, AA, AB,　... ,ZZ, AAA, AAB, ...

と順に文字列を生成していき、 入力文字列 S に一致するものが何番目に登場したか を出力すれば、正答できます。

ただし、このアルゴリズムでは実行時間に間に合わないパターンが存在するため、判定はTLEとなってしまいます。
具体的にはNが大きいケース、例えば入力例3の S = BRUTMHYHIIZP のとき 10^16回 のループが回ることになり、実行時間制限時間（2秒）を超過してしまいます。

実行時間2秒に収めるには、多くても 10^8回 程度に抑えたいところです。 より高速なアルゴリズムを考える必要があります。

26進数として見る

A, B, C, ... , Y, Z, AA, AB, ...

という並びは、10進数

1, 2, 3, ... , 8, 9, 10, 11, ...

と似ています。
10進数で「0を使わず、代わりに10をXで表現する」というルールにしてみると、より似た並びとなります。

A, B, C, ... , Y, Z, AA, AB, ...
1, 2, 3, ... , 9, X, 11, 12, ...

10進数では、”1の位”が10回カウントアップすると繰り上がりが発生し、”10の位”が1カウントアップします。 A,B,C… では、”1の位”が A~Z で26回カウントアップすると繰り上がりが発生し、”10の位”ならぬ “26の位” が1カウントアップする、と解釈することができます。

ここでは A,B,C… を”26進数”と呼び、「数と対応するもの」ではなく 「数そのもの」 として扱ってみます。

10進数を読み取るアルゴリズム

文字列 "12345" を整数 12345 として解釈するための変換アルゴリズムを考えてみます。

これは、各桁を分解し、足し合わせれば良さそうです。

• 10^4の位（つまり10000の位）は 1
  • 10000
• 10^3の位（つまり1000の位）は 2
  • 2000
• 10^2の位（つまり100の位）は 3
  • 300
• 10^1の位（つまり10の位）は 4
  • 40
• 10^0の位（つまり1の位）は 5
  • 5

→ 10000 + 2000 + 300 + 40 + 5 = 12345

このアルゴリズムでは、○○の位 という情報を使うため、「何桁の整数か」あるいは「今見ているのは何桁目か」を気にする必要があります。
よりシンプルなアルゴリズムを考えます。

10進数を”前から”読み取るアルゴリズム

"12345" という文字列を、桁数を気にせずに前から読み取る方法があります。

最初に、文字列の先頭の文字を読みます。今回は '1' です。
これを変数に格納しておきます。

n = 1

文字列の長さが1であれば、これで終了です。
ここでは、次の文字が存在したとします。
このとき、最初に読み取った'1'という文字は、実は1ではなく10を表すものであった（10の位に書かれていた）ことが判明します。
実態に合わせるため、先ほどのnを10倍しておきます。

n *= 10

次の文字は'2'であったとします。つまり、この時点で "12" までを読み取りました。
新しく読み取った値（1の位の値）をnに加算します。

n += 2

n == 12 となり、現時点で正しい値を格納することができています。

まだ次の文字が存在し、その文字は '3' であったとします。
"12" は実は12ではなく120を表していたということになるので、実態に合わせるためにnを10倍します。
そして、読み取った値（1の位の値）をnに加算します。

n *= 10
n += 3

n == 123 となり、ここでも現時点で正しい値を格納することができています。

最後の文字までこの操作を繰り返せば、10進数を”前から”読み取ることができます。

26進数を”前から”読み取るアルゴリズム

前から読み取るアルゴリズムを、26進数に応用します。

最初の文字は 'A' とします。

A = 1
B = 2
C = 3
...
Z = 26

ですから、

n = 1

とします。

次の文字は 'B' とします。
10進数の場合、次の文字が存在する際にはnを実態に合わせるために n *= 10 をしていました。これは、10ごとに繰り上がりが発生するためです。
26進数では、26ごとに繰り上がりが起こります。つまり、次の文字が存在する際にはn *= 26をします。

n *= 26
n += 2 # Bは2に対応

あとはこの繰り返しです。
この方法なら、100文字からなる26進数でも、たった100回の「26倍してから足す」の操作で整数として読み取ることができます。

その他のテクニック

Nの初期値を0とする

Nの初期値を0としておくと、最初の文字を特別扱いする必要がなくなり、実装がよりシンプルになります。

n = 0

for c in s:
    n *= 26
    n += convert(c) # A->1, B->2, ...

print(n)

ABC..から123..の変換方法

ABC.. → 123.. の変換も、様々な方法があります。

例えば、
ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
という文字列を用意しておいて、ある文字が ABC の何番目に登場するかを調べるという方法があります。

先頭からチェックしていくというアルゴリズムのため、後ろの文字ほど判定が重くなることに注意しましょう。A B A B ...の変換は高速ですが、Z Y Z Y ...のようなケースではずっと重くなります。

より高速な変換手順としては、辞書（あるいはHashやMapなど）と呼ばれるデータ構造に {'A': 1, 'B': 2, ... }を格納しておく方法もあります。

また、より簡単な実装としては、文字を文字コードに変換し整数として扱うという方法も考えられます。（ASCIIでABC...はこの順に並んでいるという性質を利用します。）

解答例

• Python 3.8.2 (25 ms)
• Rust 1.42.0 (6 ms)