はじめに
AtCoder過去問D問題にRubyで挑戦してみました。
よろしくお願いします。
問題はこちらから確認してください。↓
D - Caracal vs Monster
まずは入力を受け取ります。
その後処理に使用する変数xとx_aryという配列を準備します。
h = gets.to_i
x = 1
x_ary =[1]
実はこれの答えはある程度答えが限られています。
例えばhが2であれば答えは3です。
hが３であっても答えは3です。
もしhが4だったら答えは7です。
5でも6でも7でも答えは7です。
hが８になると答えは15です。これもhが１５までは答えは15なのです。
x_aryにmaxの1099511627775までの答えの数字を配列として入れていくのです。(10の12乗がこの数字)
先ほどのxとx_aryを利用してこれを表現します。
h = gets.to_i
x = 1
x_ary =[1]
while x != 1099511627775
x = x * 2 + 1
x_ary << x
end
ちなみにx_aryの中身は下記のようになっています。
[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775]
答えはこの中の数字でしかあり得ません。
長ったらしいですが、めちゃめちゃ時間がかかるような処理でもないと思うのでこれでいけるはずです。
続いて変数countを用意して0を代入します。
each文で配列x_aryから一つずつ取り出して、入力されたhの方が大きい限りcountに+1し続けます。ブロック変数iに代入された値がhを超えたら処理を強制的に終了させます。
x_aryの中でhよりも小さい最大の数字はx_ary[count]で表現できます。
それが答えです。
h = gets.to_i
x = 1
x_ary =[1]
while x != 1099511627775
x = x * 2 + 1
x_ary << x
end
count = 0
x_ary.each do |i|
if h > i
count += 1
else
break
end
end
puts x_ary[count]