末尾がT[i]個の0になっている整数を作っていけば良いことは分かったが、作り方の方針が誤っていた。 「2T[i] で割り切れて、2T[i]+1で割り切れない整数」と言い換えられるところは典型っぽい考え方か？ 上記の条件に加えて、「A[i-1]より大きい整数」も考慮する必要がある。
解説動画では、シフト演算で計算する考え方になっている。 基本的な考えとしては、
- A[i-1] を T[i] だけ右シフトし(2T[i]で割っている)
- 1を足し(左から(T[i]+1)番目を1とするため)
- T[i]だけ左シフトする (2T[i]で掛けている)
以上で、下T[i]桁が0となる。
ただし、2. を行った際に注意が必要で、繰り上がって末尾の 0 が増えてしまう場合がある。
例えば 1011 に 1 を足すと 1100 となってしまい、3. の操作をすると 110000 となって 0 が増えてしまう。この場合は、 1 をもう一度足して 1101 とする必要がある。
上記の手順に加えて、
2.1. 一番左の桁が 0 の場合は、1を足す
が必要となる。
以上の手順を、テキスト解説で行っている計算にマッピングしてみる。
y1 の計算は、手順 1. と 2. と 3. の計算と同様。 y2 の計算は、手順 2.1 の計算を無条件に行っている。 最後に、y1 と y2 の一方のみが 2T[i]+1 で割り切れないようになっているので、割り切れない方を選んで A[i] とする。
どうすれば解けていたかの考察
2進数での計算の性質に関する理解が少なかったことが要因。
- 「2T[i] で割り切れる かつ 2T[i]+1 で割り切れない整数を求める」という言い換え力
- A[i-1] から算出するためのビット計算方法の考案力
あたりが不足していたと考えられる。
