サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）F,G,H問題メモ

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

F - Cleaning Robot

問題

グリッド上を $(0,0)$ からスタートしてLRUDの命令に従って動くロボットがある
文字列 $S$ を $K$ 回繰り返した文字列を命令とするとき、ロボットが通過するマス数を求めよ
- 複数回通過したマスも1個と数える
$1 \le |S| \le 2 \times 10^5$
$1 \le K \le 10^{12}$

解法

$S$ 1ループで通過するマスをまず列挙する。マスの集合を $P$ とする。

最後に到達したマスが $(a,b)$ だったら、次はそこから始まるので、次の1ループは $P$ を $(a,b)$ だけ平行移動させたマスを通過する。

1ループ目      2ループ目(1ループ目はo、被ったのはXで表示)
...........    ..............
...........    ....#######G..
...........    ....#.........
.#######G..    .oooXoooS.....
.#.........    .o..#...#.....
.#...S.....    .o..#X#######.
.#...#.....    .o...o..#...#.
.#########.    .oooooooXX###.
.....#...#.    .....o...o....
.....#####.    .....ooooo....
...........    ..............

$P$ のマスの1つを $(x,y)$ とする。
ループを重ねるごとに、それに相当するマスは以下を通過することになる。
（ループのスタートからの相対位置が同じマスを「相当するマス」と呼ぶことにする）

$(x+a,y+b),(x+2a,y+2b),(x+3a,y+3b),...,(x+(K-1)a,x+(K-1)b)$

ここで、例えば $(x+3a,y+3b)$ も $P$ に含まれるとする。

すると、$(x,y)$ に相当するマスは、$(x,y),(x+a,y+b),(x+2a,y+2b)$ だけが答えに寄与する。

それ以降は $(x+3a,y+3b)$ とそれに相当するマスが既に通過済みなので、答えに寄与しない。

従って、「$(a,b)$ を加算していくことで被りうるグループ」ごとに $P$ の各マスを分類すればよい。

違うグループのマス同士は、どれだけループを重ねても被ることはない。

グループ内の計算

あるグループに $(x,y),(x+3a,y+3b),(x+10a,y+10b)$ の3つが入ったとして、$K=5$ だとすると、

$(x,y)$ は、次の $(x+3a,y+3b)$ までの3マス
$(x+3a,y+3b)$ は、次の $(x+10a,y+10b)$ と被るまでには終わるので、5マス
最後の $(x+10a,y+10b)$ は、まるまる5マス

隣り合う2マス毎に、「その差分」と「$K$」の小さい方が答えに寄与する。
従ってこのグループでは、計13マスが答えに寄与する。

全てのグループについて合計した結果が答え。

グループの分類方法

$(a,b)$ を足し引きすることで $x$ を $0～a-1$ の間にそろえればよい。

言い換えると、$0 \le x-da \lt a$ となるような $d$ を見つけて、$(x-da,y-db)$ ごとに分類すればよい。

ただし、$a=0$ の時は分けて考える必要がある点に注意。

Python3

from collections import defaultdict

s = input()
k = int(input())
visited = {(0, 0)}
i = 0
j = 0
for c in s:
    if c == 'R':
        j += 1
    elif c == 'L':
        j -= 1
    elif c == 'U':
        i -= 1
    else:
        i += 1
    visited.add((i, j))

gi = i
gj = j

if gi == 0:
    if gj == 0:
        print(len(visited))
        exit()

    ans = 0
    groups = defaultdict(list)
    for i, j in visited:
        d, m = divmod(j, gj)
        groups[i, m].append(d)
    for grp in groups.values():
        grp.sort()
        for d1, d2 in zip(grp, grp[1:]):
            ans += min(k, d2 - d1)
        ans += k
    print(ans)
    exit()

ans = 0
groups = defaultdict(list)

for i, j in visited:
    d, m = divmod(i, gi)
    groups[m, j - gj * d].append(d)
for grp in groups.values():
    grp.sort()
    for d1, d2 in zip(grp, grp[1:]):
        ans += min(k, d2 - d1)
    ans += k

