今年に入って基本的なアルゴリズムの勉強としてatcoderのコンテストにチャレンジしている。勉強ついでのアウトプットとしてこちらの問題についてメモ。
https://atcoder.jp/contests/abc242/tasks/abc242_e
問題自体は、アルファベットのみの文字列Sに対し特定の文字列と比べて辞書順で小さい回文のパターン数を数えるというもの。解説はこちらに上がっている。
https://atcoder.jp/contests/abc242/editorial/3516
全体として考えるべきことは
- 文字列の中央の文字までを決めれば回文は一意に定まる
- 文字列Sと中央の文字までが一致している回文S'を比べて、S < S'であればその1パターンのみ差し引く
1.については回文なので当然そうなる。2.については以下のような話
- S = BCDCAの場合、S' = BCDCBであり、辞書順比較でS < S'となっているためS’は条件を満たさない
この場合、最初の3文字が辞書順でBCD以下である5文字の回文のパターン数をすべて数えて、最後に条件を満たさなかった1パターンのみ引けば求めたい答えとなる。
解説コードの中の22~26行目に実際にすべての回文のパターン数を計算する処理があり、最初見たときにすぐ理解できなかったため整理してみた。
int last=(n-1)/2;
for(int i=0;i<=last;i++){
cres*=26;
cres+=(s[i]-'A');
}
cres++;
ちなみに
- nは文字列の長さ
- cresは計算結果のパターン数
- cresは0で初期化済み
- (今回の話の本筋から外れるためmodの計算処理は削除してある)
上で出した例と同じでS = BCDCAだと仮定して考えてみる。 中央の文字までを考えればよいので辞書順でBCD以下の3文字の文字列の全パターンを計算すればよい。
| 0文字目 | 1文字目 | 2文字目 |
|---|---|---|
| A | [A-Z] | [A-Z] |
| B | A,B | [A-Z] |
| B | C | A,B,C,D |
- 最初がAなら1, 2文字目はどのアルファベットが来ても辞書順で小さいという条件は満たせる
- 最初がBの場合でも1文字目がA,Bのどちらかなら2文字目はなんでもOK
- BCと続いた場合は2文字目に取れるのはA~Dまでの4つのみ
という感じ。なので
cres = ('B' - 'A') * 26 * 26 + ('C' - 'A') * 26 + ('D' - 'A')
と計算できることになる。A~(n文字目までのアルファベット)までの数をa(n)とすると
cres = a(0) * 26^2 + a(1) * 26 + a(2)
= 26 * ( 26 * a(0) + a(1) ) + a(2)
となるため、ここで解説コードのforループの中身と上記のカッコの中身が対応していることがわかった。直前のループで計算されたカッコの中の値がcresとして保持されて次のループで使われるという形。
a(0)側から順に和を取ろうとすると指数の計算に無駄が出るので、a(n)を求めておいて後ろから順に和を取っていけば同じ計算量でできそう。
