サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219)F,G,H問題メモ
F - Cleaning Robot
問題
グリッド上を $(0,0)$ からスタートしてLRUDの命令に従って動くロボットがある
文字列 $S$ を $K$ 回繰り返した文字列を命令とするとき、ロボットが通過するマス数を求めよ
$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
問題
解法
ちょっと難しめの典型として、過去のPASTや典型90などに出題されているので、解いていれば解法は比較的思いつきやすい。
(正しく実装できるかは別問題)
隣接する頂点に影響を与えるクエリは、大きく以下の2通りの更新方法がある(名称は勝手に命名)。
どちらの方法も、次数の多い頂点に連続してクエリが来たら、更新 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
問題
解法
8問体制になってからのABC最終問題って、比較的高度な定理などの知識が要求される教育的な問題が多いイメージだったけど、
今回はどちらかというと知識よりは考え方を工夫すれば解ける問題だった。(まぁその工夫がなかなか高度だけど)
小さい例を手元で考えると、どうも左右に行ったり来たりするのが最適となることもあるらしく、貪欲が難しそう。
以下のようなDPを考えるにしても、
実際は長さだけでなく時間も絡んでくるため、これでは上手くいかない。
「途中までのスコアは高いが時間がかかってしまう方法」と「スコアは劣るけど時間が早い方法」だと、
DPには前者しか記録されないが、後から後者に逆転されることもありうる。
かといって、ろうそく長も時間も $10^9$ オーダーの値を取るため、どちらかをさらにDPのキーに加えるのは難しい。
減少量・減少速度で考える
この問題は「全ての火を消すまでの、ろうそくの長さの減少量を最小化」させる問題ともいえる。
どうも「ろうそくの長さが0になったらそれ以上は減らない」ことで、
時間によって個々のろうそくが燃え尽きてるのか尽きてないのか判断する必要があることが、
DPの遷移に必要な情報量を増やしてしまっている気がする。
もし、ろうそくの長さが負になっても一律に減り続けるなら計算は少し容易になる。
総減少量に対する1分あたりの減少速度=残っているろうそくの本数であり、最初は $N$、1本火を止める毎に1ずつ減っていく。
冒頭の $DP'$ と同じ感じで、減少量を管理することを考える。
$l,r$ が同じ組は残っている本数が等しいので、仮にその状態になるまでの所要時間が異なっても、その時点での減少速度は等しい。
よって、次の遷移(左または右で次に近いろうそくを止める)までの減少量はそれまでの所要時間に依らずに計算できる。
時間に依らず遷移が等しいなら、減少量さえ管理しておけば十分となり、この $DP''$ で長さが負になり得る場合の正しい答えを求められることがわかる。
ろうそくを無かったことにする
実際には長さは0で打ち止めのため、上記の方法では答えが過小になってしまう。
長さが0以下になるろうそくは、はじめから無かったことにしたい。
最初にろうそくの部分集合を決め打って、それらだけで答えを求めることはできる。
全ての部分集合での最大値を調べれば正しい答えとなる。
部分集合によっては最適な方法に長さが0以下となるろうそくが含まれることもあり得るが、
その場合はそのろうそくが含まれない部分集合からスタートした場合でより高いスコアとなるので、最大値になることは無い。
しかし、全ての部分集合を調べるのはさすがに間に合わない。
ここで、最初に決めておくべきはろうそくの本数(初期の減少速度)だけであり、
どのろうそくを採用するかしないかは、ろうそくにたどり着いた時点で決めることができると考える。
あるろうそくにたどり着いたとき、
これで減少速度が0になるまでのスコアが答えとなる。
ここで、「スコア」とは「既に採用することが確定した $A_i$ の合計 - まだ確定していないろうそく分も含めたその時点までの減少量」を意味する。
これを実装するにはDPにもう1次元追加する必要があるが、
時間やろうそく長と違って $N$ 通りの値しか取らないため、全部で $O(N^3)$ で間に合う。
初期値として $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)