ABC343 C問題（343）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）343 のC問題をC++とPythonで解いてみました。ABC343は、2024年3月2日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 343（Difficulty : 220）

問題はリンク先をご覧ください。

ABC343 C問題 343

与えられた数以下のすべての立方数を調べます。AtCoder Problems による Difficulty は 220 でした。

解答案

$1 \leqq N \leqq 10^{18}$ と $N$ の範囲は大きいですが、3乗する範囲は、$1 \leqq i \leqq 10^6$ まででよいため、$N$ 以下のすべての立方数を調べても間に合います。

C++ プログラム例（ABC343C）

回文数になっているか関数 is_OK を用意しました。与えられた整数を文字列に変換して、反転した文字列と一致しているか返します（6ー13行目）。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

bool is_OK(ull n)
{
	string s = to_string(n);
	string t = s;
	reverse(t.begin(), t.end());

	return s == t;
}

int main()
{
	ull n;
	cin >> n;

	ull result = 1;
	for (ull i = 1; i * i * i <= n; ++i) {
		ull num = i * i * i;
		if (is_OK(num)) {
			result = num;
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC343C）

Python 版も基本的な考え方は同じです。スライス表現で文字列を反転しています（7行目）。以下となります。

"""AtCoder Beginner Contest 343 C"""


def is_OK(n):
    s = str(n)

    return s == s[::-1]


n = int(input())
i = 1
result = 1
while i * i * i <= n:
    num = i * i * i
    if is_OK(num):
        result = num
    i += 1

print(result)

こちらも「AC」と判定されました。

最後に

1から100万（10⁶）の3乗の範囲で、回文立方数は14個しかありませんでした。一番小さい回文立方数は、1です。この範囲で一番大きい回文立方数は、1331399339931331 でした。

引き続き ABC の問題を紹介していきます。