Go言語で挑む競プロ #11

前回はこちらから。

また、結構間が開いてしまった...
最近は、忙しくて時間が無いせいにするより、体力と気力をつけるべきかもと少し思ってたり...
なんとかして問題解いたり、noteに投稿する時間が欲しいなぁ。

まぁそれは置いておいて、今回も問題を解いていくぞー！

ABC083Cの問題

問題文
高橋君は、日頃の感謝を込めて、お母さんに数列をプレゼントすることにしました。
お母さんにプレゼントする数列 A は、以下の条件を満たす必要があります。
A は X 以上 Y 以下の整数からなるすべての 1≤i≤|A|−1 に対し、Ai+1 は Ai の倍数であり、かつ Ai+1 は Ai より真に大きい高橋君がお母さんにプレゼントできる数列の長さの最大値を求めてください。

制約
- 1≤X≤Y≤10^18
- 入力は全て整数である

アルゴリズム

今回の問題は、C問題？って感じの簡単な問題だね。シンプルに考えてみたらこんな感じ。

1. X,Yを受け取る
2. i=1、Ai＝Xとする
3. AiがYを超えているならば手順6へ
4. Ai+1=2*Aiとする
5. i = i + 1とし、手順3に戻る
6. iの値が解答となる

これで問題ないはず。
数列の要素を作ってみて、それがYを超えたら現在の要素数を解答する流れ。

手順で数列の値に2をかけた値を次の値としているのは、以下の2つの条件を満たす最小の整数になるから。

1. Ai+1 は Aiの倍数
2. Ai+1 > Ai

かけることにより値が大きくなる最小の整数といえば2だねってことでかけている。

ということで、考えたアルゴリズムを擬似コードに落とすとこんな感じ。

i := 0
ai := X
for ai <= Y {
    ai = 2 * ai
    i = i + 1
}

あとは、これに入出力処理をつけて完成～！

解答

最終的には、以下のようなコードに。

package main

import "fmt"

func main() {
    var x, y int
    fmt.Scan(&x, &y)

    ans := 0
    a := x
    for a <= y {
    	ans++
    	a *= 2
    }

    fmt.Println(ans)
}

今回の問題は、歯ごたえがなかったなぁって感じ。今までのC問題に比べて簡単め。
とてもシンプルな問題だし、シンプルなアルゴリズムになった。

ってことで、次はもう少し考えがいのある問題がいいかな。
さぁ、次回も頑張ろうっと。