ABC105
今回もunratedでした！(結局全体でunratedになったみたいです)
A - AtCoder Crackers
提出コード
nがkで割り切れるとき、最大と最小が1ずれるので1を出力します。割り切れないとき、n人に均等に配ることができるので0を出力します。
トランプのカードを全員に配ることを考えてみると最後どうなっているかわかると思います。
B - Cakes and Donuts
提出コード
ABぐらいの問題のコード量でバグを抱えるのすごい悲しいです…気を付けたいところです
4円のものを買う個数を0から増やしていったときに、残りを7円の品物で埋め尽くすことができるかどうかを調べます。
1つでもできればこたえはYesになります。
C - Base -2 Number
提出コード(時間外)
難しく考えすぎました。
まず、一般的なn進数について考えます(今回は2進数で考えます)
例えば10進数での14を2進数になおすとき、
2進数の一番下の位は、
- 10進数が奇数なら1、偶数なら0
となっているので、今回は0になります。
それ以降の桁は、少なくとも2の倍数(、
…)であるため、14を2で割ってあげると7になり、7を2進数になおす問題に帰着できます。
7は奇数なので一番下の位は1になり、残りは6になります。また、これを2で割って…という作業を、元の数が0になるまで繰り返すと、最終的に1110という答えになります。まとめると、
一番左の位に、元の数が奇数なら1、偶数なら0を加える
奇数だったら元の数から1を引く
元の数を2で割る
1~3を、元の数が0になるまで繰り返す
-2進数の場合も同様です。(-2)を一つのくくりとしてあげれば同じことが言えるので、
一番左の位に、元の数の絶対値が奇数なら1、偶数なら0を加える
1において、奇数であった場合元の数から1を引く
元の数を(-2)で割る
1~3を、元の数が0になるまでを繰り返す
という手順になります。
この方法だと、右の方の桁から決まっていくので、出力の順番には気を付けましょう。
D - Candy Distribution
提出コード
これまた大量のバグを抱え込みました。
lとrのうち、lを固定したときに条件を満たすrの数を高速で求めることができればよさそうです。
連続した部分の和が問題なので、累積和が何か使えないかということを考えます。
lを一番左端()に固定したとき、そこからの累積和をとっていくと、Mの倍数になるタイミング(
,r)が条件を満たすタイミングになります。
次に、lを二番目()に固定することを考えると、先ほどと同様に考えて、
からの累積和がMの倍数になるタイミング(
,r)が条件を満たすタイミングになります。これを最初に求めた累積和を利用しようと考えると、(
,r)の累積和について
を引いたものが、(
,r)の累積和になることがわかります。
まとめると、
- (
,r)の累積和から(
これを時間内で計算しきるには、mapを使用して、(,r)の累積和をMでわったあまりをキーとし、その出現回数を記録しておきます。そして、それぞれのlに対し、(
,l-1)の累積和をMでわったあまりが出現する回数を足し合わせていけば答えになります。
lを移動させるたびに、(,l)についての情報をmapから削除するのを忘れないようにしましょう。
というわけでABD3完でした。まぁこれが今の実力、って感じのコンテストでした～…
