ABC解説

ABC343 C問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが開催している、競技プログラミングコンテストのことです。

今回はABC343のC問題を解説していきます。

ABC343　C – 343

問題

問題

N以下の正整数であって回文立方数であるものの最大値を求める問題です。

回文立方数とは、回文数であり、立方数でもある数のことです。なお、回文数とは、前から読んでも後ろから読んでも同じである数のことであり、立方数とは、ある正整数の3乗である数のことです。

制約

  • \(1 \leqq N \leqq 10^{18}\)

思考の筋道

Nには\(10^18\)以下という制約があります。そのため、3乗根は\(10^6\)以下であることが保証されています。10^6個であれば、その3乗が回文数になっているかを一つずつ調べることが可能です。求めたいのは最大値のため、大きい方から調べていけばよいでしょう。

なお文字列 word が回文であるかどうかは、条件 word == word[::-1] によって調べられます。

以上が大筋、ここからは気をつけるべき話です。

Nの3乗根を求める際に誤差が発生することがあります。

例えば、1030301は101の3乗なのですが、3乗根を調べると100.99999999999997となります。これを切り捨てると100となります。100以下の数を調べるのでは、101が対象から漏れてしまいます。これではいけないので、3乗根を整数値にする際は、切り捨てではなく切り上げを行いましょう。

その結果、3乗した数がNを超える可能性がありますが、それは条件分岐で除けばよいです。

（第343回にふさわしい問題ですね）

コード

import math
N = int(input())

n = math.ceil(N ** (1 / 3))
for i in reversed(range(1, n + 1)):
    word = str(i ** 3)
    if i ** 3 <= N and word == word[::-1]:
        print(i ** 3)
        exit()

リンク

ABC343