1完、29:37。
各問題
A - Trailing Zeros
以下、0オリジンで。
- xに対して、T_iだけ下位ビットを0で埋める
ctz(A_i) = T_i
を満たすため
- xに
2^T_i
を加算する- 0埋めした後のxは元のx以下なので、狭義単調増加の条件を満たすため
- 演算後の数値は少ないに越したことはないので、末尾のT_i個を0埋めした数値で最も小さい
2^T_i
を加算
- T_iビット目が0だった場合、それを1にする
ctz(A_i) = T_i
を満たすため
以下をNまで繰り返してできたxが答えです。
B - Make N
ARCの500だし、そんな解法でいけるわけないようなぁと思いながら貪欲っぽいものを投げるも、案の定WAでした。
しかも予想外にWAが多い(35/36がWA)し、順位表を見ても全然解かれていないので、ほぼほぼ諦めの状態でした。
まとめ
ARCの500点問題がさっぱり解けないようになってしまいましたなぁ...。