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)

programming_algorithm/contest_history/atcoder/2020/0426_abc164.txt · 最終更新: 2020/04/29 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0