目次
九州大学プログラミングコンテスト2018 B～E
B - Tapu & Tapi
問題
- $A$枚の100円玉と$B$枚の10円玉と$C$枚の1円玉
- 等しい金額を2人に分けられるか判定せよ
解法
満点制約は $0 \le A,B,C \le 10^9$ なので、全探索は無理。
1種類ずつ考える。
100円玉を分けられるだけ分けて1枚余った時（$A$が奇数）、1枚を片方にあげると、もう一人には10円と1円で100円分を用意してあげなければならない。（足りないなら無理）
100円玉について解決してから、10円玉を分けられるだけ分けて1枚余った時、1枚を片方にあげると、もう一人には1円で10円分を用意してあげなければならない。（足りないなら無理）
最後に1円玉を等しく分けられるか。
以上が満たされるか調べればよい。
q = int(input())
for _ in range(q):
a, b, c = map(int, input().split())
d, m = divmod(a, 2)
if m == 1:
if b < 10:
if b * 10 + c < 100:
print('No')
continue
else:
b = 0
c -= 100 - b * 10
else:
b -= 10
d, m = divmod(b, 2)
if m == 1:
if c < 10:
print('No')
continue
else:
c -= 10
print('Yes' if c % 2 == 0 else 'No')
C - Ito Campus
問題
- $H \times W$ のフィールド
'.': 更地、自由に移動できる'#': 壁、人もイノシシも移動できない、外周1マスは必ず壁'@': イノシシ、体当たりされると痛い、複数体いる'S': スタート、フィールドに1つだけある'G': ゴール、フィールドに1つだけある
- 上下左右に動いてスタートからゴールまで行く
- 「そこから$X$マス移動したらイノシシにたどり着けてしまう」マスは危険なので通ってはいけない
- 最短距離を求めよ。無理なら
'-1'を出力せよ - $4 \le H,W \le 1000$
解法
「そこから$X$マス移動したらイノシシにたどり着けてしまうマス」＝「イノシシから$X$マス移動したマス」
まずは通れるマスを明らかにする。イノシシを始点として $X$マスを上限として幅優先探索すると、たどり着けるマスが通れないマスとなる。
イノシシは何体いるか分からないが、制約上、約$1000^2$体まで配置されてる可能性がある。これらを1体1体起点として調べてたら間に合わない。
幅優先探索やDijkstraは、起点は複数あってもよい。 （ただし、FIFO制約を満たす場合。つまり、どこから出発しようと「あるマスAに遅く着いた方が、早く着くより他のマスBに早く着ける」ということが無い場合）
なので、探索キューの初期状態に全てのイノシシの座標を放り込んでおけばよい。
安全なマスが判明したら、そのマスのみを通って、今度は普通に$S$から$G$まで探索すればよい。
from collections import deque
h, w, x = map(int, input().split())
field = [[0] * w for _ in range(h)]
s, g = 0, 0
inos = deque()
for i in range(h):
for j, c in enumerate(input()):
if c == 'S':
s = (i, j)
elif c == 'G':
g = (i, j)
elif c == '@':
inos.append((0, i, j))
elif c == '#':
field[i][j] = 1
def solve(field, s, g, inos):
DXY = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while inos:
cnt, i, j = inos.popleft()
if field[i][j] == 1:
continue
field[i][j] = 1
if cnt == x:
continue
for di, dj in DXY:
ni, nj = i + di, j + dj
if field[ni][nj] == 1:
continue
inos.append((cnt + 1, ni, nj))
si, sj = s
gi, gj = g
if field[gi][gj] == 1:
return -1
q = deque([(0, si, sj)])
while q:
c, i, j = q.popleft()
if i == gi and j == gj:
return c
if field[i][j] == 1:
continue
field[i][j] = 1
for di, dj in DXY:
ni, nj = i + di, j + dj
if field[ni][nj] == 1:
continue
q.append((c + 1, ni, nj))
return -1
print(solve(field, s, g, inos))
D - Novelist
問題
- 王都が1個と地方都市が$N$個
- 王都～地方都市間を行き来する商人の護衛を出来るだけ多くこなす
- 王都から $i$ 番目の地方都市の移動は$T_i$日かかる
- 王都→地方都市への依頼が$M$件
- $i$番目の依頼は、$A_i$日目に都市$X_i$に向かって出発する（$A_i+T_{X_i}$日目に都市$X_i$に到着する）
- 地方都市→王都への依頼が$L$件
- $i$番目の依頼は、$B_i$日目に都市$Y_i$を出発する（$B_i+T_{Y_i}$日目に王都に到着する）
- 依頼を受けずに移動することはしない
- 到着した日に出発することは出来ない（翌日以降）
- 最大いくつの依頼をこなせるか
解法
地方都市→王都の依頼に関しては、直近の依頼を受けてとっとと王都に戻った方がよい。
しかし、王都→地方都市の依頼は、もし最初に来る依頼が移動に時間のかかる都市だったり、王都に戻るための依頼がなかなか来ない都市だったりしたら、パスして他の都市への依頼を待った方がいいかも知れない。
王都がハブなので、「王都→地方都市→王都」という移動をワンセットとして考える。
$dp[d]=d$日目まで（正確にはその前日まで）に受けられる依頼数の最大値として動的計画法で計算する。
王都を出発する$i$番目の依頼について、最も早く帰ってこれる日を$E_i$とすると、$dp[E_i]=dp[A_i]+2$ となる。
ただし日数の制約は$10^9$まであるので、dpを配列として持つことはできない。（$10^9$日＝274万年だが、異世界なので寿命とか時間の数え方が違うんだろう、きっと）
依頼数の制約が$10^5$以下なので、連想配列型で持つか、最初に「日付⇔連番」対応表を作って変換してから行う。
その際、「$d$日未満で受けられる依頼の最大値」は二分探索で求められる。
E - Treeone
問題
- 数列に対し「連続する 長さ 1 以上の部分列のうち、要素の総和が 0 であるものの個数」を「たぴさ」と命名する
- 部分列の中身が同じでも、位置が異なれば別のものとして数える
- 長さ $N$ の数列 $A_1,A_2,...,A_N$ が与えられる
- このうち 1 つの要素を好きな整数値に変更できる
- 「たぴさ」が最小となるように要素と変更値を選ぶとき、その最小値を求めよ
解法
$-10^9 \le A_i \le 10^9$の制約があるので、まったく規格外の整数(1恒河沙とか)に変更してしまえば、確実にその数字を含む区間は0にはならない。
こういう「部分列の要素の総和が0である」問題は、累積和を取って、同じ数字となった区間で効率的に数えることができる。
で、選ぶ$A_i$は、なるべく様々な数字の様々な区間に多く入っているものを用いるべきだ。
累積和で、たとえば'2'となるものに着目する。
累積和中で$l+1$番目の'2'の場合、左側には$l$個、右側には$N-l$個の'2'が登場する。このうち、$l+1$個目を変更することで部分列の和を0に出来なくなるのは、左側から1個、右側から1個を選ぶ$(l(N-l))$通り。
from collections import Counter, defaultdict
from itertools import accumulate
n = int(input())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
cnt = Counter(acc)
dcc = defaultdict(lambda: 0)
max_dcr = 0
dcr = 0
for c in acc:
p = dcc[c]
q = cnt[c] - p
prev = p * q
curr = (p + 1) * (q - 1)
dcr += curr - prev
max_dcr = max(max_dcr, dcr)
dcc[c] += 1
ans = 0
for k in cnt.values():
ans += k * (k - 1) // 2
print(ans - max_dcr)
