AtCoder Beginner Contest 338 F,G 問題メモ

AtCoder Beginner Contest 338

F - Negative Traveling Salesman

問題

$N$ 頂点 $M$ 辺の重み付き単純有向グラフがある
辺は負の重みをとることもあるが、負閉路は存在しない
全ての頂点を1度以上通るようなウォークがあるか判定し、ある場合は通る辺の重みの総和の最小値を求めよ
- 同じ辺を2度以上通ってもよいが、コストは通るたびに加算される
$2 \le N \le 20$

解法

Floyd-Warshall は、負辺があっても負閉路がなければ全頂点間同士の最短距離を求められる。

また、巡回セールスマンも通った頂点集合が小さい方から探索を進めれば、コストに負が出てきても大丈夫。
（Dijkstra的に、コストが小さい方から探索してしまうと、負辺が出てくる場合は上手くいかない）

Floyd-Warshall で求めた全頂点間の最短距離を使って、巡回セールスマンをおこなえば、答えとなる。

証明

以下を両方言えれば、上記の方法で答えが求められるといえる。

1) 巡回セールスマンのパスに対応する、全頂点を1回以上通るウォークが存在する
2) 正解のウォークに対応する、巡回セールスマンのパスが存在する

※ここでの意味づけ
ウォーク: 直接辺がある頂点間のみ通り、同じ頂点を複数回通ってもいいような一連の移動
巡回セールスマンのパス: 直接辺が無くてもよく、全頂点を1度ずつ訪れるパス

2)より、巡回セールスマン中に正解のコストがちゃんと探索・考慮されることが保証される。
1)より、全ての巡回セールスマンのパスは何らかのウォークに対応づけられる。ウォークで表現できない何者かが、本来の正解のコストより小さくなってしまうことはない。

1)、②→①→④→⑤→…→③ という巡回セールスマンのパスに対して、各移動（②→①、①→④、…）を最短距離を実現するパスに置き換えれば、全頂点を1回以上通るウォークとなる。

②→①→→→④→→→→→⑤→...→③

  ①→④ の最短距離を実現するパスは、①→②→④
  ④→⑤ の最短距離を実現するパスは、④→③→②→⑤
  ...etc.

↓ウォークを復元できる
↓（このパスから復元されるウォークは、各移動を最短距離でおこなうこれが最適）

②→①→②→④→③→②→⑤→...→③

2)、コスト最小となる正解のウォークが ②→①→②→④→③→②→⑤→…→③ みたいな感じであるとする。

負閉路はないので、始点と終点は別としてよい。
（始点と終点が一致ならループしており、ループ上のどこかにはコスト非負の辺が含まれる。それを削除して切り開けば、悪化させずに始点と終点を別にすることができる）

すると、始点②と終点③はそのまま、他は正解ウォーク中にはじめて出てくる順に抜き出した $1～N$ の順列（②→①→④→⑤→…→③）を作り、その順に向かうことにすると、巡回セールスマンのパスで表現できる。

これを1)の方法で復元すると、元のウォークに戻るはずである。
もし、よりコストの低い別のウォークとなってしまったら、そっちの方が正解となり、最初の過程と矛盾する。

実装上の留意点として、負辺を含む場合、DP配列の初期値として十分大きい数 $INF=10^{18}$ などで“不可能な状態”を表していると、負辺を通って「INFよりちょっと少ない数」で更新されてしまう可能性があり、「最終的な結果=INFなら不可能」と言えなくなる。

いずれかの対策を取る必要がある。
- 答えの取り得る範囲を $-X～X$ として、 $2X$ 以上の数で初期化して、 $X$ 以上なら「不可能」と判定する
- INFと定めた値からは更新しないようにする

巡回セールスマンの時の $DP[S,i]$ の $S$ って、通常の場合は「既に訪れた頂点」と意味づけることが多いので、その意味合いのまま、今回の問題で元のウォークの状態を表現しようとすると、「Froyd-Warshallにおける最短距離を実現するパス」の情報まで必要になってしまい、実装が大変になった。

途中の通過点を無視した実装でも、ちゃんといけるんだね。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(inp):
    n, m = inp[:2]
    uuu = inp[2::3] - 1
    vvv = inp[3::3] - 1
    www = inp[4::3]
 
    INF = 1 << 60
    dist = np.full((n, n), INF, np.int64)
    for i in range(n):
        dist[i, i] = 0
    for i in range(m):
        u = uuu[i]
        v = vvv[i]
        w = www[i]
        dist[u, v] = w
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i, j] = min(dist[i, j], dist[i, k] + dist[k, j])
 
    dp = np.full((1 << n, n), INF, np.int64)
    for i in range(n):
        dp[1 << i, i] = 0
 
    mask = (1 << n) - 1
    for bitset in range(1, 1 << n):
        for u in range(n):
            if dp[bitset, u] == INF:
                continue
            for v in range(n):
                if dist[u, v] == INF or bitset & (1 << v) != 0:
                    continue
                dp[bitset | (1 << v), v] = min(dp[bitset | (1 << v), v], dp[bitset, u] + dist[u, v])
 
    ans = dp[mask, :].min()
    return ans
 
 
SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()
 
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)
 
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
 
if ans == 1 << 60:
    print('No')
else:
    print(ans)

            

        
      

G - evall

問題

