AtCoder Regular Contest 139 参加記

2022/4/24に開催されたAtCoder Regular Contest 139に参加しました。

土曜のABCでは、いろいろやらかしてしまい2完爆死という結果でした。

今回は少しでも昨日の負けを取り戻せるようにという気持ちで臨むこととしました。

Rated参加します。昨日のABCでは2完で爆死しましたので、取り戻せるように頑張ります✊

AtCoder Regular Contest 139 - AtCoder https://t.co/0x5wMzlUEY
— devgenjin77 (@devgenjin77) 2022年4月24日

今回の結果

で、今回はなんとか1完を確保したという結果となりましたとさ。

しかしながら、今回はB問題がやたらと難しかったのか、1完でも水パフォが出てくれて、昨日の負けを少し取り戻すことが出来ました。

1完でも水パフォ出ました😂
devgenjin77さんのAtCoder Regular Contest 139での成績：880位
パフォーマンス：1249相当
レーティング：1016→1042 (+26) :)#AtCoder #ARC139 https://t.co/HevBtJmVGE
— devgenjin77 (@devgenjin77) 2022年4月24日

振り返り

Bは途中であきらめてしまいました。

A問題

A - Trailing Zeros

とりあえず、整数を $2$ 進表記したときの末尾の $0$ の個数が重要になるので、シフト演算処理で考えれば単純化できるかという印象でした。

とりあえず、サンプル4の入力について、ノートに愚直に計算結果を書いていった結果、見えてきた解法は以下の通り。

初期値 $A_1$ を、 $1$ を $T_1$ ビット分左シフトした値とする。
$T_{i+1} = T_i$ の場合、 $A_i$ を $T_i$ ビット分右シフトし、2を足した後、 $T_i$ ビット分左シフトした値を $A_{i+1}$ とする。
$T_{i+1} \lt T_i$ の場合、 $A_i$ に $1$ を $T_i$ ビット分左シフトした値を足した値を $A_{i+1}$ とする。
$T_{i+1} \gt T_i$ の場合、 $A_i$ を $T_i$ ビット分右シフトし、シフト後の値の末尾が0の場合1を、末尾が1の場合2を足す。その後、 $T_i$ ビット分左シフトした値を $A_{i+1}$ とする。