🔖

AtCoder Beginner Contest 343 C - Repunit Trio 備忘録 PHP

2024/05/22に公開

PHP

AtCoder

tech

PHPで解いています。

問題はこちら。

解のポイント

この問題の肝は「レピュニットの桁数の上限」を概算でいいから出せるか？
にあります。

実は親切にも入力例3にNの上限である333の場合の回答が記載されています。
↓
112222222233
つまり12ケタまでのレピュニットを使うことになる。

3回分のループで数字を組み合わせて合計を出す方法であれば
計算量は O(nの３乗)になります。

TLE（処理オーバー）になるのはnの8乗以上。
つまり３重ループで処理しても問題ない、という判断ができます。

あとは重複した値を削除し、ソートで順番に並べ、N番の値を出力すればOKです。

別の考え方
333が入力例にない場合、気づかない場合はどうするのか？と思いchatGPTに聞いてみました。
正直、解説ライブの説明がよく分からなかったので。
そうすると出てきた解答が「ありだな」と思えたのでまとめておきます。

「とりあえず作ってみる」方式

とりあえず10ケタまでのレピュニットを作って計算してみる
Nの最大値333で試す
なければ桁を1つずつ増やしてみる
↓
なるほど、これなら数弱でもいける…！

ところでなぜ10ケタスタートなのか？

10ケタなら10個のレピュニットができる
10 * 10 * 10つまり1000通りとなり、重複を排除してもかなりの数が残るのは予想できる。
Nの上限は333。つまり333個以上の和ができれば事たりる。その数が出るまで調整をつづけていけばいい

全体コード

<?php

$n = trim(fgets(STDIN));

$numbers = [];
for ($i = 1; $i <= 12; $i++) {
  $numbers[] = intval(str_repeat("1", $i));
}

$sum_list = [];

foreach ($numbers as $a) {
    foreach ($numbers as $b) {
        foreach ($numbers as $c) {
            $sum = $a + $b + $c;
      $sum_list[] = $sum;
        }
    }
}

$sum_list = array_unique($sum_list);
sort($sum_list);

echo $sum_list[$n-1] . "\n";

解のポイント

全体コード

Discussion