AtCoder Beginner Contest 421 D,E,F,G問題メモ

AtCoder Beginner Contest 421

D - RLE Moving

問題文

$(0,0)$ を中心に無限に広がるグリッドがあります。
最初、高橋君はマス $(R_t,C_t)$ に、青木君はマス $(R_a,C_a)$ にいます。
二人はそれぞれ 'U','D','L','R' からなる長さ $N$ の文字列 $S,T$ に従って $N$ 回移動を行います。
- ただし $N$ は非常に大きいため、ランレングス圧縮した形で与えられます。
- つまり、$S,T$ は $ ( (S'_1, A_1),\ldots(S'_M,A_M) ), ( (T'_1,B_1),\ldots,(T'_L,B_L) ) $ の形で与えられます。
$N$ 回の移動の中で、移動直後に高橋君と青木君が同じマスにいた回数を求めてください。
- 各移動は同時におこなわれ、すれ違うのはカウントしません。

制約

$-10^9 \leq R_t,C_t,R_a,C_a \leq 10^9$
$1\leq N \leq 10^{14}$
$1\leq M,L \leq 10^5$
$S'_i,T'_i$ は 'U', 'D', 'L', 'R' のいずれか
$1 \leq A_i,B_i \leq 10^9$
$A_1+\dots+A_M=B_1+\dots+B_L=N$
与えられる数値は全て整数

解法

上手く工夫しないと、場合分けが多く実装に時間がかかってしまう問題。
本番中はその工夫が思いつかず「うわあああやってられっか！」と思って飛ばした。

ただ、落ち着いてちゃんと性質を考えれば十分に軽くすることが可能。

まず、2人のマンハッタン距離を考えると、1ステップで $-2,0,2$ のいずれかしか増減しない。
初期状態が奇数の場合は $0$ が答えとなる。

そうでない場合、公式解説のように「どちらかの移動が切り替わるタイミング」ごとに分割して考える。

解説 - AtCoder Beginner Contest 421

これは、$[(S'_1,A_1),...,(S'_M,A_M)]$ と $[(T'_1,B_1),...,(T'_L,B_L)]$ の両配列でどこまで進んだかを表すポインタ $i,j$ を用意して、

$\min(A_i,B_j)$ ステップ分をまとめて考える。
$A_i \lt B_j$ の場合は、$B_j←B_j-A_i$ とし、$i$ を1進める。
$A_i \gt B_j$ の場合は、$A_i←A_i-B_j$ とし、$j$ を1進める。
$A_i = B_j$ の場合は、$i,j$ をともに1進める。

としていけばよい。

「$c$ ステップ分をまとめて考える」とした部分問題で答えに寄与する回数は、以下のように求められる。

$S'_i=T'_j$（進む方向が同じ）なら、

高橋君、青木君の現在位置が同じなら $c$ 回
そうでなければ $0$ 回

$S'_i \neq T'_j$（進む方向が違う）なら $0$ 回か $1$ 回。どちらになるかを考える。
同じマスに来るとしたら、それは $h=(2人の現在のマンハッタン距離)/2$ ステップ後である。

$h=0$ なら0回（求めたいのは“移動後”に同じマスにいるかなので）
$h \gt c$ なら0回
$0 \lt h \le c$ なら、$h$ ステップだけ実際に移動させてみて、実際に同じマスに来たら1回

$h=0$ を見落としがちだが、親切なことにサンプルでそのケースがあるので、考察漏れに気づける。

他にも場合分けを減らす方法としては、

高橋君の移動開始が常に原点になるように平行移動させる
高橋君の移動方向が常に右向きになるように回転させる

などより汎用的な方法もあるが、この問題は「同じマスになるとしたら $h$ ステップ後しかない」が一意に決まるので、実際に移動させて試してみるのが混乱しにくいように思う。どっちみち、同じマスにいる回数を求めた後は実際に移動させるので、処理も使い回せる。

Python3

