満点制約は $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')
'.
': 更地、自由に移動できる'#
': 壁、人もイノシシも移動できない、外周1マスは必ず壁'@
': イノシシ、体当たりされると痛い、複数体いる'S
': スタート、フィールドに1つだけある'G
': ゴール、フィールドに1つだけある'-1
'を出力せよ「そこから$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))
地方都市→王都の依頼に関しては、直近の依頼を受けてとっとと王都に戻った方がよい。
しかし、王都→地方都市の依頼は、もし最初に来る依頼が移動に時間のかかる都市だったり、王都に戻るための依頼がなかなか来ない都市だったりしたら、パスして他の都市への依頼を待った方がいいかも知れない。
王都がハブなので、「王都→地方都市→王都」という移動をワンセットとして考える。
$dp[d]=d$日目まで(正確にはその前日まで)に受けられる依頼数の最大値として動的計画法で計算する。
王都を出発する$i$番目の依頼について、最も早く帰ってこれる日を$E_i$とすると、$dp[E_i]=dp[A_i]+2$ となる。
ただし日数の制約は$10^9$まであるので、dpを配列として持つことはできない。($10^9$日=274万年だが、異世界なので寿命とか時間の数え方が違うんだろう、きっと)
依頼数の制約が$10^5$以下なので、連想配列型で持つか、最初に「日付⇔連番」対応表を作って変換してから行う。
その際、「$d$日未満で受けられる依頼の最大値」は二分探索で求められる。
$-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)