AtCoder Beginner Contest 105
AtCoder Beginner Contest 105 (ABC105) の解説です。
AtCoder Beginner Contest 105 旧版
AtCoder Beginner Contest 105 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 105
unrated
8/11(土) 21:00 ~ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分
方針
外出中のため、後で解く
A - AtCoder Crackers
まず、とします。
この時、全員に枚配ってもせんべいの枚数の差は0なので配ってしまうと、残りは枚になります。
ここでならば差は0枚であり、ならば人に1枚ずつ配ることで差を1枚にできます。
よって、答えはが0ならば0、そうでないなら1です。
B - Cakes and Donuts
全通り試せば良い話ですが、ちょっと考え方を変えてみる方法を紹介します。
まず、ドルとなる買い方がある⇔を満たすが存在するということができます。
ここでを固定すると、、つまりが4の倍数であれば条件を満たすということができます。
またが4の倍数であればもまた4の倍数ですから、については全てYesになります。
何故なら、、、、は互いに素なので、どの4つも4で割った余りは異なることから鳩の巣原理よりどれか1個は4の倍数になるからです。
よって、における条件を満たさない値を調べると、これはの9つです。
よってこの9つのみNoを、それ以外はYesを出力すれば良いです。
ちなみに、の形で閃いた人もいると思いますが、拡張ユークリッド互除法を用いれば程度で解けます。
C - Base -2 Number
数Aで習うと思いますが、におけるの進数表現は次のように導出できます。
- ならば"0"を書いて終了
- ならば終了
- をで割った余りを1の位に書く
- をで割った値について2を適用して求め、結果を1の位の左側に結合する
例えば9を2進数で表すと次のような手順になります。
- 9を2で割った余りは1なので、((9-1)/2を2進数で表した値) + "1"
- 4を2で割った余りは0なので、((4-0)/2を2進数で表した値) + "0" + "1"
- 2を2で割った余りは0なので、((2-0)/2を2進数で表した値) + "0" + "0" + "1"
- 1を2で割った余りは1なので、((1-1)/2を2進数で表した値) + "1" + "0" + "0" + "1"
- 0なので終了し、答えは"1001"
これをについても適用できないか考えると、実は同様に解けることが分かります。
ただし、注意点としてはとして考え、またの時はになるまでを足すものとします。
これはなどとすると良いでしょう。
実際に入出力例1で試してみます。
- -9を-2で割った余りは1なので、((-9-1)/(-2)を-2進数で表した値) + "1"
- 5を-2で割った余りは1なので、((5-1)/(-2)を-2進数で表した値) + "1" + "1"
- -2を-2で割った余りは0なので、((-2-0)/(-2)を-2進数で表した値) + "0" + "1" + "1"
- 1を-2で割った余りは1なので、((1-1)/(-2)を-2進数で表した値) + "1" + "0" + "1" + "1"
- 0なので終了し、答えは"1011"
計算量はです。
D - Candy Distribution
まず、を全探索すると計算量はより間に合いません。
ここで、まずは条件を見てみると、の倍数かどうかのみが条件になることが分かります。
ここでがの倍数である⇔を利用すると、区間[l, r]の総和のが0になることが分かります。
また、区間[l, r]を決め打ちしたときにで導出したいので、累積和という考え方を使います。
累積和とします。
この時、区間[l, r]におけるの総和はと表すことができます。
なことを利用すれば、予め全てのを上で計算して良くて、この時ならば条件を満たすことが分かります。
さて、ここまでで計算量をまで落としましたが、もう一工夫しましょう。
今回求めたいのはとなるような全てのです。
逆に、今個のが同値だったとします。
この時、同値な全てのについて2個取り出すと条件を満たすので、答えはとなります。
ただしそのようなであるならば区間[i, i]も条件を満たすので、答えはとなります。
ということは、についてソートしておくとこれは単調性を持つので、答えをで求めることができます。
ソートのコストがなので計算量はとなります。
感想
C問題に関しては実験及び発想力が大事で、与えられた値は進数上においてと表せると気付くと、として再帰的に解けることに気付けると思います。
これは進数と聞いて既存のの時と同じように解けないかとやってみると導出できるのではないかと思います。
D問題は類題としてAGC023_A - Zero-Sum Rangesを解いていると比較的楽に考えられたかもしれません。
何にせよ今回の問題セットはmodを如何に理解しているかのコンテストでしたね。