目次
AtCoder Beginner Contest 105
問題不足の疲れからか、黒塗りの高級車に追突してしまったため、Unratedです。
A - AtCoder Crackers
問題
- $N$ 枚のせんべいを $K$ 人になるべく均等に分ける
- 一番多くもらえる人と一番少ない人との差をなるべく小さくすると、その差はいくつか
解法
トランプなんかの札を配る時を思い出すと分かるように、均等に配ったらその差はせいぜい1枚になる。
完全に均等に配れる時のみ0枚になる。これは、$N$ を $K$ で割った余りが0になるかどうかで判断できる。
n, k = map(int, input().split()) print(1 if n % k else 0)
B - Cakes and Donuts
問題
- 1個4ドルのケーキと 1個7ドルのドーナツが無数に売られている
- 合計金額が $N$ ドルとなる買い方はあるか、判定せよ
- 1つも買わない商品があってもよい
- $1 \le N \le 100$
解法
制約が小さいので、全部試すのが楽。
ミスタードーナツは mister donuts だけど、クリスピークリームドーナツは Krispy Kreme Doughnuts。
n = int(input())
doughnuts = 0
while doughnuts * 7 <= n:
if (n - doughnuts * 7) % 4 == 0:
print('Yes')
break
doughnuts += 1
else:
print('No')
C - Base -2 Number
問題
- 10進数表記 $N$ の、「-2進数表記」を答えよ
例
-2進数表記で 11001 は、
| 位 | $(-2)^4$ | $(-2)^3$ | $(-2)^2$ | $(-2)^1$ | $(-2)^0$ |
| 16 | -8 | 4 | -2 | 1 | |
| 1 | 1 | 0 | 0 | 1 |
なので、$16+(-8)+1=9$ となる。
解法
なんか素直にやれば良さそうに見えて、手こずった結果、却ってややこしいことしてるやつ。
コンピュータにおける整数の2進数表現を考えると、負の値は、正の値のビットを全て反転させた上で1を足した値となる。
10進 2進 13 -> ...0001101 反転 -> ...1110010 -13 -> ...1110011
こうしておくと、足し算に一貫性を持たせられるからだ。
13 00001101
+ -13 + 11110011
----- ----------
0 100000000 -> 00000000
^オーバーフローで切り落とされる
で、-2進数表記で各桁の示す要素は、2進数表現で以下のようになる。
1 00000001 -2 11111110 4 00000100 -8 11111000 16 00010000 -32 11100000
この中から上手く選んで、その和が $N$ になるようにすればよい。以下、右から1桁目、2桁目 …とする。
以下のことが分かる。
- ① -2進数で $i$ 桁目に対応する要素は、2進数表記で $i-1$ 桁目以下が必ず
'0' - ② -2進数で $i$ 桁目に対応する要素は、2進数表記で $i$ 桁目が必ず
'1'
$N$ の2進数表現をもとに、-2進数表記を1桁目から確定させていくことを考える。
1桁目を考える時、①の通り、2桁目以降に対応する要素(-2,4,-8…)は2進数表記の1桁目が全て0なので、これらは後々どう選ぼうとも和には影響しない。1桁目に対応する要素(1)のみが影響するので、2進数表現が'1'なら-2進数表記も'1'、'0'なら'0'となる。
同様に、和の $i$ 桁目に影響を及ぼすのは $i$ 桁目以下のみであり、$i$ 桁目を考える時には $i-1$ 桁目までは確定済みなので、暫定結果を踏まえた上で $i$ 桁目のみ考えればよい。②の通り、$i$ 桁目に対応する要素は必ず和の $i$ 桁目に影響する。
2進数と-2進数は、負の要素を使うと異なってくる。ここで、たとえば2桁目の要素(-2)を使うことになったとする。すると暫定和でそれより左の桁は全て1が入る。
N 001101|10
使用有無
1 000000|01 0
-2 111111|10 1
------|--
111111|10 暫定和
次の3桁目が、2進数表現では'1'だったとしても、-2進数表記では既に入っているので'0'となる。
N 00110|110
使用有無
1 00000|001 0
-2 11111|110 1
4 00000|100 0
-----|---
11111|110 暫定和
逆に2進数表現で'0'なら、-2進数表記では'1'を入れて反転させる必要がある。その場合、繰り上がりが連鎖して、左の桁に入っていた'1'は、'0'に戻る。
N 00110|010
使用有無
1 00000|001 0
-2 11111|110 1
4 00000|100 1
-----|---
100000|010 暫定和
ただし反転のために加えた要素もまた負数だった場合は、$既存の1+新規の1+繰り上がりの1=11_2$ となるため、結果変わらない。
N 0011|0110
使用有無
1 0000|0001 0
-2 1111|1110 1
4 0000|0100 0
-8 1111|1000 1
----|----
11111|1010 暫定和
まとめると、
- $k$: $N$ の $i$ 桁目
- $p$: $i-1$ 桁目までの暫定和の $i$ 桁目以降が
'0'で埋まる(正)か'1'で埋まる(負)かフラグ - $d$: $i$ 桁目の要素が正(0)か負(1)かフラグ
とすると、答えの $i$ 桁目は、$k\ xor\ p$ となる。またそれが'1'だった際、$d\ xor\ p$ なら、$p$ を反転させる。
ちなみに、Pythonでは右シフトした時、一番左のビットは正負を保つように補完される(正なら'0'、負なら'1')。負数を右シフトし続けると、-1でループする。
どの桁まで続けるかの終了条件を考えると、まぁ暫定和を逐一計算して $N$ と等しいか調べてもいいのだが、$N$ を右シフトし続けた結果を $M$ として「$M=0$ かつ $p=0$」または「$M=-1$ かつ $p=1$」ならば $N$ と暫定和が合致していることになるため、それでも判定できる。
def solve(n):
if n == 0:
return '0'
ans = ''
p = 0
d = 0
while n + p:
if (n & 1) ^ p:
ans += '1'
if d ^ p:
p ^= 1
else:
ans += '0'
n >>= 1
d ^= 1
return ans[::-1]
n = int(input())
print(solve(n))
D - Candy Distribution
問題
- $N$ 個の箱が左右一列に並び、左から $a_1,a_2,...,a_N$ 個のお菓子が入っている
- $M$ 人の子供がいる
- 連続する箱を選ぶ。選んだ箱からお菓子を全て取り出し、子供たちに均等に、余りなく分け与えたい
- つまり、選んだ箱のお菓子の合計個数が $M$ の倍数となる
- そのような連続する箱の選び方は何通りあるか
解法
累積和問題。
累積和$(acc_0,acc_1,...,acc_N)$を取っておくと、$l$～$r$ 番目の箱を選んだ時の合計を $acc_r-acc_{l-1}$ で求められる。
で、それが $M$ の倍数か判定すればよいので、累積和を $M$ で割った値を求めておく。
M = 3 i 1 2 3 4 5 a 5 2 5 2 1 累積和 0 5 7 12 14 15 mod M 0 2 1 0 2 0
すると、同じ値同士の区間和は、同じ値同士を引き算するので当然 $0 \mod{M}$、つまり $M$ の倍数となる。逆に違う値同士は $M$ の倍数にならないので、求めるのは「同じ値同士の中から左端、右端の2個を選ぶパターン数」と同じことになる。
a 5 2 5 2 1
mod M 0 2 1 0 2 0
~~~~~~~~~ 5+2+5 = 12
~~~~~~ 2+1 = 3
~~~~~~~~~~~~~~~ 5+2+5+2+1 = 15
~~~~~~~~~ 2+5+2 = 9
たとえば0が3回出てくるなら、その中から2個を選ぶので、パターン数は ${}_3C_2=3(3-1)/2=3$ 個となる。
これを各同じ値につき合計したのが答えとなる。
今回の制約では、箱に1個以上のお菓子は必ず入っているので、「合計が0個の場合mod $M \equiv 0$ なのに分け与えることができない」などは考えなくてよい。
累積和（accumulate）も、数列に出てくる同じ値の個数を数える（Counter）も、Pythonでは最初から用意されているので楽ですね。
from collections import Counter from itertools import accumulate n, m = map(int, input().split()) acc = [0] acc.extend(accumulate(map(int, input().split()))) acc = Counter(a % m for a in acc) print(sum(c * (c - 1) // 2 for c in acc.values()))
