🐕

AtCoder Beginner Contest 343 C - 343 備忘録 PHP

2024/05/16に公開

PHPで解いています。

感想：
解けなかったので解説をみながら考え工夫してみた。
難易度は中より上の部類（by AtCoderProblems）
問題文の「回文立方数」は初めて聞いたのでそれだけで逃げ出したくなった問題。
しかし意味を知ると複雑ではない。
教訓→はじめての言葉でもネットで調べて挑戦してみよう

解のポイント

xの３乗 = K <= N
一番最初に思いつくのは
N以下の数をmaxから順番に「回文かどうか？」を判定していく方法。

それだと案の定、計算量オーバーになる。

左側のxの３乗、つまりx**3に目をむける。

x**3＜Nなのでxは少なくとも3分の1の数
つまりNの最大値である1018の3分の1 106まで照合していけばいいのでは？
それならできそう

という事でxに目をむけて解いていく。

回文のチェックは

数字を文字列にする
リバースする
元の文字列とリバースしたものを比較しイコールなら回文判定

という流れで行う。
また回文の最大のものを出力するので判定は配列の後列から行い見つかった時点で終了とした。

このチェックもやった事なく初見で考えつくのはなかなか難しいと思うので、色々なパターンになれてアイデアを解法の糸口をインプットしておくのが大事だと思う。

全体コード

170ms
処理は特別早くもないのでもっと短縮したい所。


<?php
$n = trim(fgets(STDIN));

$i = 1;
$array = [];// 平方数を格納する配列
while(true){
  $s = pow($i, 3);  
  if($s > $n){
    break;
  }
  $array[] = $s;
  $i++;
}

$array = array_reverse($array);

foreach($array as $val){
  if($val == strrev($val)){
    echo $val . PHP_EOL;
    exit;
  }
}

解のポイント

全体コード

Discussion