def solve(rt, ct, ra, ca, n, m, l, sss, ttt):
    if (abs(rt - ra) + abs(ct - ca)) % 2 == 1:
        return 0

    MOVE_DIC = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    sss = [(s, int(a)) for s, a in sss]
    ttt = [(t, int(b)) for t, b in ttt]

    def move(s, r, c, dist):
        dr, dc = MOVE_DIC[s]
        return r + dr * dist, c + dc * dist

    def count_ans(s, t, c, rt, ct, ra, ca):
        if s == t:
            if rt == ra and ct == ca:
                return c
            return 0
        half_manhattan = (abs(rt - ra) + abs(ct - ca)) // 2
        if half_manhattan == 0 or half_manhattan > c:
            return 0
        mrt, mct = move(s, rt, ct, half_manhattan)
        mra, mca = move(t, ra, ca, half_manhattan)
        if mrt == mra and mct == mca:
            return 1
        return 0

    ans = 0
    i = 0
    j = 0
    while i < m and j < l:
        s, a = sss[i]
        t, b = ttt[j]
        if a < b:
            ans += count_ans(s, t, a, rt, ct, ra, ca)
            rt, ct = move(s, rt, ct, a)
            ra, ca = move(t, ra, ca, a)
            ttt[j] = (t, b - a)
            i += 1
        elif a > b:
            ans += count_ans(s, t, b, rt, ct, ra, ca)
            rt, ct = move(s, rt, ct, b)
            ra, ca = move(t, ra, ca, b)
            sss[i] = (s, a - b)
            j += 1
        else:
            ans += count_ans(s, t, a, rt, ct, ra, ca)
            rt, ct = move(s, rt, ct, a)
            ra, ca = move(t, ra, ca, b)
            i += 1
            j += 1
    return ans


rt, ct, ra, ca = map(int, input().split())
n, m, l = map(int, input().split())
sss = [input().split() for _ in range(m)]
ttt = [input().split() for _ in range(l)]
ans = solve(rt, ct, ra, ca, n, m, l, sss, ttt)
print(ans)

E - Yacht

問題文

$5$ 個の $6$ 面ダイスがあります。どのダイスも各面に書かれた数は $A_1,\ldots,A_6$ の $6$ 個であり、各面が出る確率は $\frac{1}{6}$ です。
あなたはこれらのダイスを使って次の手順で $1$ 人ゲームを行います。
- $5$ 個のダイスを全て振り、その結果を見て、好きな個数($0$ 個でもよい)のダイスをキープする。
- キープされていないダイスを全て振り直し、その結果を見て、振り直したダイスのうち好きな個数($0$ 個でもよい)のダイスを追加でキープする。前のステップでキープしたダイスはキープしたままとなる。
- キープされていないダイスを全て振り直し、その結果を見る。
- 好きな数 $X$ を選ぶ。$5$ 個のダイスのうち $X$ の目が出ているダイスの個数を $n$ として、このゲームの得点は $nX$ 点となる。

ゲームの得点の期待値を最大化するように行動するときの、ゲームの得点の期待値を求めてください。

制約

$A_i$ は $1$ 以上 $100$ 以下の整数

解法

原案は実在するサイコロゲームとみられる。

ヤッツィー

AC数がF問題より大幅に少ない。
メモ化再帰なのだが、結果の「maxをとる」のか「平均を取る」のかが混ざるので、しっかり意識しないといけない。

サイコロを振るのは運否天賦なので、結果の平均を取る。
出た目の中でどれを残すかは自分の意思で選択できるのでmaxをとる。

よって、以下を行えばよい。

サイコロ5個振って出た目を全探索。出た目に対する以下の結果の平均を取ると答え。
- 出た目に対してキープするものを全探索。以下の結果のMAXを取ったものを自身の結果とする。
  - キープしてないサイコロに対して出た目を全探索。以下の結果の平均を取る。
    - 出た目に対してキープするものを全探索。以下の結果のMAXを取る。
      - キープしてないサイコロに対して出た目を全探索。以下の結果の平均を取る。
        
        5個の目が確定しているので、一番いいスコアを得られる $nX$ を探す。

（やることは以上で全てなのだが、なかなかシンプルに実装しようとすると難しい）

厳密な計算量見積もりはなかなか難しいが、振る個数を $k$ として、サイコロの出た目は $6^k$、キープの仕方は $2^k$ ある。
結果をメモしながらおこなうと、$7～8 \times 10^5$ 回くらいの再帰関数の呼び出しで答えが求められる。

出た目の全探索は $6^k$ よりも重複組合せとかの方が探索数は減らせると思うが、平均を取るので、その出目が出る確率 $\dfrac{k!}{6^kc_1!c_2!...c_6!}$ を結果にかける必要があり実装量は増える（$c_i$ は第 $i$ 面が出ているダイスの個数）。お好みで。

Python3

from collections import Counter
from itertools import product


def iter_bitset_to_index(x):
    i = 0
    while x:
        if x & 1:
            yield i
        x >>= 1
        i += 1