print(ans)

G - Propagation

問題

$N$ 頂点 $M$ 辺の単純無向グラフ
頂点 $i$ には値 $i$ がはじめ、書かれている
今から $Q$ 個のクエリを順に処理する
クエリ
- 頂点 $x_i$ に隣接する全ての頂点の値を、その時点で $x_i$ に書かれている値に書き換える
最終的に各頂点に書かれた値を求めよ
$1 \le N,Q \le 2 \times 10^5$

解法

ちょっと難しめの典型として、過去のPASTや典型90などに出題されているので、解いていれば解法は比較的思いつきやすい。（正しく実装できるかは別問題）

典型90の該当問題

隣接する頂点に影響を与えるクエリは、大きく以下の2通りの更新方法がある（名称は勝手に命名）。

方法① プッシュ型
- $x_i$ にクエリが来たら、その都度 $x_i$ の全ての隣接頂点を更新する
方法② プル型、遅延更新型
- 現時点の値が必要になった時に、隣接頂点に更新があったか問い合わせる
- 以下のようにクエリを処理する
  - $x_i$ の現時点の値を求める
    - $x_i$ とその隣接頂点の中で、最も新しいクエリによって更新された値である
    - これを $v$ とする
  - 「私はクエリ $i$ で値 $v$ に更新されました」という情報を $x_i$ に紐付けておく
  - 以降、$x_i$ の隣接頂点 $y$ にクエリが来た際、$y$ はこの情報を参考にする

どちらの方法も、次数の多い頂点に連続してクエリが来たら、更新 or 問い合わせる頂点数が多くなり、$O(NQ)$ かかってしまう。

ここで、頂点を次数によって2種類に分ける。閾値はだいたい $\sqrt{M}$、今回だと最大300～500くらいに設定する。

閾値より次数が小さい頂点については、①で全隣接頂点を更新する。これは高々 $O(\sqrt{M})$ で済む。

①が負担になるのは次数の大きい頂点なので、それに関しては②で遅延更新する。

すると、更新があったか問い合わせる先は、次数が閾値より大きい頂点だけに絞れるので、多くとも (2 * 辺数 / 閾値)、つまり $O(\sqrt{M})$ 個くらいになる。

よって、クエリ1回が $O(\sqrt{M})$ で済み、全体で $O(Q \sqrt{M})$ となる。

①で隣接頂点から更新された時点・値と、②で $x_i$ に紐付ける情報の時点・値は、分けて管理する点に注意。

X-Y-Z    Yが仮に次数の大きい頂点だったとして、
1 2 3    0. 初期状態
2 2 2    1. Yにクエリが来る、X,Zが2になる（遅延更新）
5 2 2    2. 描かれてない他の部分で、X=5 になったとする
5 5 2    3. Xにクエリが来る、Yが5に書き換えられる（即更新）
         4. Zにクエリが来る

このとき、Zの現時点の値は2だが、遅延更新のため配列上はまだ初期の3が入っている。
Yは、現時点の値は5だが、Zに伝播させる過去の遅延更新の値2は、どこかで保持しておく必要がある

Python3

n, m, q = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
xxx = list(map(int, input().split()))

hub_vertices = set()
THRESHOLD = 500
for v in range(n):
    if len(links[v]) >= THRESHOLD:
        hub_vertices.add(v)

major_links = [set() for _ in range(n)]
for v in range(n):
    for u in links[v]:
        if u in hub_vertices:
            major_links[v].add(u)

selected_time = [0] * n
propagated_time = [0] * n
values = list(range(1, n + 1))
lazy_values = [-1] * n

for i, x in enumerate(xxx, start=1):
    x -= 1

    t = propagated_time[x]
    v = values[x]
    for u in major_links[x]:
        if selected_time[u] > t and lazy_values[u] != -1:
            t = selected_time[u]
            v = lazy_values[u]

    selected_time[x] = i
    propagated_time[x] = i
    values[x] = v
    lazy_values[x] = v

    if x in hub_vertices:
        continue

    for u in links[x]:
        propagated_time[u] = i
        values[u] = v

