ABC 401-500/ABC414C - Palindromic in Both Bases - 競技プログラミング用 知識集積所【7/13更新】

---

問題

ABC414C

必要知識

B以下レベルの内容は省略

• 回文判定（未作成）
• 基数変換（未作成）

考え方

まず、文字列が大して長くないので、回文判定（未作成）は単純な「元のとリバースしたのが一致する」で大丈夫。
基数変換（未作成）も普通通りにやれば大丈夫。
つまり、ある数に対して「十進法でもA進法でも回文か？」を判定する関数は簡単に作れる。

問題は1からNまで全部調べる全探索（未作成）だと余裕でTLEする点。
計算量的には√Nくらいまでしか間に合わない。

そこで、10^12以下の十進法の回文をすべて生成してしまう力技を取る。
偶数桁の回文は、小さい順に

11, 22, 33, 44, 55, 66, 77, 88, 99,
1001, 1111, 1221, 1331, 1441, 1551, ……, 9779, 9889, 9999,
100001, 101101, 102201, ……

となっている。
つまり、小さいほうからk番目は、kの後ろに桁数を逆順にくっつけたものである。
ということは、ループを999999回回せば、十進法で12桁以下の偶数桁の回文数がすべてできあがる。

奇数桁の回文は、小さい順に

1, 2, 3, 4, 5, 6, 7, 8, 9,
101, 111, 121, 131, 141, 151, ……, 979, 989, 999,
10001, 10101, 10201, ……

となっている。
つまり、小さいほうからk番目は、kの後ろに桁数を逆順にくっつけたもの（真ん中はダブらせる）である。
ということは、ループを999999回回せば、十進法で12桁以下の奇数桁の回文数がすべてできあがる。

ということで、文字列の結合等をうまく使って12桁以下の回文数1999998個を全て生成し、それぞれN以下のA進法回文数かどうか判定していけばいい。
（最初に用意するつもりだった関数に、十進法回文判定は不要だったことがわかる）

解答例

解答例

注意点

n=10^12という入力を警戒する

入力は最大12桁……と見せかけて、実は1つだけ13桁の入力がある。
「13桁の入力の場合でも、13桁の10進数回文は存在しないから12桁までの調査で大丈夫だな」と確認してからやること。

別解