AtCoder Beginner Contest 182 C,D,E,F問題メモ
C - To 3
問題
解法
$N$ が大きい場合は各桁の和が3の倍数となることを利用する方法が速いが、
今回はたかだか18桁しかないので、実際に全部試してもよい。
Pythonなら itertools.combinations(リスト的なもの, k)
で、
リスト的なものから $k$ 個選ばれる全パターンのイテレータを得られる。
並び順も元のリスト的なものの状態が保たれている。
Python3
from itertools import combinations
def solve(n):
for r in range(len(n), 0, -1):
for m in combinations(n, r):
if int(''.join(m)) % 3 == 0:
return len(n) - r
return -1
n = input()
print(solve(n))
D - Wandering
解法
累積和と累積MAXを同時に使う面白い問題。
$i$ 回目の「操作」を「$A_1$ 進み、$A_2$ 進み、…、$A_i$ 進む」行為とし、$j$ 回目の「移動」をその操作中での「$A_j$ 進む」行為のことを指すとする。
「$C_i$: $i$ 回目の操作の前と後でどれだけ(正の向きに)進むか」は、$A_1+A_2+...+A_i$ なので各 $i$ についての値を累積和で求められる。
また、$i$ 回目の操作の移動中に「$D_i$: 初期位置から最大いくつ進んだ座標まで訪れることがあるか」というのは、
$\max(A_1,A_1+A_2,A_1+A_2+A_3,...,A_1+A_2+...+A_i)$
なので、“累積和の累積MAX”で求められる。
「今まで進んだことのある最大座標 $p$」「操作後の座標 $q$」を持ち、各操作毎に、
として $p,q$ を更新していくと、$p$ が答えとなる。
Python3
import sys
from itertools import accumulate
n, *aaa = map(int, sys.stdin.buffer.read().split())
acc = list(accumulate(aaa))
acc_max = list(accumulate(acc, func=max))
ans = 0
x = 0
for i in range(n):
inter = acc_max[i]
ans = max(ans, x + inter)
x += acc[i]
print(ans)
E - Akari
問題
$H \times W$ のマス目
$N$ 個の電球と $M$ 個のブロックが置かれている
電球は、ブロックに阻まれるまで、上下左右の 4 方向に光を放つ
マス目上のブロックの置かれていないマスのうち、電球の光が届くものの数を求めよ
$1 \le H,W \le 1500$
$1 \le N \le 5 \times 10^5$
$1 \le M \le 10^5$
解法
Eにしては、素直に調べるだけ、という印象。
一応、上下左右に照らされるマスを調べる過程で、それ以上調べる必要の無い条件をはっきりさせて打ち切らないとTLEになる、という工夫は必要。
○:照明 ■:壁 ─:光線
──①───②───■
このような時、各照明(①)から上下左右に照らされるマスを1マスずつ調べるが、
たとえば右方向に調べて他の照明(②)にぶつかったら、それよりさらに右は②を調べる過程で調べられるので、①からはこれ以上調べる必要は無い。
そうすることで同じマスを何度も調べること無く、$H \times W$ の各マスを、同じ方向ではせいぜい1回だけ調べればよくなる(全体で4方向なのでせいぜい $4HW$)。
また、制約を見ると照明より壁の方が数が少ないので、壁から調べることもできる。
外周を含めた各壁から同様に上下左右に調べて、他の壁または照明にぶつかったら打ち切る。
ここで探索されたマスは、たとえば左方向への探索では、「右から照らされることは無いマス」と言える。
・・○・・■・・・■・・
↑↑ ↑↑↑
右方向から照らされることは無いマス
上下左右どの方向からも照らされることは無いマスが最終的に照らされないマスとなるので、全体から引けばよい。
Python3
import os
import sys
import numpy as np
def solve(inp):
h, w, n, m = inp[:4]
aaa = inp[4:4 + 2 * n:2] - 1
bbb = inp[5:4 + 2 * n:2] - 1
ccc = inp[4 + 2 * n::2] - 1
ddd = inp[5 + 2 * n::2] - 1
field = np.zeros((h, w), np.int8)
for i in range(n):
a = aaa[i]
b = bbb[i]
field[a, b] = 1
for i in range(m):
c = ccc[i]
d = ddd[i]
field[c, d] = -1
kabe = np.zeros((h, w), np.int8)
for i in range(h):
j = 0
while j < w and field[i, j] == 0:
kabe[i, j] += 1
j += 1
j = w - 1
while j >= 0 and field[i, j] == 0:
kabe[i, j] += 1
j -= 1
for j in range(w):
i = 0
while i < h and field[i, j] == 0:
kabe[i, j] += 1
i += 1
i = h - 1
while i >= 0 and field[i, j] == 0:
kabe[i, j] += 1
i -= 1
for t in range(m):
c = ccc[t]
d = ddd[t]
i = c
j = d + 1
while j < w and field[i, j] == 0:
kabe[i, j] += 1
j += 1
i = c
j = d - 1
while j >= 0 and field[i, j] == 0:
kabe[i, j] += 1
j -= 1
i = c + 1
j = d
while i < h and field[i, j] == 0:
kabe[i, j] += 1
i += 1
i = c - 1
j = d
while i >= 0 and field[i, j] == 0:
kabe[i, j] += 1
i -= 1
ans = h * w - m - (kabe == 4).sum()
return ans
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', '(i8[:],)')(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit('(i8[:],)', cache=True)(solve)
print('compiled', file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
F - Valid payments
問題
$A_1$ 円玉、$A_2$ 円玉、…、$A_N$ 円玉の $N$ 種類のコインがある
$X$ 円の商品を購入する
$y$ 円払うと $y-X$ 円のお釣りが返る
以下の条件を全て満たすような支払額 $y$ が何通りあるか求めよ
$1 \le N \le 50$
$1 = A_1 \lt A_2 \lt ... \lt A_N \le 10^{15}$
$1 \le X \le 10^{15}$
解法
日常でも、なんかボケてると必要のない硬貨を渡して店員にそのまま返されることってたまにある。
ここでは、「お釣りに含まれない一番大きいコイン」で場合分けした。
入出力サンプルからいろいろ条件を探しての解法だが、公式解説にあるような解法2の方がスマート。
前処理
まず、サンプル3のように、$X$ が $A_i$($2 \le i$)の倍数なら、$A_i$ 未満のコインは使われない。
$y \equiv y-X \mod{A_i}$ なので、もしこれが0でなかった場合、支払いとお釣りに同じ硬貨が含まれてしまう。
かならず最小の硬貨が使われるよう、全体を上記を満たす最大の $A_i$ で割り、それ未満のコインはなかったものとする。
N=5 X=44 A=(1, 2, 4, 20, 100)
↓
N=3 X=11 A=( 1, 5, 25)
これで、置き換え後の $A_1=1$ は、ぴったり払う上で必ず使われることが保証される。
この置き換えは後続の計算を上手くやると不必要かもだが、思考する上で条件の見落としが減ってわかりやすくなる。
サンプル観察
サンプル2では、1,5,10,50,100のコインで198円を支払う。
支払いに含まれる お釣りに含まれるコイン
198 1,5,10,50,100 -
200 100 1
203 1, 100 5
208 1,5, 100 10
248 1,5,10, 100 50
203~248は、200円をベースとして、お釣りに含まれるコインを支払い側に順次含ませることで、お釣り側を繰り上げている感じ。
すると、細かな詰めの部分はあるとしても以下の方針がとれそう。
支払う最小のコインを $A_i$ とし、ギリギリ $X$ を超える支払額 $y_i$、その時のお釣り $z_i$ を求める
お釣り側のどのコインを支払い側に含ませて、お釣りを繰り上げるかの派生パターン数を求める
ただし、お釣りには $A_i$(以上)が含まれないようにする
これを各 $A_i$ について合計する
$A_{i-1}$ を繰り上げると $A_i$ がお釣りに含まれてしまうため、繰り上げ可能なのは $A_{i-2}$ まで。
これで求められる派生を含めた $y$ の範囲は、お釣りに $A_i$ 以上が含まれないことから「$y_i$ 以上 $X+A_i$ 未満」となる。
$y_{i} \lt y_{i+1}$ であれば、$X+A_i \le y_{i}+A_i \le y_{i+1}$ のため、$A_{i+1}$ について求める場合の範囲「$y_{i+1}$ 以上 $X+A_{i+1}$ 未満」とは被らない。
一方、$y_{i} = y_{i+1}$ の場合は範囲が丸かぶりするが、$y_{i+1}$ の方がカバー範囲が広いため、そちらでまとめて計算することとする。
派生パターンの求め方
場合分けの方針は良さそうなので、派生パターンを数える。
ざっくり考えると、$A_i$ の時には、$A_1~A_{i-2}$ をそれぞれ繰り上げるか否かの $2^{i-2}$ 通りくらいあるかな?と思う。
しかし、サンプル4は、コイン枚数の割には支払い方が21種類と意外と少ない。
数字の大きさにびびらず「何枚で次のコインに繰り上がるか」「最大コインだけで支払った場合のお釣り」を観察してみる。
X = 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840
繰り上げ
枚数 942454037 3 7 13 3 5 8 7
お釣り 414872683 2 2 12 2 4 7 6
すると、$A_4$ 以降は全て繰り上げ枚数がお釣りギリギリとなっている。
つまり、$A_3$ などを支払い側に含ませてお釣りを繰り上げようとすると、連鎖的に繰り上がって最大の $A_9$ が含まれることになる。
$A_9$ については、$A_8$ のみならず $A_3~A_7$ も全て繰り上げ不可となる。
$A_2$ もギリギリのため、結局、派生は以下の2通りしかないことになる。
また、お釣りが0枚のコインも、繰り上げられない。(繰り上げ枚数の分だけコインを追加することになり、それなら $A_{i+1}$ 1枚で払うことになる)
ただし、下の桁から繰り上がってきた1枚があれば、追加するのは(繰上げ枚数-1)枚となり、繰り上げられる。
このように、下の桁からの繰り上げの有無で遷移が変わるのは、桁DPを想起させる。
とすると、お釣りが「0枚」「繰り上げ枚数ギリギリ」「それ以外」で遷移が変化する。
お釣り
0 繰り上げギリギリ それ以外
i i+1 i i+1 i i+1
j=0 o → o o → o o → o
↗ ↘ ×
j=1 o → o o → o o → o
最終的に $A_i$ まで繰り上がってくるパターンが不可なので、繰り上がりのない $DP[i-1][0]$ が $A_i$ に対しての派生パターン数となる。
まとめると、
これを合計すればよい。ただし、$y_i=y_{i+1}$ となる $i$ については合計しない。
Python3
import sys
def solve(n, x, aaa):
min_coin = 0
for i in range(n - 1, -1, -1):
a = aaa[i]
if x % a == 0:
min_coin = i
break
if min_coin > 0:
unit = aaa[min_coin]
n -= min_coin
x //= unit
aaa = [a // unit for a in aaa[min_coin:]]
if n == 1:
return 1
carry_up = [] # 各コインは何枚使うと次のコイン1枚に繰り上がるか
for i in range(n - 1):
carry_up.append(aaa[i + 1] // aaa[i])
a = aaa[-1]
y = a * ((x - 1) // a + 1)
z = y - x
change = [-1]
for j in range(n - 2, -1, -1):
b = aaa[j]
d, z = divmod(z, b)
change.append(d)
change.reverse()
ans = 1
carried_up = 0
not_carried_up = 1
for j in range(n - 1):
if change[j] == 0:
not_carried_up += carried_up
elif change[j] == carry_up[j] - 1:
carried_up += not_carried_up
else:
carried_up = not_carried_up = carried_up + not_carried_up
if change[j + 1] != 0:
ans += not_carried_up
return ans
n, x, *aaa = map(int, sys.stdin.buffer.read().split())
ans = solve(n, x, aaa)
print(ans)
解法2
要は、「$C_1A_1+C_2A_2+...+C_NA_N=X$ となる整数の組 $(C_1,C_2,...,C_N)$ は何通りですか」という問題で、
$C_i$ が正ならその枚数だけ支払い、負ならお釣りに用いると考えると問題のシチュエーションに当てはめられる。
ただし各 $C_i$ の絶対値には上限があり、
1段階大きいコインで表現できてしまう枚数($\dfrac{A_{i+1}}{A_i}$)以上は使うことが出来ない。
この上限制約があるため、$A_1,A_2,...,A_{i-1}$ の全てを上限まで使っても $A_i$ 未満にしかならない。
また、以下のようにどちらからどちらの変換へも1通りに決まるので、$C_i$ の組と $y$ は1対1対応とわかる。
以上を踏まえて $C_i$ を $i$ の大きい方から考えると、各コイン、支払う可能性のある枚数というのは、
$X$ をちょうど払える場合、1通り
$X$ をちょうど払えない場合、以下の2通り
で、ちょうど払えない場合は端数を1段階小さいコインで表現する方法を考えれば、再帰的に解ける。
もしこれ以外の枚数だと、端数の絶対値が $A_i$ 以上ということになり、$A_1~A_{i-1}$ では表現できないため、不可能。
一見、2通りずつに分岐するので状態数が $2^N$ とかになってしまいそうだが、
実は以下のように多くの状態が同じになり、メモ化すれば $2N$ 程度にしかならない。
$X=198$ を100円で
ギリギリ足りない: 1枚→$X=98$
ギリギリ超える: 2枚→$X=-2$
$X=98$ を50円で
$X=-2$ を50円で
ギリギリ足りない: -1枚→$X=48$
ギリギリ超える: 0枚→$X=-2$
(100×1, 50×1 の支払い)と、(100×2 の支払い, 50×1のお釣り)とで、端数48が同じになる。
Python3
import sys
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i, x):
a = aaa[i]
d, m = divmod(x, a)
if m == 0:
return 1
if i < n - 1:
lim = aaa[i + 1] // a
if d > 0 and lim == d + 1:
return solve(i - 1, x - a * d)
if d < 0 and lim == -d:
return solve(i - 1, x - a * (d + 1))
return solve(i - 1, x - a * d) + solve(i - 1, x - a * (d + 1))
n, x, *aaa = map(int, sys.stdin.buffer.read().split())
ans = solve(n - 1, x)
print(ans)