for x in range(n):
    t = propagated_time[x]
    v = values[x]
    for u in major_links[x]:
        if selected_time[u] > t and lazy_values[u] != -1:
            t = selected_time[u]
            v = lazy_values[u]
    values[x] = v

print(*values)

H - Candles

問題

数直線上にろうそくが $N$ 本並んでいる
- ろうそく $i$ は座標 $X_i$ に長さ $A_i$ で火の付いた状態で立っている
- 火の付いたろうそくは1分に1cmずつ短くなっていく
- 長さ0でろうそくは燃え尽き、火が消える
- 火の消えたろうそくの長さは変化しない
あなたは座標0にいて、数直線上を左右に分速1で移動できる
- ろうそくと同じ座標に来たとき、ろうそくの火を消せる
上手く移動して火を消して、残るろうそくの長さの総和を最大化せよ
$1 \le N \le 300$
$-10^9 \le X_i \le 10^9$
$1 \le A_i \le 10^9$

解法

8問体制になってからのABC最終問題って、比較的高度な定理などの知識が要求される教育的な問題が多いイメージだったけど、今回はどちらかというと知識よりは考え方を工夫すれば解ける問題だった。（まぁその工夫がなかなか高度だけど）

小さい例を手元で考えると、どうも左右に行ったり来たりするのが最適となることもあるらしく、貪欲が難しそう。

以下のようなDPを考えるにしても、

$DP'[l][r][k]=$ 座標0から左に $l$ 個、右に $r$ 個のろうそくを止めて、最後に止めたのが $k=0:左端, 1:右端$ だった時に、火を消して確定したろうそく長合計の最大値

実際は長さだけでなく時間も絡んでくるため、これでは上手くいかない。
「途中までのスコアは高いが時間がかかってしまう方法」と「スコアは劣るけど時間が早い方法」だと、 DPには前者しか記録されないが、後から後者に逆転されることもありうる。

かといって、ろうそく長も時間も $10^9$ オーダーの値を取るため、どちらかをさらにDPのキーに加えるのは難しい。

減少量・減少速度で考える

この問題は「全ての火を消すまでの、ろうそくの長さの減少量を最小化」させる問題ともいえる。

どうも「ろうそくの長さが0になったらそれ以上は減らない」ことで、時間によって個々のろうそくが燃え尽きてるのか尽きてないのか判断する必要があることが、 DPの遷移に必要な情報量を増やしてしまっている気がする。

もし、ろうそくの長さが負になっても一律に減り続けるなら計算は少し容易になる。

総減少量に対する1分あたりの減少速度＝残っているろうそくの本数であり、最初は $N$、1本火を止める毎に1ずつ減っていく。

冒頭の $DP'$ と同じ感じで、減少量を管理することを考える。

$DP''[l][r][k]=$ 座標0から左に $l$ 個、右に $r$ 個のろうそくを止めた時点までの、全ろうそくの長さの総減少量

$l,r$ が同じ組は残っている本数が等しいので、仮にその状態になるまでの所要時間が異なっても、その時点での減少速度は等しい。

よって、次の遷移（左または右で次に近いろうそくを止める）までの減少量はそれまでの所要時間に依らずに計算できる。

時間に依らず遷移が等しいなら、減少量さえ管理しておけば十分となり、この $DP''$ で長さが負になり得る場合の正しい答えを求められることがわかる。

ろうそくを無かったことにする

実際には長さは0で打ち止めのため、上記の方法では答えが過小になってしまう。

長さが0以下になるろうそくは、はじめから無かったことにしたい。

最初にろうそくの部分集合を決め打って、それらだけで答えを求めることはできる。

（採用するろうそくの $A_i$ の総和）-（それら全ての火を止めるまでの減少量の最小値）

