つい最近、似たような問題が出た気がする。復習大事。
from collections import defaultdict
s = input()
cnt = defaultdict(int)
cnt[0] += 1
tmp = 0
for i, c in enumerate(s[::-1]):
c = int(c)
tmp = (tmp + c * pow(10, i, 2019)) % 2019
cnt[tmp] += 1
print(sum(c * (c - 1) // 2 for c in cnt.values()))
頂点を多重にする最短経路探索の練習的問題？
$N,A_i$ がなかなか少なめ。
運賃があるなら時間優先で各都市に向かいたいが、足りない場合、どこかで両替の必要がある。 遠く離れた都市でメッチャ速く両替できるなら、わざわざそこまで行って両替して、帰ってくるみたいなこともあり得る。 なので、1回訪れた都市を再度訪れるかも知れないので、普通のDijkstraなどでは上手くいかない。
だが、もし2回目に訪れたとき、1回目より所持銀貨が同じや少なかったら……？
その場合、2回目から時間 $t$ かけて訪れられる都市は、1回目の時点でも当然同じ経路を辿れば同じように訪れられる。 従って、トータルでは絶対に遅くなるので、それ以上探索を広げる必要は無い。
所持銀貨の情報も合わせて考慮すればよさそう。
Dijksra法を使うとし、頂点を「$(v, s)=$ 都市 $v$ を、所持銀貨 $s$ で訪れた状態」とする。$DP[v,s]$ をその状態に至れる最短所要時間とする。
とある $(v,s)$ に時間 $t$ で到達できた場合、以下の2通りの遷移を行う。
ここで $s$ は、都市が50個しか無いので最遠でも $49$ 回鉄道に乗ればよくて、鉄道1回の運賃も50以下なので、 多くとも $50 \times 49 = 2450$ さえ持っていれば、それ以上両替の必要は無い。
よって、頂点数は $O(N^2A_{max})$ となる。
辺数も、1頂点から伸びる1本が約2450倍に複製される感じなので、$O(NMA_{max})$ となる。
優先付きキューを使うと、Dijkstraの計算量は $O((N^2A_{max}+NMA_{max})\log{N^2A_{max}})$ で、上限の数字を当てはめるとだいたい6375000となる。
これは実際、Pythonではちょっと厳しくて、下手なことをするとTLEになってしまう。
たとえば、1回都市 $v$ を訪れたなら、そこで両替できるだけしてしまうという考えもある。
だがこうすると、Dijkstraの実装によっては、キューに同じ状態を示す頂点が多く積み上がってしまうことになり、TLEとなる。（この事実に気付くのに時間かかった）
両替は1度に金貨1枚分とし、それがキューから引っ張り出されたら、改めてもう1枚両替を考慮すればよい。
import sys
from heapq import heappop, heappush
n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
u, v, a, b = map(int, line.split())
u -= 1
v -= 1
links[u].add((v, a, b))
links[v].add((u, a, b))
aaa.append(a)
exchanges = []
for line in lines[m:]:
c, d = map(int, line.split())
exchanges.append((c, d))
req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n
q = [(0, ss, 0)] # (time, silver, city)
visited = set()
fixed = 0
while q:
t, s, v = heappop(q)
if (s, v) in visited or ans_silver[v] >= s:
continue
visited.add((s, v))
if ans[v] == INF:
ans[v] = t
ans_silver[v] = s
fixed += 1
if fixed == n:
break
for u, a, b in links[v]:
if s < a:
continue
ns = s - a
nt = t + b
if (ns, u) in visited or ans_silver[u] >= ns:
continue
heappush(q, (nt, ns, u))
c, d = exchanges[v]
ns = s + c
if ns <= req and (ns, v) not in visited:
heappush(q, (t + d, ns, v))
print('\n'.join(map(str, ans[1:])))
数字を2進数で見たとき、ある桁の処理は他の桁に影響しないので、桁毎に考える。$U,V$ は 0/1 の2通りだけを考えればよくなる。
S 処理 U
_ _ _ _ | 1 or 1
_ _ _ _ | 1 or 0
_ _ _ _ | 0 and 0
_ _ _ _ | 0 and 1
-----------------+
T 0 1 0 1
処理 and or and or
V 1 1 0 0
ここで、まずは2つの事実により、確定する行・列がある。（$T,V$ でも同じ）
これを埋める。この時点で、行と列でかち合うものがあれば、不可能。
S 処理 U
_ _ _ _ | 1 or 1
0 0 0 0 | 1 or 0 ←確定
_ _ _ _ | 0 and 0
1 1 1 1 | 0 and 1 ←確定
-----------------+
T 0 1 0 1
処理 and or and or
V 1 1 0 0
↑
1確定だが、既に0が埋まっている
以下のようにすると、かち合うものを検出できる。
さて、次に、確定しないものを考える。
ここで、未確定の行・未確定の列の個数で、処理を場合分けする。
話は簡単で、未確定マスの中だけで市松模様状に敷き詰めればよい。必ず、どの行・列にも0,1が1マス以上存在するようになる。
S 処理 U
1 [0] 1 [1] | 1 or 1
1 [1] 1 [0] | 1 or 1
1 [0] 1 [1] | 0 and 0
1 1 1 1 | 0 and 1
マスは全て確定している。「確定する条件」の中では、矛盾はない。
後は、未確定条件が全て合致しているか調べればよい。
以下は、列側の要件により全てが“1”で確定した状態で 行側の要件を確認する過程だが、この時に「どれか1つは0」があると矛盾する。
S 処理 U
1 1 1 1 | 1 or 1 [未確定] どれか1つは1
1 1 1 1 | 1 or 1 [未確定] どれか1つは1
1 1 1 1 | 0 and 0 [未確定] どれか1つは0 → 矛盾
1 1 1 1 | 0 and 1 [確定]
これも、確定行同士での矛盾を検出するときと同様、「0で埋まった列があるか」「1で埋まった列があるか」を記録しておけばよい。
市松模様が使えない。この処理にちょっと混乱してWAを連発した。まぁこれは丁寧にいろんなケースを確認していくしかないんだろう。
未確定が1つのみなのが列であるとし、その列で少なくとも1つは存在しなければいけない値が $b$ だとする。
S 処理 U
1 1 _ 1 | 1 or 1 どれか1つは1
1 1 _ 1 | 1 or 1 どれか1つは1
1 1 _ 1 | 0 and 0 どれか1つは0
1 1 1 1 | 0 and 1 [確定]
↑
どれか1つは1 ... 既に満たされている
この場合、未確定列の要件は既に満たされているので、行方向で未確定の要件に求められているものを埋めればよい。
S 処理 U
1 1 [1] 1 | 1 or 1 どれか1つは[1]
1 1 [1] 1 | 1 or 1 どれか1つは[1]
1 1 [0] 1 | 0 and 0 どれか1つは[0]
1 1 1 1 | 0 and 1 [確定]
$\bar{b}$ は、反転したもの（0なら1、1なら0）とする。
S 処理 U
0 1 _ 1 | 1 or 1 どれか1つは1
0 1 _ 1 | 1 or 1 どれか1つは1
0 1 _ 1 | 0 and 0 どれか1つは0
0 1 _ 1 | 0 and 0 どれか1つは0
↑
どれか1つは1
この場合、未確定な行の要件で、$\bar{b}$ なものは既に満たされているので、全て $b$ で埋めてよい。
S 処理 U
0 1 [1] 1 | 1 or 1 どれか1つは1
0 1 [1] 1 | 1 or 1 どれか1つは1
0 1 [1] 1 | 0 and 0 どれか1つは0 [要件は既に満たされている]
0 1 [1] 1 | 0 and 0 どれか1つは0 [要件は既に満たされている]
↑
どれか1つは[1]
S 処理 U
1 1 _ 1 | 0 and 0 どれか1つは0
1 1 _ 1 | 0 and 0 どれか1つは0
1 1 _ 1 | 0 and 0 どれか1つは0
1 1 _ 1 | 0 and 0 どれか1つは0
↑
どれか1つは1
未確定な行で、入れたい値が $\bar{b}$ なものは、まだ要件が満たされていないので、未確定の残る1列に入れるしかない。
よって、基本は未確定な行の要件で埋めていく。
そうして埋めていって、$b$ の入る行が1つも無ければ、そこで不可能となる。
S 処理 U
1 1 0 1 | 0 and 0 どれか1つは0
1 1 0 1 | 0 and 0 どれか1つは0
1 1 0 1 | 0 and 0 どれか1つは0
1 1 0 1 | 0 and 0 どれか1つは0
↑
どれか1つは1 ... 矛盾!
1つでもあれば、それで列の要件も満たされるので、よし。
# なんて冗長なコードですこと。
from functools import reduce
def add_row(ans, n, i, k):
for j in range(n):
ans[i][j] |= k
def add_column(ans, n, j, k):
for i in range(n):
ans[i][j] |= k
def solve(n, sss, ttt, uuu, vvv):
max_d = max(max(uuu).bit_length(), max(vvv).bit_length())
ans = [[0] * n for _ in range(n)]
for d in range(max_d):
k = 1 << d
ambiguous_i = []
ambiguous_j = []
filled_i = [False, False]
filled_j = [False, False]
for i, (s, u) in enumerate(zip(sss, uuu)):
if s == 0:
if u & k:
add_row(ans, n, i, k)
filled_i[1] = True
else:
ambiguous_i.append((i, 0))
else:
if u & k:
ambiguous_i.append((i, 1))
else:
filled_i[0] = True
for j, (t, v) in enumerate(zip(ttt, vvv)):
if t == 0:
if v & k:
if filled_i[0]:
return -1
add_column(ans, n, j, k)
filled_j[1] = True
else:
ambiguous_j.append((j, 0))
else:
if v & k:
ambiguous_j.append((j, 1))
else:
if filled_i[1]:
return -1
filled_j[0] = True
# print(*map('{:064b}'.format, [k] * (n + 1)))
# for i in range(n):
# print(*map('{:064b}'.format, ans[i]), end=' ')
# print('{:064b}'.format(uuu[i]))
# print(*map('{:064b}'.format, vvv))
# print(ambiguous_i, ambiguous_j)
# print(filled_i, filled_j)
# print()
if len(ambiguous_i) == 0:
amb = set(bj for j, bj in ambiguous_j)
for bj in amb:
if not filled_i[bj]:
return -1
elif len(ambiguous_j) == 0:
amb = set(bi for i, bi in ambiguous_i)
for bi in amb:
if not filled_j[bi]:
return -1
elif len(ambiguous_i) == 1:
i, bi = ambiguous_i[0]
if filled_j[bi]:
for j, bj in ambiguous_j:
if bj:
ans[i][j] |= k
elif filled_i[bi ^ 1]:
if bi:
for j, bj in ambiguous_j:
ans[i][j] |= k
else:
ok = False
for j, bj in ambiguous_j:
if bj:
ans[i][j] |= k
if bi == bj:
ok = True
if not ok:
return -1
elif len(ambiguous_j) == 1:
j, bj = ambiguous_j[0]
if filled_i[bj]:
for i, bi in ambiguous_i:
if bi:
ans[i][j] |= k
elif filled_j[bj ^ 1]:
if bj == 1:
for i, bi in ambiguous_i:
ans[i][j] |= k
else:
ok = False
for i, bi in ambiguous_i:
if bi:
ans[i][j] |= k
if bi == bj:
ok = True
if not ok:
return -1
else:
for ii, (i, bi) in enumerate(ambiguous_i):
for jj, (j, bj) in enumerate(ambiguous_j):
if (ii ^ jj) & 1:
ans[i][j] |= k
return ans
n = int(input())
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))
uuu = list(map(int, input().split()))
vvv = list(map(int, input().split()))
ans = solve(n, sss, ttt, uuu, vvv)
if ans == -1:
print(ans)
else:
for row in ans:
print(*row)