AtCoder が提供しているABC（AtCoder Beginner Contest）363 F問題をC++とPythonで解いてみました。ABC363は、2024年7月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Palindromic Expression（Difficulty : 1913）
問題の詳細は、リンク先をご覧ください。
ABC363 F問題 Palindromic Expression
再帰を使って約数を全探索して、前後から式を決めます。AtCoder Problems による Difficulty は 1913 でした。
解答案
与えられた $N$ の2以上の約数に対して、
1) 文字列として反転した文字列が表す数字も約数になり
2) 数字として0を含まない
場合に、2つの約数で割った数字について、約数を再帰的に調べます。
$\sqrt{N}$ までの約数を調べればよいことと、2つの約数で割っていくため、調べる数字は速く小さくなります。結果的に、それほどの計算量ではないと予想できます。
C++ プログラム例（ABC363F）
ほとんどの実装を、再帰関数 rec として実装します。この関数は文字列を返します。
- 引数で与えられた数字が回文数なら、その回文数を返します（22ー27行目）。
- 与えられた数字の2以上の約数が、上の考察で述べた2つの条件を満たす場合は、その２つの約数で割った値を再帰関数に渡します（41行目）。
- もし、”-1” 以外の文字列が返ってきたら、両側の数字と “*” を加えて返します（43行目）。
- 条件を満たす約数が無い場合は、”-1″ を返します。
- 0を含む場合を除外するため、下請け関数 has0 を用意しました（8ー18行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
ull n;
bool has0(string s)
{
bool result = false;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '0') {
result = true;
}
}
return result;
}
string rec(ull n)
{
string t1 = to_string(n);
string t2 = t1;
reverse(t2.begin(), t2.end());
if ((t1 == t2)&& !has0(t1)) {
return t1;
}
for (ull i = 2; i * i <= n; ++i) {
if (n % i == 0) {
t1 = to_string(i);
t2 = t1;
reverse(t2.begin(), t2.end());
ull j = stoi(t2);
if ((n / i) % j != 0) {
continue;
}
if (has0(t1)) {
continue;
}
string t = rec(n / i / j);
if (t != "-1") {
return t1 + "*" + t + "*" + t2;
}
}
}
return "-1";
}
int main()
{
cin >> n;
cout << rec(n) << endl;
return 0;
}上記のプログラムでもAC判定となりましたが、メモ化再帰で計算量を小さくしたプログラムも紹介します。値の範囲が広いのでメモに map を使いました。
差分コードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
ull n;
map<int, string> memo;
bool has0(string s)
{
bool result = false;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '0') {
result = true;
}
}
return result;
}
string rec(ull n)
{
if (memo[n] != "") {
return memo[n];
}
string t1 = to_string(n);
string t2 = t1;
reverse(t2.begin(), t2.end());
if ((t1 == t2)&& !has0(t1)) {
memo[n] = t1;
return memo[n];
}
for (ull i = 2; i * i <= n; ++i) {
if (n % i == 0) {
t1 = to_string(i);
t2 = t1;
reverse(t2.begin(), t2.end());
ull j = stoi(t2);
if ((n / i) % j != 0) {
continue;
}
if (has0(t1)) {
continue;
}
string t = rec(n / i / j);
if (t != "-1") {
memo[n] = t1 + "*" + t + "*" + t2;
return memo[n];
}
}
}
memo[n] = "-1";
return memo[n];
}
int main()
{
cin >> n;
cout << rec(n) << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC363F）
Python版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 363 F"""
import math
def rec(n):
t1 = str(n)
t2 = t1[::-1]
if t1 == t2 and "0" not in t1:
return t1
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
t1 = str(i)
t2 = t1[::-1]
j = int(t2)
if (n // i) % j != 0:
continue
if "0" in t1:
continue
t = rec(n // i // j)
if t != "-1":
return t1 + "*" + t + "*" + t2
return "-1"
n = int(input())
print(rec(n))Python では、デコレータを使って、メモ化再帰が簡単に実現できます。具体的には、2行追加するだけです（2、6行目）。以下となります。
"""AtCoder Beginner Contest 363 F"""
import functools
import math
@functools.cache
def rec(n):
t1 = str(n)
t2 = t1[::-1]
if t1 == t2 and "0" not in t1:
return t1
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
t1 = str(i)
t2 = t1[::-1]
j = int(t2)
if (n // i) % j != 0:
continue
if "0" in t1:
continue
t = rec(n // i // j)
if t != "-1":
return t1 + "*" + t + "*" + t2
return "-1"
n = int(input())
print(rec(n))どちらも「AC」と判定されました。
実行時間の比較
試行回数は1回ですが、実行時間は以下となりました。特にC++版は、メモ化なしでも制限時間と比較して、十分に短い時間で実行できました。
| C++版 | Python版 | |
| メモ化無し | 49ms | 563ms |
| メモ化有り | 13ms | 156ms |
フィボナッチ数列を再帰的に求める場合、メモ化をしないと計算量が爆発的に増えます。この問題の場合は、それほどの差はでませんでした。重複する約数がそれほど多くないと思われます。
最後に
公式解説を参考に記事にしました。難易度が高い問題でしたが、自分には理解しやすかったです。
引き続き ABC の問題を紹介していきます。
