AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）E,F,G問題メモ

AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）

GW中の開催のため、連休にちなんだ問題が多かった。

E - Endless Holidays

問題文

AtCoder 王国には $N$ 個の都市 $1,2,\dots,N$ があります。
また都市同士を双方向に結ぶ $M$ 本の道路があり、$i$ 番目の道路は都市 $U_i$ と都市 $V_i$ を結んでいます。
- どの都市間もいくつかの道路を辿ることで行き来可能です。
AtCoder 王国では一週間が $W$ 日からなります。
- 一週間は曜日 $1,2,\dots,W$ と進んでいき、曜日 $W$ の次の日は曜日 $1$ に戻ります。
- 都市ごとにいくつかの曜日が休日となっています。
- 都市 $i$ の休日の情報は長さ $W$ の文字列 $S_i$ で与えられます。
  - $S_i$ の $j$ 文字目が o のとき曜日 $j$ が休日であることを、x のとき曜日 $j$ が平日であることを意味します。
高橋君は曜日 $1$ の日の昼に、好きな都市を選んでそこを訪問します。
それ以降毎日夜に一度、今いる都市にとどまるか、道路で直接結ばれた都市のいずれかに移動することを繰り返します。
毎日昼の時点でいる都市が休日であるように移動を続けることが可能ならば Yes を、不可能ならば No を出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \leq T \leq 10^5$
$1 \leq N \leq 10^5$
$N-1 \leq M \leq 10^5$
$1 \leq U_i \lt V_i \leq N$
どの都市間もいくつかの道路を辿ることで行き来可能である
$2 \leq W \leq 10$
$T,N,M,U_i,V_i,W$ は整数
$S_i$ は o, x からなる長さ $W$ の文字列
全てのテストケースにおける $N$ の総和は $10^5$ 以下
全てのテストケースにおける $M$ の総和は $10^5$ 以下

解法

頂点倍加 + ループ検出。

グラフの頂点を (都市, 曜日) 毎に1つ用意する。各頂点に対し、平休が決まっていることになる。

$(a,d)→(b,d+1)$ への辺は、以下の2つをともに満たす場合にのみ張られる。曜日が一巡するところ（$W→1$）も含む。

$a→b$ に対する道路があるか、または $a=b$ である
$(a,d)$ と $(b,d+1)$ がともに休日である

この $NW$ 頂点 $MW$ 辺のグラフにループが存在すれば、条件を満たすことが言える。

グラフで行き止まりの頂点を順次削除していき（削除の結果、新たな行き止まりとなった頂点も含む）、全ての $NW$ 頂点が削除される前に削除できる頂点が無くなれば、ループが存在していると言える。

Python3

def solve(n, m, edges, w, whs):
    edges = [(u - 1, v - 1) for u, v in edges]
    edges.extend([(v, u) for u, v in edges])
    edges.extend((u, u) for u in range(n))

    rev_links = [[] for _ in range(n * w)]
    in_counts = [0] * (n * w)

    def get_v_num(v, i):
        return (i % w) * n + v

    for i in range(w):
        for u, v in edges:
            if whs[u][i - 1] == 'o' and whs[v][i] == 'o':
                uk = get_v_num(u, i - 1)
                vk = get_v_num(v, i)
                rev_links[vk].append(uk)
                in_counts[uk] += 1

    leaves = [i for i in range(n * w) if in_counts[i] == 0]
    while leaves:
        v = leaves.pop()
        for u in rev_links[v]:
            in_counts[u] -= 1
            if in_counts[u] == 0:
                leaves.append(u)

    ans = any(ic > 0 for ic in in_counts)

    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(m)]
    w = int(input())
    whs = [input() for _ in range(n)]
    ans = solve(n, m, edges, w, whs)
    if ans:
        print('Yes')
    else:
        print('No')

F - Plan Holidays

問題文