def challenge(aaa, cur=(), k=0, memo={}):
    res = 0.
    if (k, cur) in memo:
        return memo[k, cur]

    if len(cur) == 5:
        for x, cnt in Counter(cur).items():
            res = max(res, x * cnt)
        memo[k, cur] = res
        return res

    if k < 2:
        res = 0.
        free_count = 5 - len(cur)
        for roll in product(aaa, repeat=free_count):
            tmp = 0.
            for keep in range(1 << free_count):
                new_cur = cur + tuple(roll[i] for i in iter_bitset_to_index(keep))
                tmp = max(tmp, challenge(aaa, new_cur, k + 1))
            res += tmp
        res /= pow(6, free_count)
        memo[k, cur] = res
        return res

    res = 0.
    free_count = 5 - len(cur)
    for roll in product(aaa, repeat=free_count):
        new_cur = cur + roll
        res += challenge(aaa, new_cur, 3)
    res /= pow(6, free_count)
    memo[k, cur] = res
    return res


aaa = list(map(int, input().split()))
ans = challenge(aaa)
print(ans)

F - Erase between X and Y

問題文

数列 $A$ があります。
はじめ、$A=(0)$ です。（すなわち、$A$ は $0$ を唯一の要素として含む長さ $1$ の数列です）。
クエリが $Q$ 個与えられるので、順に処理してください。
$i$ 番目 $(1\leq i\leq Q)$ のクエリは以下のいずれかの形式です。
- '1 x'：$A$ の中で $x$ が現れる場所の直後に $i$ を挿入する。
  - このクエリを処理する直前の時点で $A$ には $x$ が含まれていることが保証される。
- '2 x y'：$A$ の中で $x$ と $y$ の間（両端を除く）にある要素の値の合計を出力し、それらの要素を全て削除する。
  - ここで、このクエリを処理する直前の時点で $A$ には $x$ および $y$ が共に含まれていることが保証される。

なお、どのようなクエリの列に対しても、クエリを処理する過程で $A$ の中に同じ値が複数回現れることはなく、ゆえに $A$ の中である値が現れる場所は（存在するならば）一意であることに注意してください。

制約

$1\leq Q \leq 5\times 10^5$
$i$ 番目のクエリについて、
- $1$ 種類目のクエリのとき：
  - $0\leq x \lt i$
  - クエリを処理する直前の時点で $A$ には $x$ が含まれる
- $2$ 種類目のクエリのとき：
  - $0\leq x \lt y \lt i$
  - クエリを処理する直前の時点で $A$ には $x,y$ が共に含まれる
入力は全て整数

解法

連結リストの問題。
シンプル故に制限が多いデータ構造だが、この問題ではその制限は邪魔にならない。

配列と連結リスト｜アルゴリズム、データ構造の基本

実際のA       (0, 5, 2, 4, 1, ...)

連結リスト  i  0  1  2  3  4  5
            B  5     4     1  2

i→Bi→B[Bi]→...を辿っていくと、Aを復元できる

クエリ1では、$x→B_x$ を、$x→i→B_x$ に張り替えればよい。

クエリ2では、もし $A$ の中で $x$ の方が先に出現していたら、 $x→B_x→...→y$ まで辿って和を求めた後、$x→y$ に張り替えればよい。

この場合の計算量は、各要素に対する操作を「(A) クエリ1や、クエリ2の始点や終点として指定される」「(B) クエリ2の途中の数字として辿られる」に分けると、 (A)は全クエリ合わせて $O(Q)$ 回である。(B)は各要素につき高々1回しか発生せず要素数は $O(Q)$ である。
よって全体で $O(Q)$ で求められる。

ただし、先ほどは「$x$ の方が先に出現している」ことを仮定したが、$y$ の方が先に出現している可能性もある。
連結リストでは $x,y$ の具体的な出現位置を管理できないため、どちらが先かわからないことが問題となる。

だが、$x$ から辿った場合と $y$ から辿った場合を1ステップずつ並行して進めていけばどちらかは辿り着く。上記の計算量の(B)が2倍に増える程度で、変わらず $O(Q)$ で両方を試すことができる。

実装においては、連結リスト上で「終端」を示す要素（たとえば $Q+1$）を用意して、 $B_{Q+1}=Q+1$ などとしてループさせておけば、並行して進めた結果、一方が終端に到達してインデックスエラーになるなどの例外を手軽に防止できる。

Python3

def solve(q, queries):
    nxt = [-1] * (q + 2)
    nxt[0] = q + 1
    nxt[q + 1] = q + 1
    ans = []
    for i, query in enumerate(queries, start=1):
        if query[0] == 1:
            x = query[1]
            nxt[i] = nxt[x]
            nxt[x] = i
            continue
        x, y = query[1], query[2]
        ans_x = 0
        ans_y = 0
        ix = nxt[x]
        iy = nxt[y]
        while ix != y and iy != x:
            ans_x += ix
            ans_y += iy
            ix = nxt[ix]
            iy = nxt[iy]
        if ix == y:
            ans.append(ans_x)
            nxt[x] = y
        else:
            ans.append(ans_y)
            nxt[y] = x
    return ans


q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(q, queries)
print('\n'.join(map(str, ans)))