全ての部分集合での最大値を調べれば正しい答えとなる。
部分集合によっては最適な方法に長さが0以下となるろうそくが含まれることもあり得るが、その場合はそのろうそくが含まれない部分集合からスタートした場合でより高いスコアとなるので、最大値になることは無い。

しかし、全ての部分集合を調べるのはさすがに間に合わない。

ここで、最初に決めておくべきはろうそくの本数（初期の減少速度）だけであり、どのろうそくを採用するかしないかは、ろうそくにたどり着いた時点で決めることができると考える。

あるろうそくにたどり着いたとき、

もしそのろうそくを採用するなら、スコアに $A_i$ を加算し、次からの減少速度は1減る
採用しない（はじめから無かったことにする）なら、減少速度はそのまま

これで減少速度が0になるまでのスコアが答えとなる。

ここで、「スコア」とは「既に採用することが確定した $A_i$ の合計 - まだ確定していないろうそく分も含めたその時点までの減少量」を意味する。

これを実装するにはDPにもう1次元追加する必要があるが、時間やろうそく長と違って $N$ 通りの値しか取らないため、全部で $O(N^3)$ で間に合う。

$DP[l][r][k][c]=$ 座標0から左に $l$ 個、右に $r$ 個までのろうそくに到達していて、これから採用するのが $c$ 本で、いまいる位置が $k=0:左端, 1:右端$ だった時の最大スコア

初期値として $DP[0][0][:][:]$ を $0$ に、他を $-INF$ にしておくことで、様々な $c$ からスタートした場合の答えをまとめて計算できる。

Python3

Pythonでは、次元の小さい添字をより外側に持ってきた方が若干速くなるので、$DP$ の配列で左/右フラグを最も外側にしている。


n = int(input())
left_candles = []
right_candles = []
ans = 0
for _ in range(n):
    x, a = map(int, input().split())
    if x == 0:
        ans += a
    elif x > 0:
        right_candles.append((x, a))
    else:
        left_candles.append((-x, a))

n = len(left_candles)
m = len(right_candles)

INF = 1 << 60
left_candles.append((0, 0))
left_candles.append((INF, 0))
right_candles.append((0, 0))
right_candles.append((INF, 0))

left_candles.sort()
right_candles.sort()

dp = [
    [[[-INF] * (n + m + 1) for _ in range(m + 1)] for _ in range(n + 1)],
    [[[-INF] * (n + m + 1) for _ in range(m + 1)] for _ in range(n + 1)],
]

for k in range(n + m + 1):
    dp[0][0][0][k] = 0
    dp[1][0][0][k] = 0

for i in range(n + 1):
    lx, _ = left_candles[i]
    llx, lla = left_candles[i + 1]

    for j in range(m + 1):
        rx, _ = right_candles[j]
        rrx, rra = right_candles[j + 1]

        for k in range(n + m + 1):
            ls = dp[0][i][j][k]
            rs = dp[1][i][j][k]

            if i < n:
                dp[0][i + 1][j][k] = max(
                    dp[0][i + 1][j][k],
                    ls - (llx - lx) * k,
                    rs - (llx + rx) * k,
                )
                if k > 0:
                    dp[0][i + 1][j][k - 1] = max(
                        dp[0][i + 1][j][k - 1],
                        ls - (llx - lx) * k + lla,
                        rs - (llx + rx) * k + lla,
                    )
            if j < m:
                dp[1][i][j + 1][k] = max(
                    dp[1][i][j + 1][k],
                    ls - (rrx + lx) * k,
                    rs - (rrx - rx) * k,
                )
                if k > 0:
                    dp[1][i][j + 1][k - 1] = max(
                        dp[1][i][j + 1][k - 1],
                        ls - (rrx + lx) * k + rra,
                        rs - (rrx - rx) * k + rra,
                    )

ans += max(dp[0][n][m][0], dp[1][n][m][0])

print(ans)

目次

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）F,G,H問題メモ

F - Cleaning Robot

問題

解法

グループ内の計算

グループの分類方法

G - Propagation

問題

解法

H - Candles

問題

解法

減少量・減少速度で考える

ろうそくを無かったことにする