Open2
AtCoder Beginners Selectionの別解の勉強メモ
こどはざ第 3 問 : ABC081B - Shift only
Bitwiseで解く別解に関心。
ビット演算が非常に効果的に働くケースもあるけど、この問題も工夫で演算処理を縮められる。
- 2で割れるか？
- 奇数か？(=2で割れないか)
などの処理はビット演算で簡単に出来るし、大量の整数の配列を処理しながら偶数奇数の判断を求められる問題に出くわしたら、ビット演算のケースについても考えたい。
今回は、
- 入力がすべて正の整数の配列
- すべての数を2で割り続けられる最小の回数を求める
- ビット演算なら右から数えて最短で1が立っている箇所を求める
ということがポイントで、結果すべての整数入力を | でOR演算することで最短のビットを1つの整数で表現できてしまった。
あとは立っているビットに出くわすまで num >> 1 し続けるだけ。
目からウロコだった。
こどはざ第 4 問 : ABC087B - Coins
int res = 0; // 回答
for (int a = 0; a <= A; ++a) {
for (int b = 0; b <= B; ++b) {
int part = a * 500 + b * 100; // ここまでの合計金額
if (X >= part && X - part <= C * 50) ++res;
}
}
3重ループで500円、100円、50円の枚数を求めていたが、合計金額は50の倍数ということが約束されているため、2重ループで解決できた。
大きい金額からそれぞれA,B枚使うとして、AとBを決定した時点で合計を超えていないか比較。超えていないかつ50円xC枚以下の金額なら払い切れるのでOK（この処理にループが不要）。
ピッタリではなく超えていればOK というところを見落としていた。
さらに別解の話
O(AB)で解ける解法も目からウロコだったが、O(A)の解法もO(1)の解法もあるらしい。
O(A)について解説を3日ほどかけて考えてみたが、理解度半分くらいで終わってしまった。
もっと勉強して戻ってきたらすんなり理解できるだろうか。
int res = 0; // 回答
for (int a = 0; a <= A; ++a) {
int rem = X - a * 500; // 残金
res += max(0, min(rem / 100 + 1, B + 1)) // 区間の上端
- max(0, min((rem - (C - 1) * 50) / 100, B + 1));// 区間の下端
}