情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

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

まず、N = aK + b(0 \leq b < K)とします。
この時、全員にa枚配ってもせんべいの枚数の差は0なので配ってしまうと、残りはb枚になります。
ここでb=0ならば差は0枚であり、b>0ならばb人に1枚ずつ配ることで差を1枚にできます。
よって、答えはN \mod Kが0ならば0、そうでないなら1です。

B - Cakes and Donuts

全通り試せば良い話ですが、ちょっと考え方を変えてみる方法を紹介します。
まず、Nドルとなる買い方がある⇔N=4a+7b(0 \leq a, b)を満たすa, bが存在するということができます。
ここでbを固定すると、N-7b=4a、つまりN-7bが4の倍数であれば条件を満たすということができます。
またN-7(4+b)が4の倍数であればN-7bもまた4の倍数ですから、N \geq (4 - 1) \cdot 7 = 21については全てYesになります。
何故なら、NN-7N-14N-21は互いに素なので、どの4つも4で割った余りは異なることから鳩の巣原理よりどれか1個は4の倍数になるからです。
よって、N < 21における条件を満たさない値を調べると、これは1,2,3,5,6,9,10,13,17の9つです。
よってこの9つのみNoを、それ以外はYesを出力すれば良いです。
ちなみに、N=4a+7b(0 \leq a, b)の形で閃いた人もいると思いますが、拡張ユークリッド互除法を用いれば\rm{O}(\gcd(4,7))=\rm{O}(\log(\min(4, 7)))程度で解けます。

C - Base -2 Number

数Aで習うと思いますが、m \geq 2におけるNm進数表現は次のように導出できます。

  1. N=0ならば"0"を書いて終了
  2. N=0ならば終了
  3. Nmで割った余りを1の位に書く
  4. N-(N \mod m)mで割った値について2を適用して求め、結果を1の位の左側に結合する

例えば9を2進数で表すと次のような手順になります。

  1. 9を2で割った余りは1なので、((9-1)/2を2進数で表した値) + "1"
  2. 4を2で割った余りは0なので、((4-0)/2を2進数で表した値) + "0" + "1"
  3. 2を2で割った余りは0なので、((2-0)/2を2進数で表した値) + "0" + "0" + "1"
  4. 1を2で割った余りは1なので、((1-1)/2を2進数で表した値) + "1" + "0" + "0" + "1"
  5. 0なので終了し、答えは"1001"

これをm \leq -2についても適用できないか考えると、実は同様に解けることが分かります。
ただし、注意点として N \mod m N \mod |m|として考え、またN<0の時はN \geq 0になるまで|m|を足すものとします。
これは((N \mod |m|) + |m|) \mod |m|などとすると良いでしょう。
実際に入出力例1で試してみます。

  1. -9を-2で割った余りは1なので、((-9-1)/(-2)を-2進数で表した値) + "1"
  2. 5を-2で割った余りは1なので、((5-1)/(-2)を-2進数で表した値) + "1" + "1"
  3. -2を-2で割った余りは0なので、((-2-0)/(-2)を-2進数で表した値) + "0" + "1" + "1"
  4. 1を-2で割った余りは1なので、((1-1)/(-2)を-2進数で表した値) + "1" + "0" + "1" + "1"
  5. 0なので終了し、答えは"1011"

計算量は\rm{O}(\log N)です。

D - Candy Distribution

まず、l, rを全探索すると計算量は\rm{O}(N^3)=10^{15}より間に合いません。
ここで、まずは条件を見てみると、Mの倍数かどうかのみが条件になることが分かります。
ここでxMの倍数である⇔x \mod M = 0を利用すると、区間[l, r]の総和の \mod Mが0になることが分かります。
また、区間[l, r]を決め打ちしたときに\rm{O}(1)で導出したいので、累積和という考え方を使います。
累積和sum_i=\sum_{k=1}^i A_kとします。
この時、区間[l, r]におけるA_iの総和は\sum_{k=l}^r A_k = \sum_{k=1}^r A_k - \sum_{k=1}^{l-1} A_k = sum_r - sum_{l-1}と表すことができます。
(a+b) \mod m = (a \mod m) + (b \mod m)なことを利用すれば、予め全てのB_i \mod M上で計算して良くて、この時sum_r = sum_{l-1}ならば条件を満たすことが分かります。
さて、ここまでで計算量を\rm{O}(N^2)まで落としましたが、もう一工夫しましょう。
今回求めたいのはsum_r = sum_{l-1}となるような全てのsum_iです。
逆に、今n個のsum_iが同値だったとします。
この時、同値な全てのsum_iについて2個取り出すと条件を満たすので、答えは{}_nC_2 = (n-1)n/2となります。
ただしそのようなsum_i= 0であるならば区間[i, i]も条件を満たすので、答えは{}_nC_2 + n = n(n+1)/2となります。
ということは、sum_iについてソートしておくとこれは単調性を持つので、答えを\rm{O}(N)で求めることができます。
ソートのコストが\rm{O}(N \log N)なので計算量は\rm{O}(N \log N)となります。

感想

C問題に関しては実験及び発想力が大事で、与えられた値Nm進数上においてN=am+b(0 \leq b < |m|)と表せると気付くと、a=(N-b)/mとして再帰的に解けることに気付けると思います。
これはm進数と聞いて既存のm \geq 2の時と同じように解けないかとやってみると導出できるのではないかと思います。
D問題は類題としてAGC023_A - Zero-Sum Rangesを解いていると比較的楽に考えられたかもしれません。
何にせよ今回の問題セットはmodを如何に理解しているかのコンテストでしたね。