以下を全て満たす文字列を「計算式として評価できる文字列」とする
- '0'以外の数字と、'+','*'のみからなる
- 先頭と末尾の文字が数字
- 数字でない文字は2個以上連続しない
計算式として評価できる文字列 $S$ が与えられる
$S$ の全ての（連続した）部分文字列のうち、計算式として評価できる文字列であるものを、計算式として評価した結果の総和を $\mod{998244353}$ で求めよ
$1 \le |S| \le 10^6$

解法

まず、かけ算が優先されるので、そちらを先に評価した方がやりやすそう。'+'で区切ってしまう。

123*456*789+12345*6789+12*34*56*78*9
↓
[123*456*789, 12345*6789, 12*34*56*78*9]

区切られた1つ1つを「かけ算式」と呼ぶことにする。

各かけ算式について、加算される回数を求める。

①
123*456*789 ┐かけ算式内に左端があり、右端はこれより後のかけ算式内にある場合、
 23*456*789 │こいつらは、それぞれ、これより後に出てくるかけ算式の、
  3*456*789 │数字の個数分だけ加算される
    456*789 │
     56*789 │
      6*789 │
        789 │
         89 │
          9 ┘
②
123*456*789 ┐かけ算式内に右端があり、左端はこれより前のかけ算式内にある場合、
123*456*78  │こいつらは、それぞれ、これより前に出てくるかけ算式の、
123*456*7   │数字の個数分だけ加算される
  :         │
123         │
12          │
1           ┘

③
123*456*789   かけ算式を覆うように区間が設定される場合、全体が、
              （これより前に出てくる数字の個数）×（後に出てくる数字の個数）
              分だけ加算される

④かけ算式内に左端も右端もある場合（後述）

①②③は、各かけ算式のprefix,suffix（上記に列挙したような式）の総和と、数字の個数を数えておけばよい。
前からと後ろから調べれば、それぞれ $O(|S|)$ で作れる。

④は、'*'で区切って数字のみの式（数字式と呼ぶことにする）にして、1文字ずつ評価すれば、

[123, 456, 789] に分割した内の、789 の '8' を評価中として、

(A)それより前の数字式のsuffixの和
123*456 ┐
 23*456 │
   :    │
     56 │
      6 ┘

(B)現在の数字式の'8'以前の部分
78

(C)現在の数字式の'8'以前の部分のsuffixの和
78 ┐
 8 ┘

④に分類される式のうち、'8'を右端としたものの総和は、 $A \times B + C$ で求められる。

数字式内では、B,Cを以下で更新していける。（数字 $x$ で更新するとする）

$B←10B+x$
$C←10C+x \times (xがその数字式の何番目の数字か)$

数字式の終端まで来たら、 $A←A \times B + C$ で更新し、 $B,C←0$ として次の数字式に移る。

これで全ての場合を $O(|S|)$ で求められる。

Python3

        
          
          
              
              from itertools import accumulate
 
s = input()
MOD = 998244353
plus_split = s.split('+')
fwd_sum = []
bwd_sum = []
full_eval = []
counts = []
ans = 0
for t in plus_split:
 
    mul_split = t.split('*')
    tmp = 0
    cnt = 0
    p = 1  # 現在処理中の * 以前の、先頭からの計算結果 ex) 12*34*56  56を処理中として、12*34
    r = 0  # 現在処理中の * 以前の、末尾からの計算の和 ex) 12*34*56  56を処理中として、12*34 + 2*34 + 34 + 4
    for u in mul_split:
        q = 0  # 現在処理中の*区間の、先頭からの評価結果 ex) 123456  5を処理中として、1234
        m = 0  # 現在処理中の*区間の、末尾からの評価の和 ex) 123456  5を処理中として、1234 + 234 + 34 + 4
        for i, c in enumerate(u, start=1):
            c = int(c)
            q = (q * 10 + c) % MOD
            m = (m * 10 + c * i) % MOD
            tmp += p * q
            tmp %= MOD
            ans += r * q + m
            ans %= MOD
            cnt += 1
        p *= q
        p %= MOD
        r = (r * q + m) % MOD
    fwd_sum.append(tmp)
    counts.append(cnt)
    full_eval.append(p)
 
    tmp = 0
    cnt = 0
    p = 1  # 現在処理中の * 以後の、末尾からの計算結果 ex) 12*34*56  12を処理中として、34*56
    for u in reversed(mul_split):
        q = 0  # 現在処理中の*区間の、末尾からの評価結果 ex) 123456  2を処理中として、3456
        d = 1
        for c in reversed(u):
            c = int(c)
            q = (c * d + q) % MOD
            tmp += p * q
            tmp %= MOD
            d *= 10
            d %= MOD
        p *= q
        p %= MOD
    bwd_sum.append(tmp)
 
fwd_cnt = [0] + list(accumulate(counts))
fwd_cnt.pop()
counts.reverse()
bwd_cnt = [0] + list(accumulate(counts))
bwd_cnt.pop()
bwd_cnt.reverse()
 
for i in range(len(fwd_sum)):
    ans += fwd_sum[i] * fwd_cnt[i]
    ans += bwd_sum[i] * bwd_cnt[i]
    ans += full_eval[i] * (fwd_cnt[i] * bwd_cnt[i])
    ans %= MOD
 
print(ans)

            

        
      