高橋君は $N$ 日間のスケジュールを決めようとしています。初期状態ではどの日も休日ではありません。
以下のいずれかの操作を好きな回数繰り返すことができます。
- $1$ 以上 $N$ 以下の整数 $i$ を選び、$i$ 日目を休日にする。この操作にはコストが $A_i$ かかる。
- $2$ 以上 $N-1$ 以下の整数 $i$ のうち $i-1$ 日目と $i+1$ 日目がすでにどちらも休日であるような $i$ を選び、$i$ 日目を休日にする。この操作にはコストはかからない。
連続する $K$ 日以上の休日を作るために必要なコストの総和の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq K \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
入力はすべて整数
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下

解法

トロピカル演算上の行列累乗。

クエリが無く、全ての日を休日にする場合の最小コストを求める場合をまず考える。

$a_i:=1～i$ 日目を全て休日にした場合の最小コスト（$i$ 日目は操作1により休日にしている）

とすると、$a_0=\infty, a_1=A_1$ とした上で、$i=2,3,...$ の順に

$a_i=\min(a_{i-1},a_{i-2})+A_i$

という漸化式で求められる。これは、行列演算で以下のようにも表現できる。

$$ \begin{pmatrix} a_i \\ a_{i-1} \end{pmatrix} = \begin{pmatrix} A_i & A_i \\ 0 & \infty \end{pmatrix} \oplus \begin{pmatrix} a_{i-1} \\ a_{i-2} \end{pmatrix} $$

ただし $\oplus$ は、通常の行列演算の $(+, \times)$ を、$(\min, +)$ に置き換えた演算を指すとする。

動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 #数学 - Qiita

この演算も、行列積に対して結合法則が成り立つことが知られている。つまり、

$$ \begin{pmatrix} a_i \\ a_{i-1} \end{pmatrix} = \begin{pmatrix} A_i & A_i \\ 0 & \infty \end{pmatrix} \oplus \begin{pmatrix} A_{i-1} & A_{i-1} \\ 0 & \infty \end{pmatrix} \oplus ... \oplus \begin{pmatrix} A_{2} & A_{2} \\ 0 & \infty \end{pmatrix} \oplus \begin{pmatrix} A_{1} \\ \infty \end{pmatrix} $$

のようにしたとき、どこから計算しても良い。

行列ごとセグ木などに載せ、$[l+1,r]$ の区間の集約値を得て最後に $A_l$ を加算することで、区間クエリに答えられる。

Python3

from atcoder.segtree import SegTree


def solve(n, k, aaa):
    if k == 1:
        return min(aaa)

    INF = 1 << 60
    init = [(a, a, 0, INF) for a in aaa]

    def merge(a, b):
        return (
            min(a[0] + b[0], a[2] + b[1]),
            min(a[1] + b[0], a[3] + b[1]),
            min(a[0] + b[2], a[2] + b[3]),
            min(a[1] + b[2], a[3] + b[3]),
        )

    sgt = SegTree(merge, (0, INF, INF, INF), init)

    ans = 1 << 60
    for l in range(n - k + 1):
        ans = min(ans, aaa[l] + sgt.prod(l + 1, l + k)[0])
        if l + k + 1 <= n:
            ans = min(ans, aaa[l] + sgt.prod(l + 1, l + k + 1)[0])
    return ans


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, k, aaa)
    print(ans)

G - Count Holidays

問題文

高橋君はこれから $N$ 日間についての勤務予定を、各日を勤務日か休日のどちらかに設定することで作成しようとしています。
勤務に関する条件を表す長さ $N$ の文字列 $S$ が与えられます。
- $S$ の $i$ 文字目が “x” のとき $i$ 日目は必ず勤務日にしなければなりません。
- “.” のとき $i$ 日目は勤務日と休日のどちらにすることもできます。
条件を満たす勤務予定は $S$ に含まれる “.” の個数を $q$ としたとき全部で $2^q$ 通り考えられます。
$k=1,2,\dots,N$ について次の問題を解いてください。
- 条件を満たす勤務予定 $2^q$ 通りのうち、最長の連続する休日がちょうど $k$ 日であるような決め方の総数を $998244353$ で割ったあまりを求めてください。

制約

$N$ は $1$ 以上 $2 \times 10^5$ 以下の整数
$S$ は ., x からなる長さ $N$ の文字列

