カメヲラボ

主にプログラミングとお勉強全般について書いてます

少ない重りで重さを量ろう【解説】

  • 本稿はCodeIQで出題された 第1回プロコン:【雉】くそ生意気な雉を黙らせよう という問題の解答例と簡単な解説です。

  • 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の言語で書いてみたよ!」という場合は、自由にコメントに書いていただいても、個人のブログ等で公開していただいても結構です。

問題本文はこちら

少ない重りで重さを量ろう【解説】

◆解説

1つひとつの分銅には、「左に置く」「右に置く」「置かない」という3つの選択があります。つまりn個の分銅を用いると、3n通りの置き方があります。ただし、1つの分銅を左に置く場合と右に置く場合で量ることのできる重量は変わりませんから、左右の違いは1つのペアと考えなければなりません。
たとえば、AとBの2つの分銅を使って、左にA・右にBを乗せる場合と、左にB・右にAを乗せる場合とでは、量ることのできる重量は同じです。左にAB・右はナシの場合と左はナシ・右にABの場合も同じ重量です。唯一ペアにならない(ペアが存在しない)のは、おもりを1つも乗せない場合です(左に乗せないや右に乗せないとは言いませんね)。 以上から、n個の分銅を用いて表すことのできる0以上の連続する整数値は、最大で(3n – 1) / 2と表すことができます。

◆解答例

#!ruby
n = STDIN.gets.to_i
m = 1

while (3**m-1)/2 < n
  m += 1
end

puts m

◆補足

本問の解答には必要ありませんが、n個の分銅の質量は、3n-1グラムにします。たとえば、分銅を2つ用意する場合、1グラム(A)と3グラム(B)にすると、

  • 乗せない…0グラム
  • Aだけ乗せる…1グラム
  • 一方にA、もう一方にBを乗せると…3-1=2グラム
  • Bだけを乗せる…3グラム
  • 一方にAB両方を乗せる…3+1=4グラム

のように4グラムまで表すことができ、(32 - 1) / 2の値と一致します。分銅を3つ用意する場合、1グラム(A)、3グラム(B)、9グラム(C)にすると、先程の0~4グラムに加えて、

  • 一方にC、もう一方にAB…5グラム
  • 一方にC、もう一方にB…6グラム
  • 一方にAC、もう一方にB…7グラム
  • 一方にC、もう一方にA…8グラム
  • 一方にだけC…9グラム
  • 一方にだけAC…10グラム
  • 一方にBC、もう一方にA…11グラム
  • 一方にだけBC…12グラム
  • 一方にだけABC…13グラム

のように、13グラムまで表すことができ、(33 - 1) / 2の値と一致します。