ARC139 参加記録
コンテスト中AC:A
A - Trailing Zeros
説明のため、二進数10桁しかないと仮定します。
例えば、の時、
??????1000となり、?の部分が未確定です。
この時、??????の部分は、000000〜111111があり得ます。
000000, 000001, ...と増加させていくと、ある境でとなり、以降全てこれが成立します。
よって、この境界は二分探索可能です。
最大何桁目まで考慮するかですが、問題文にも特に言及はなかったので64bit整数に収まるだろうと推測し、60桁としました。
ACできたので、問題なかったようです。
コンテスト後に最大桁数について考えてみました。
が最大となるのは、
かつ、
がいずれも40の場合だと思います。
100...0が0〜41桁目までありますが、一旦無視して42桁目以降を考えます。
の42桁目以降は、
{00...001, 00...010, 00...011,...}という感じで+1ずつ増やしていけばが最小となるので、
の42桁目以降は
の二進数表記となっているはずです。
従って、の最大は、
99999の二進数表記 11000011010011111の17桁
と
10000000000000000000000000000000000000000の41桁
を連結させた数になります。
従って、58桁が考慮すべき最大桁数となると思います。