上記の通り、連結リストは要素を順番に辿ることしかできないため区間に対する操作に毎回 $O(N)$ かかり、上手い工夫ができる拡張もあまりない（自分が知らない）。

この問題のように「1回辿ったら削除」という条件があるなら使えるが、要素が残り続ける場合は使えなくなる。

その場合は、クエリ先読みによりクエリ1だけを連結リストやStackで処理し各要素の相対的な位置関係を構築した後、その列をセグメント木などに載せることで、$O(Q\log{Q})$ で解ける。

解説 - AtCoder Beginner Contest 421

G - Increase to make it Increasing

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
また、$M$ 個の整数組 $(L_1, R_1), (L_2, R_2), \dots, (L_M, R_M)\ (1\leq L_i\leq R_i\leq N)$ が与えられます。
あなたは数列 $A$ に対して、以下の操作を好きな回数（$0$ 回でも良い）行うことができます。
- $1$ 以上 $M$ 以下の整数 $i$ を選び、$A_{L_i}, A_{L_i+1},\dots, A_{R_i}$ にそれぞれ $1$ を足す。

$A$ を広義単調増加にすることが可能かどうか判定し、可能ならば必要な操作回数の最小値を求めてください。

制約

$1\leq N \leq 300$
$1\leq M \leq 300$
$1\leq A_i \leq 300$
$1\leq L_i\leq R_i\leq N$
入力は全て整数

解法

次の要素との差分 $D_i=A_{i+1}-A_i$ に注目する。

i   1   2   3   4
A   4   2   3   2
D  -2   1  -1   _

操作 $(L,R)$ は「$D_{L-1}$ に $1$ を足し、$D_{R}$ から $1$ を引く」という操作に対応する。
（※ $L=1$ である操作は無駄なため無視してよい）

操作によって $D_i$（$1 \le i \le N-1$）が全て非負になれば、$A$ は広義単調増加になっている。

i    1   2   3   4
A    4   2   3   2
D   -2   1  -1   _
     +       -        ←操作 (2,3)
A    4   3   4   2
D   -1   1  -2   _
             +   -    ←操作 (4,4)
A    4   3   4   3
D   -1   1  -1  -1    ※D4はどれだけ減らしてもよい

これは、以下のサイトで副次的に解説されているような「始点・終点が1つとは限らない最小費用流問題」に落とし込むことができる。

最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

有向グラフがある
各頂点 $v$ には余っている水の量 $d_v$ が定まっている（$d_v \lt 0$ なら不足を表す）
辺にしたがって水をやりとりし、過不足を解消するための最小コストは？

$D_i$ が、この水の過不足量 $d_i$ にちょうど当てはまる。
いくらでも減らしていい $d_N$ は、便宜的に $10^9$ など十分大きな値としておく。

操作 $(L,R)$ は、$R→(L-1)$ へのコスト1、容量無制限の辺に相当する。

上のブログでは $\sum_v d_v=0$ である場合について解説されているが、今回の場合は必ずしも $d_v$ の総和が $0$ になるとは限らない。

だが、負の部分が解消されればよいので、ブログの解説の通り辺を張って「$d_v$ が負のものの絶対値の合計」だけ流すことができれば十分となる。

流すことができなければ広義単調増加にすることも不可能となる。

Python3

本番では $\sum_v d_v=0$ にしなきゃ！と思って、余った $d_v$ をそこに集める“ゴミ箱頂点”みたいなのを作って、帳尻を合わせた。

from atcoder.mincostflow import MCFGraph


def solve(n, m, aaa, sections):
    ddd = [aaa[i + 1] - aaa[i] for i in range(n - 1)]
    INF = 10 ** 9
    total = sum(ddd)
    ddd.append(INF - total)
    ddd.append(-INF)
    mcf = MCFGraph(n + 3)
    g = n
    s = g + 1
    t = s + 1
    flow = 0

    for i, d in enumerate(ddd):
        if d > 0:
            mcf.add_edge(s, i, d, 0)
            mcf.add_edge(i, g, INF, 0)
            flow += d
        elif d < 0:
            mcf.add_edge(i, t, -d, 0)

    for l, r in sections:
        if l == 1:
            continue
        l -= 2
        r -= 1
        mcf.add_edge(r, l, INF, 1)

    f, cost = mcf.flow(s, t, flow)
    if f < flow:
        return -1
    return cost


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
sections = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, aaa, sections)
print(ans)

目次

AtCoder Beginner Contest 421 D,E,F,G問題メモ

D - RLE Moving

問題文

制約

解法

E - Yacht

問題文

制約

解法

F - Erase between X and Y

問題文

制約

解法

G - Increase to make it Increasing

問題文

制約

解法