解法

“x” で分割して、「“.” が $l$ 個連続したものが $c$ 個」というように、ラン長 $l$ ごとに個数カウントしておく。

$k$ に対する答えは、

$F(k):=$ 未確定日全体を、連続休日 $k$ 日以下で埋める方法の個数
$f(n,k):=n$ 日の連続した未確定日を、連続休日 $k$ 日以下で埋める方法の個数

としたとき、$F(k)=f(l_1,k)^{c_1} \times f(l_2,k)^{c_2} \times ...$ となる。 $k=0,1,2,...$ について $F(k)$ を求め、最後に差分を取れば、ちょうど $k$ の場合の答えが求められる。

よって、$f(n,k)$ を求められればよい。

これは、「正整数 $n+1$ を、$k+1$ 以下の要素で（順序も考慮して）分割する方法の個数」と一致する。

「+1」は、休日と休日の区切りに勤務日を入れる必要があるため、それを考慮したものである。

|---------- n ---------|
休休休勤休休勤休休勤勤休勤
|------||----||----||||--|  ←連続休日+勤務日1日 の組で分割

以下、（+1 をずらして）「正整数 $n$ の $k$ 以下の要素からなる順序付き分割の個数」を考慮するとする。

$n \le k$ の時、要素が $k$ を超えることがないので、どのように決めても良い。制約のない順序付き分割は $2^{n-1}$ で求められる。

$n \gt k$ の時が難しい。包除原理で求められる。

総和が S になる数列の個数 - 最大値が k

この計算量は、$O(\frac{n}{k})$ であるので、$k=0,...,n$ の範囲を全て計算するのは $O(n \log{n})$ でおこなえる。

全てのラン長 $l_i$ に対しておこなう必要があるが、$\sum_i l_i \le N$ のため、全体でも $O(N \log{N})$ でおこなえる。

ただし計算量が多くTLEが厳しめのため、階乗や $2$ の累乗は事前計算しておくのが望ましい。

Python3

from collections import defaultdict


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, s):
    counter = defaultdict(int)
    for part in s.split('x'):
        l = len(part)
        if l == 0:
            continue
        counter[l + 1] += 1

    series = list(counter.items())

    MOD = 998244353
    facts, finvs = precompute_factorials(n + 1, MOD)
    pow2 = [1]
    for _ in range(n):
        pow2.append(pow2[-1] * 2 % MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    def k_times_over_m_in_n(n, m, k):
        """ n の組成であって m+1 以上が少なくとも k 回出現するものの個数 """
        result = 0
        if n - 1 - k * (m + 1) >= 0:
            result += ncr(n - 1 - k * m, k) * pow2[n - 1 - k * (m + 1)]
            result %= MOD
        if k >= 1 and n - k * (m + 1) >= 0:
            result += ncr(n - 1 - k * m, k - 1) * pow2[n - k * (m + 1)]
            result %= MOD
        return result

    def lower_m_in_n(n, m):
        """ n の組成であって最大値が m 以下であるものの個数 """
        ans = 0
        for i in range(n + 1):
            result = k_times_over_m_in_n(n, m, i)
            if result == 0:
                break
            if i % 2 == 0:
                ans += result
            else:
                ans -= result
            ans %= MOD
        return ans

    def lower_m_in_all(m):
        """ 全ての未確定日の決め方において最大値が m 以下であるものの個数 """
        result = 1
        for l, cnt in series:
            if l <= m:
                result *= pow(pow2[l - 1], cnt, MOD)
            else:
                result *= pow(lower_m_in_n(l, m), cnt, MOD)
            result %= MOD
        return result

    buf = []
    for k in range(1, n + 2):
        buf.append(lower_m_in_all(k))

    for i in range(n, 0, -1):
        buf[i] -= buf[i - 1]
        buf[i] %= MOD

    return buf[1:]


n = int(input())
s = input()
ans = solve(n, s)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）E,F,G問題メモ

E - Endless Holidays

問題文

制約

解法

F - Plan Holidays

問題文

制約

解法

G - Count Holidays

問題文

制約

解法