【二重ループ：活用編 三角形の探索】STEP: 4 log2 (paizaランク C 相当) 解答例 – PHP編【二重ループメニュー】
【二重ループメニュー】 > 【二重ループ：活用編 三角形の探索】STEP: 4 log2 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
一見簡単そうに見えて”ある罠”が仕掛けれられています。私も見事に引っかかって詰まった問題です(;^ω^)
アルゴリズムってやつなんでしょうか？解答方法を工夫しないと「テストケース3以降」で失敗する問題です。
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
<?php $input = trim(fgets(STDIN)); $counter = 0; $subcounter = 0; for($i = 1;$i <= $input;$i++){ $subcounter = 0; $test = $i; $judge = $test % 2;; if($judge == 0){ $hantei = $test % 2; while($hantei == 0){ $test = $test / 2; $subcounter++; $hantei = $test % 2; } } $counter += $subcounter; } echo $counter; ?> |
解答方針
与えられる整数Nに対し、「1 × 2 × … × (N-1) × N 」を計算してから2で割ろうとすると、テストケース3で与えられる「100」という整数で、計算結果が巨大になりすぎ、表示できる数を越えるため解答が狂ってきます。そこで次の解法で答えを導きます。
解法2 は素数であるので、1 × 2 × … × (N-1) × N を 2 で割ることができる回数は、
(1 を 2 で割ることができる回数) + (2 を 2 で割ることができる回数) + … + (N-1 を 2 で割ることができる回数) + (N を 2 で割ることができる回数) と一致する。
(1 を 2 で割ることができる回数) + (2 を 2 で割ることができる回数) + … + (N-1 を 2 で割ることができる回数) + (N を 2 で割ることができる回数) と一致する。
例えば「テストケース1」の「N = 4」の場合、
「1 は 2 で割れないので 0」 + 「2 は 2 で1回割れるので 1」 + 「3 は 2 で割れないので 0」 + 「4 は 2 で2回割れるので 2」= 3
となる訳です。このような数式を再現できれば、例え整数Nが大きくなっても答えを導けるというギミックのようです。難しい＞＜
