競プロ初心者の秘密ノート 1.Atcoder Beginner Contest 081B - Shift only
この記事はコンテスト参加歴二回の競技プログラミング初心者の僕が
解いた問題を解説することで理解しているかを確認する。 という目的で書くものです。
これはどんな処理なのか。なぜ、その処理を行うのか。を明確にするのが目標です。
用語、組み込み関数などプログラミングに関する知識が無に等しいのでそのあたりも。
1.Atcoder Beginner Contest 081B - Shift only
問題
黒板に NN 個の正の整数 A1,…,ANA1,…,AN が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます
・黒板に書かれている整数すべてを，2 で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．
【解法】
けんちょんさんの写経になっております・・・
無限ループから抜け出す方法が思いつかなかったんや。
けんちょんさんはQiitaなどで競プロ等の記事を書いている方です。初心者向けの記事もいくつかあり、どれも本当に丁寧に解説して下さっているので、僕はとても助かっています。ありがとうございます。
方法としては
１、数字が何個書かれているか受け取る。
２、書かれている数字を受け取る。
３、問題文から、書かれた数字が偶数である限り操作を続ける必要があるので
ループさせます。何度ループさせれば良いかこの時点では分からないので
無限に回します。
４、bool型を使います。
bool型はture(1)かfalse(0)しか値を持つことができません。
ここでは、奇数があるかどうかを判定するのに使います。
あればture、無いならfalseです。
なぜ、偶数ではなく奇数を見つけるのかと言うと、奇数がある時点で
操作が行えないからです。ループの終わりが明確になるんですね。
最初は奇数があるか分からないので、falseにしておきます。
５、for文で書かれた数字が偶数であるかどうか判定をしていきます。
１つずつ調べます。全探索です。
奇数があった場合、先程のbool型の値をtureにします。
６、ループを抜けるための処理です。
奇数があるときにループから抜け出せるようにします。
if文は条件式がtureの時だけ後に続く処理を行います。
このためにboolを使う必要があったんですね！
（別にboolじゃなくてもできるけど）
breakを使うことでループから抜け出します。
７、ここからは奇数がなかった場合の処理です。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき
次の操作を行うことができます．
・黒板に書かれている整数すべてを，2 で割ったものに置き換える．
と、あるのでfor文ですべて2で割ったものに置き換えます
８、操作が行われた回数をカウントします。
６、の後ならどこでもいいです。
【別解】といってもほとんど同じですが
可読性が消えた（）
上の７を５の下に持ってきただけ。
与えられた数を２で素因数分解して、２の最小個数を数えれば解けるのではと思ったのが間違いだった。全然できなくて時間が消えました。人間には簡単にできても機械にやらせるのは難しい。
