目次
AtCoder Beginner Contest 164 D,E,F問題メモ
D - Multiple of 2019
問題
- 長さ $N$ の'0'～'9'からなる文字列 $S$ が与えられる
- 連続する区間 $[l,r]$ で、$S_l～S_r$ を10進数の整数として見たときに2019の倍数となっているようなものはいくつあるか求めよ
- $1 \le N \le 2 \times 10^5$
解法
つい最近、似たような問題が出た気がする。復習大事。
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()))
E - Two Currencies
問題
- $N$ 頂点 $M$ 辺のグラフに見立てた都市と鉄道がある
- あなたは今、都市1にいて、金貨を超沢山、銀貨を $S$ 枚持っている
- $i$ 番目の鉄道は都市 $U_i$ と $V_i$ を結び、運賃は片道銀貨 $A_i$ 枚、所要時間は $B_i$
- 金貨では支払えない
- 各都市では両替ができて、都市 $i$ では金貨1枚を銀貨 $C_i$ 枚に、時間 $D_i$ で両替できる
- 何枚でも両替できるが、時間はその都度かかる
- 都市 $2～N$ のそれぞれについて、到達できる最短時間を求めよ
- $2 \le N \le 50$
- $N-1 \le M \le 100$
- $1 \le A_i \le 50$
- $0 \le S \le 10^9$
- $0 \le B_i,C_i,D_i \le 10^9$
解法
頂点を多重にする最短経路探索の練習的問題？
$N,A_i$ がなかなか少なめ。
運賃があるなら時間優先で各都市に向かいたいが、足りない場合、どこかで両替の必要がある。 遠く離れた都市でメッチャ速く両替できるなら、わざわざそこまで行って両替して、帰ってくるみたいなこともあり得る。 なので、1回訪れた都市を再度訪れるかも知れないので、普通のDijkstraなどでは上手くいかない。
だが、もし2回目に訪れたとき、1回目より所持銀貨が同じや少なかったら……？
その場合、2回目から時間 $t$ かけて訪れられる都市は、1回目の時点でも当然同じ経路を辿れば同じように訪れられる。 従って、トータルでは絶対に遅くなるので、それ以上探索を広げる必要は無い。
所持銀貨の情報も合わせて考慮すればよさそう。
Dijksra法を使うとし、頂点を「$(v, s)=$ 都市 $v$ を、所持銀貨 $s$ で訪れた状態」とする。$DP[v,s]$ をその状態に至れる最短所要時間とする。
とある $(v,s)$ に時間 $t$ で到達できた場合、以下の2通りの遷移を行う。
- 両替する
- $DP[v,s+C_v]←DP[v,s]+D_v$
- 更新したなら、$(v,s+C_v)$ をキューに追加
- 移動する
- $v$ から伸びる鉄道 $i$ を使って移動する（もう一方の都市を $u$ とする）
- $DP[u, s-A_i]←DP[v,s]+B_i$
- 更新したなら、$(u,s-A_i)$ をキューに追加
- ※ただし、運賃が足りる場合のみ
計算量
ここで $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$ を訪れたなら、そこで両替できるだけしてしまうという考えもある。
- $(v,s+C_v)$ をキューに追加
- $(v,s+2C_v)$ をキューに追加
- $(v,s+3C_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:])))
F - I hate Matrix Construction
問題
- 整数 $N$ と、長さ $N$ の4つの数列 $S,T,U,V$ が与えられる
- $S,T$ は '0','1'のみからなる
- 以下の条件を満たす $N \times N$ 行列を一例、構築せよ
- 条件
- $S_i=0$ の時、$i$ 行目の要素を全て BitwiseAnd すると $U_i$
- $S_i=1$ の時、$i$ 行目の要素を全て BitwiseOr すると $U_i$
- $T_j=0$ の時、$j$ 行目の要素を全て BitwiseAnd すると $V_j$
- $T_j=1$ の時、$j$ 行目の要素を全て BitwiseOr すると $V_j$
- $1 \le N \le 500$
- $0 \le U_i,V_i \lt 2^{64}$
解法
数字を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_i=0$:AND なら、$U_i=1$ の行は全て1
- $S_i=1$:OR なら、$U_i=0$ の行は全て0
これを埋める。この時点で、行と列でかち合うものがあれば、不可能。
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が埋まっている
以下のようにすると、かち合うものを検出できる。
- まず行（$S,U$）で確定できるところを埋める。その際、0,1それぞれ、確定したものがあったかを記録する
- 次に列（$T,V$）で確定できるところを埋める際、埋めようとする値と矛盾するものが、行で確定していたら、不可能
さて、次に、確定しないものを考える。
- $S_i=0$:AND なら、$U_i=0$ の列の少なくとも1つは0
- $S_i=1$:OR なら、$U_i=1$ の列の少なくとも1つは1
ここで、未確定の行・未確定の列の個数で、処理を場合分けする。
ともに2つ以上ある
話は簡単で、未確定マスの中だけで市松模様状に敷き詰めればよい。必ず、どの行・列にも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で埋まった列があるか」を記録しておけばよい。
どちらかが1つのみ
市松模様が使えない。この処理にちょっと混乱してWAを連発した。まぁこれは丁寧にいろんなケースを確認していくしかないんだろう。
未確定が1つのみなのが列であるとし、その列で少なくとも1つは存在しなければいけない値が $b$ だとする。
直交する行に既に $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}$ が確定している
$\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)
