目次
AtCoder Grand Contest 044 A,B,C,D問題メモ
解法の迷路を彷徨うにあたって道標になるのが「この方向では解けない」という枝刈りであって、これを早期に判断できる知識（と感覚の中間くらいにあるもの）が必要と感じる。
難しい問題では正解の方向を突きつめるだけでそれなりの考察が必要になるので、間違った方向を無理だと判断できず考察してしまうと、時間がいくらあっても足りない。
たまに偶然、最初の考察で上手くいく時があっても、再現性が無い。
A - Pay to Win
問題
- はじめ、$X=0$ である
- 以下の5つの操作を何回でも好きな順に $X$ に適用して、$X=N$ にしたい
- コスト $A$ : $X$ を2倍する
- コスト $B$ : $X$ を3倍する
- コスト $C$ : $X$ を5倍する
- コスト $D$ : $X$ に1を足す
- コスト $D$ : $X$ から1を引く
- 必要な最小コストを求めよ
- $1 \le N \le 10^{18}$
- $1 \le A,B,C,D \le 10^9$
解法
経路探索への転換
$N \le 10^{18}$ と大きいので、DPで $n$ が小さい方から「$X=n$ を達成できる最小コスト」みたいに埋めていくのはできない。
ただ、2倍、3倍していくので、DPは全て埋めなくても結構飛び飛びにしてもいいのでは？
たとえば、$X$ の値を頂点として経路探索みたいにすると、頂点 $n$ からは以下の5つに遷移する。
- コスト $A$ の辺が $2n$ に伸びる
- コスト $B$ の辺が $3n$ に伸びる
- コスト $C$ の辺が $5n$ に伸びる
- コスト $D$ の辺が $n+1,n-1$ に伸びる
頂点は訪れる可能性が生じた時点で初めて作成し、一度訪れた頂点には訪れないようにする。 コストの小さい頂点から確定させていけば、全ての頂点を調べなくとも“一応”答えは出る。
だが、たとえば $A,B,C$ に比べ $D$ だけが小さかったりすると、結局 $D$ の辺が選ばれ $1,2,3,...$ と探索されることになる。これでは間に合わない。
では、$n$ から $N$ までの残りコストを評価関数に加えて、$N$ に近づくほど先に確定させられるようにできないか？ とも考えたが、適当な評価関数がなかなか難しい。（真の値に近いが真の値を超えることはないのが望ましい）
また、これはヒューリスティックな解法であって、マラソンならともかく明確な解法のある問題にはあまり適さない気もする（それが唯一の解法、ということが考えづらい）。
処理をまとめたい
1ずつ足すのを、まとめられないか？
だが、どこまでまとめて足せば都合よく $N$ に近づけられるか、というのが判断しづらい。
N = 155 A = 100, B = 10, C = 10, D = 1 0→1→2→...→6→30→31→155 D D D D C D C
上の例では、$X=6$ まで1ずつ足した後、微調整しながら5倍していくのがよい。 この1ずつ足す処理をまとめようと思えば、事前に「5でも7でもなく、6で止める」というのをわかってないといけないが、これが難しい。
仮にそれを実現する方法があるなら、その方法だけで答えを出せそうな気がする。
ただ、ここで1つ気付くのは、「たくさんまとめて足すことがあるのは、最初だけ」ということ。
たとえば、3をかけた後、1を4回続けて足すのなら、かける前に1回足しておいた方が絶対によい。
B 4D コスト x → 3n → ... → 3x+4 B+4D x → x+1 → 3x+3 → 3x+4 B+2D D B D
なので、$k$ をかけた後は、せいぜい $k-1$ までしか、続けて足したり引いたりする必要は無い。
逆から
「どこかまで1を足し続ける」、そこからは「$k$ をかける」「$0～k-1$ を足したり引いたりする」の繰り返しで作るのはわかった。
しかし、どこまで足し続ければよいかの境界を見極めるのは難しい。
逆から考えるとよい。つまり、$N$ を2,3,5で割ったり±1しながら $0$ にすると考える。
そう考えると、「1ずつ足し引きする」という厄介な遷移を無くすことができる。ある頂点 $x$ について、
- 各 $d=2,3,5$ について
- $x$ が $d$ で割り切れるなら、$\dfrac{x}{d}$ に遷移
- 割り切れないなら、以下の2つに遷移
- $x$ より大きい直近の $d$ の倍数 $y$ まで1を足してから、$\dfrac{y}{d}$ に遷移
- $x$ より小さい直近の $d$ の倍数 $z$ まで1を引いてから、$\dfrac{z}{d}$ に遷移
これで十分である。
訪れた各頂点につき、「$N$ を $x$ にするコスト」+「$x$ から1ずつ引き続けて0にするコスト $=xD$」が、 元の問題で「$x$ まで1を足し続けて、そこからかけ算を含めて $N$ を作るコスト」になる。
この最小値が答えとなる。
計算量は、解説によると $\dfrac{N}{2^a3^b5^c}$ で、$a,b,c$ に適当な整数を代入して作れる数（の、直近の整数）しか探索されない。
従って、$N=10^{18}$ でも $a \le 60, b \le 40, c \le 30$ 程度なので、$2 \times 61 \times 41 \times 31 = 155062$ 以下となる。（実際はもっと少ない）
from heapq import heappop, heappush
def solve(n, a, b, c, d):
q = [(0, n)]
checked = set()
ans = n * d + 1
while q:
cost, x = heappop(q)
print(cost, x)
if cost >= ans:
break
if x in checked:
continue
checked.add(x)
ans = min(ans, cost + d * x)
if x == 0:
continue
div, mod = divmod(x, 2)
if mod == 0:
if div not in checked:
heappush(q, (cost + a, div))
else:
if div not in checked:
heappush(q, (cost + a + d, div))
if div + 1 not in checked:
heappush(q, (cost + a + d, div + 1))
div, mod = divmod(x, 3)
if mod == 0:
if div not in checked:
heappush(q, (cost + b, div))
else:
if div not in checked:
heappush(q, (cost + b + mod * d, div))
if div + 1 not in checked:
heappush(q, (cost + b + (3 - mod) * d, div + 1))
div, mod = divmod(x, 5)
if mod == 0:
if div not in checked:
heappush(q, (cost + c, div))
else:
if div not in checked:
heappush(q, (cost + c + mod * d, div))
if div + 1 not in checked:
heappush(q, (cost + c + (5 - mod) * d, div + 1))
return ans
t = int(input())
for _ in range(t):
n, a, b, c, d = map(int, input().split())
print(solve(n, a, b, c, d))
B - Joker
問題
- $N \times N$ の映画館の座席、初期状態は満席
- 各座席は、以下のように番号が付いている
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
- ここから、$1～N^2$ の順列 $P_1,P_2,...,P_{N^2}$ の順に退席する
- 今いる位置から、隣接する上下左右のどこかの席に移動することを繰り返す
- 正方形の外周のどこかにたどり着けたら、退席完了
- 各人は、退席中、残っている人の席を通過する回数を最小化するように退席する
- 横切る人 $x$、横切られる人 $y$ のペア $(x,y)$ の個数を求めよ
- $2 \le N \le 500$
解法
ちゃんと立ち止まって考えないと、「計算量的に無理」と素通りしてしまいそうな解法。
6×6でも「横切らざるを得ない座席数」は2が最大だったりするので、それなりに大きな例でなければ手元での実験がしづらい問題はちょっと大変。
まず、満席である最初の状態で横切らざるを得ない座席数は、以下の感じ。同心円ならぬ同心正方形？に同じ数字が並ぶ。
⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ❶ ❶ ❶ ❶ ❶ ❶ ⓿ ⓿ ❶ ❷ ❷ ❷ ❷ ❶ ⓿ ⓿ ❶ ❷ ❸ ❸ ❷ ❶ ⓿ ⓿ ❶ ❷ ❸ ❸ ❷ ❶ ⓿ ⓿ ❶ ❷ ❷ ❷ ❷ ❶ ⓿ ⓿ ❶ ❶ ❶ ❶ ❶ ❶ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿
ここからたとえば20の人が退席すると、表の20の位置にある「2」がそのまま、答えに加算される。そして、以下の状態になる。
⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ （●が在席、○が退席済を示す） ⓿ ❶ ❶ ❶ ❶ ❶ ❶ ⓿ ⓿ ❶ ❷ ② ❷ ❷ ❶ ⓿ ⓿ ❶ ❷[❷]❸ ❷ ❶ ⓿ ←[ ]の人は、横切らざるを得ない人数が1人減る ⓿ ❶ ❷ ❸ ❸ ❷ ❶ ⓿ ⓿ ❶ ❷ ❷ ❷ ❷ ❶ ⓿ ⓿ ❶ ❶ ❶ ❶ ❶ ❶ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿ ⓿
この、「$P_i$ の人が退席する時になったら、表の $P_i$ に書いてある数がそのまま答え」となる状態を保てたら楽だな、と思う。
$P_i$ の退席による周囲への影響は、$P_i$ を起点として幅優先探索などすることで更新できる。
ただ、1人の退席は、かなり離れた位置の人まで波及しうる。退席済みの人がいれば尚更である。
... ⓿ ⓿ ⓪ ⓿ ⓿ ⓿ ⓿ ⓿ ...
... ❶[⓿(⓪)⓿]❶ ❶ ❶ ❶ ... ← (ここ)の人が退席すると
... ❷[❶ ⓿ ① ① ① ❶]❷ ...
... ❸[❷ ❶ ❶ ❶ ❶ ❷]❸ ... [ここ]で囲った人たち全員が変わる（図は更新済み）
... ❹[ ]❹ ...
︙︙︙︙︙︙︙︙︙︙
ここで、つい単純に「各 $P_i=1～N^2$ につき、退席時に $N \times N$ のグリッドを探索して更新するので、総計算量は $O(N^4)$ か」と考えてしまう。
実際は更新できなくなったら打ち切っていいので、全員の探索範囲の合計はもっと少ない。
どうやって見積もればよいかというと、更新回数に着目する。各席から横切らざるを得ない席数は、更新できるとすれば、1回の更新で必ず1ずつ減る。
初期状態で●に書かれた数の総和は、❶が $(N-2)^2$ の正方形、❷がその上に加えて $(N-4)^2$ の正方形、……と考えて、$N=500$ でも約 $2.07 \times 10^7$ となる。
全ての $P_i$ からの探索を合わせてこの数しか更新されないため、この方法で間に合う。
探索の実装方法
$P_i$ の人が退席時に横切った人数を $x$ とする。
$P_i$ の上下左右に隣接する席は、まず空席 $P_i$ に移れば、後は同じルートを辿ればよいのだから、多くとも $x$ で可能である。
$P_i$ のたとえば左に隣接する席 $P_i-1$ にとって、さらにそこに隣接する席は以下のようになる。
- $P_i-1$ が空席なら、そのまま $x$ で退席可能
- $P_i-1$ が在席なら、$P_i-1$ の人を横切らないといけないので、$x+1$ で退席可能
このように、ある席が空席ならそのまま、在席ならコストを+1して次のマスに探索を広げればよい。
もちろん、ある席のコストが元から更新値以下なら、$P_i$ 退席による影響はないとして、そこで打ち切ってよい。
Pythonでは
計算量の概算 $10^7$ はちと厳しい。
ただ、言語のバージョンアップによりそれなりに速度も上がっているため、PyPyなら下手なことをしなければ間に合う。
探索にあたり、「上下左右の席をとりあえずキューに放り込み、取り出された時点でチェック・更新する」という方法では、同じ頂点が複数の経路で放り込まれてしまうため、キューが肥大化し、遅くなる。通常はそこまで致命的にはならないが、この問題では避けたい。
「ある席から上下左右を確認する時点で、更新可能なら更新してしまう。更新した場合のみキューに放り込む」という実装方法がよい。
更新可能だとしても1しか更新できないという特徴があるので、後から別経路で更新されようとしても値は既に更新済みで、重複してキューに入れられることはない。
また、この方法ならBFSにしなくてもDFSで実装できる。BFSなら双方向キューが必要となるが、DFSなら通常のListへのappend, popで可能なため、若干速くなる（あくまでこの問題での体験談で、一般に適用されるかは不明）。
また、Pythonでもnumbaを使えば同様に探索に注意すれば通る。
import sys
import numpy as np
from numba import njit
@njit('i4(i4,i4[:])', cache=True)
def solve(n, ppp):
n2 = n + 2
nsq = n2 * n2
seats = np.zeros(nsq, dtype=np.int16)
is_seated = np.zeros(nsq, dtype=np.int8)
for i in range(n):
ud = min(i, n - 1 - i)
ri = (i + 1) * n2
for j in range(n):
ij = ri + j + 1
seats[ij] = min(ud, j, n - 1 - j)
is_seated[ij] = 1
MOVES = np.array([-n2, -1, 1, n2], dtype=np.int32)
ans = 0
for pi in range(n * n):
i, j = divmod(ppp[pi], n)
i = (i + 1) * n2 + j + 1
res = seats[i]
ans += res
is_seated[i] = 0
q = []
for mi in range(4):
ni = i + MOVES[mi]
if seats[ni] > res:
seats[ni] = res
q.append(ni)
while q:
j = q.pop()
val = seats[j]
if is_seated[j]:
val += 1
for mi in range(4):
nj = j + MOVES[mi]
if seats[nj] > val:
seats[nj] = val
q.append(nj)
return ans
n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32) - 1
print(solve(n, ppp))
C - Strange Dance
問題
- $3^N$ 人の人が環状に並ぶ
- ある地点から順番に $0,1,2,...,3^N-1$ と番号が付いていて、地点 $i$ にははじめ、人 $i$ がいる
- 彼らは2種類の曲が流れると、以下のルールに従って移動する
- サルサ
- 自身の地点を3進数で表して、“1” と “2” を入れ替えた地点に移動する
- たとえば地点46にいる人は、$46=1201_3→2102_3=65$ なので地点65へ移動する
- ルンバ
- 自身の地点の番号を1つ増やした位置に移動する
- 地点 $3^N-1$ にいた人は地点0に移動する
- 今、曲が文字列 $T$ で表される順で流れた
- $T$ の $i$ 文字目が 'S' ならサルサ、'R' ならルンバが $i$ 番目に流れたことを表す
- 全ての曲が流れた後の、$i=0～3^N-1$ のそれぞれの人のいる地点を答えよ
- $1 \le N \le 12$
- $1 \le |T| \le 2 \times 10^5$
解法
愚直にやったら、各 $3^N$ の人に $|T|$ の曲を適用し、特にサルサは桁毎に見る処理が入るのでさらに $N$ かかり、$O(N3^N|T|)$ となる。
まず、サンプル3の出力例あたりを、3進数で表してみる。以下、基本的に地点番号は3進数で表す。
23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10 ↓ 212 100 211 022 010 021 202 220 201 012 200 011 122 110 121 002 020 001 112 000 111 222 210 221 102 120 101
1の位だけ取り出すと、2,0,1が繰り返されている。
212 100 211 022 010 021 202 220 201 012 200 011 122 110 121 002 020 001 112 000 111 222 210 221 102 120 101 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1
下2桁を取り出すと、9個の00～22の同じ並びが3回繰り返されている
212 100 211 022 010 021 202 220 201 | 012 200 011 122 110 121 002 020 001 | 112 000 111 222 210 221 102 120 101 12 00 11 22 10 21 02 20 01 | 12 00 11 22 10 21 02 20 01 | 12 00 11 22 10 21 02 20 01
$N=5$ なら、答えとなる273人の下4桁を見ると、同じ81個の数の並びが3回繰り返されていることになる。
これは偶然ではなく、必ずこうなる。（ある桁の動きは、それより下の桁の動きに影響しないので）
よって、「初期位置の下 $k$ 桁が同じ人は、最終位置の下 $k$ 桁も一緒」ということはわかる。
初期位置 000 001 002 010 011 012 020 021 022 100 101 102 ...
最終位置 212 100 211 022 010 021 202 220 201 012 200 011
初期位置の下1桁 0 1 2 0 1 2 0 1 2 0 1 2 ...
最終位置の下1桁 2 0 1 2 0 1 2 0 1 2 0 1 ...
初期位置の下2桁 00 01 02 10 11 12 20 21 22 00 01 02 ...
最終位置の下2桁 12 00 11 22 10 21 02 20 01 12 00 11 ...
~~~~~~~~~~ ~~~~~~~~~~
ということは、たとえば下2桁の最終位置が既に計算済みだったとして、
?00 ?01 ?02 ?10 ?11 ?12 ?20 ?21 ?22 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ?02 ?00 ?21 ?12 ?10 ?01 ?22 ?20 ?11
9個それぞれにつき、「?」の初期位置の値が0,1,2だった場合の動きを追って最終位置を求めてやれば下3桁それぞれ、計27個の最終位置が分かる。
さらにそれを元に、下から4桁目を“?”としつつ ?000～?222 それぞれついて $? = 0,1,2$ の場合をシミュレーションすると、計81個の最終位置が分かる。
この繰り返しで解ける。
$d$ 桁目の動きのシミュレーション
繰り上がりがキーワードとなる。
$d$ 桁目も、初期値が同じなら途中まではほとんど同じ動きをする。唯一、ルンバによる繰り上がりがそれを乱し、一度乱された後は別の動きとなる。
しかし、とあるルンバによる繰り上がりが $d$ 桁目にまで波及するというのは、
それが流れたタイミングで $d-1$ 桁以下が 222…2 の場合のみに限られ、
それに該当する初期位置は桁が増える毎にどんどん少なくなる。
それ以外の初期位置にとって、そのルンバは実質的に無視できる、という考え方である。
$d-1$ 桁目以下の動きを事前計算している間に、$d$ 桁目まで波及する曲も同時にメモしておく。
- サルサ
- 同時に全ての桁に波及する
- ただし、連続した2つのサルサは、単に元に戻るだけなので、無いのと同じである
- ルンバ
- 自身が“2”の時に下の桁から繰り上がってきたときのみ、上の桁にも波及する
- その他は、上の桁にとっては無いのと同じである
S R R S R S R S 初期位置の下6桁が 012012 の時に
7桁目まで波及してくる曲がこうだとする
1 2→0 1 2→0 0 1 2 初期位置の7桁目が"1"だとしてシミュレートすると、
* * "*"のルンバでのみ繰り上がりが発生する
S R S R S S 8桁目に波及するRは、7桁目で繰り上がりが発生したもののみ残す
S R S R 2つ連続するSは消す
→下7桁が"1012012"の場合は、「S R S R」のみが流れたとして8桁目を動かしてよい
計算量
シミュレーション回数が、桁を増やす毎に場合分けが3倍になっていくので $\displaystyle 3+9+27+... = \sum_{k=1}^{N} 3^k = \frac{3(3^N-1)}{2}$ で、$O(3^N)$ となる。
1回のシミュレーション毎に、その桁まで波及する曲数分の計算が必要になるが、これは上記のように $|T|$ から桁を増やす毎に減っていく。
まぁ、1桁増やすとざっくり3分の1くらいになると考えると、
- 1桁目の3回の処理でそれぞれ $|T|$
- 2桁目の9回の処理でそれぞれ $|T|/3$
- 3桁目の27回の処理でそれぞれ $|T|/9$
- …
となり、各桁で $3|T|$ ずつ、$N$ 桁で計 $O(N|T|)$ となる。全て合わせて $O(3^N+N|T|)$ で可能となる。
n = int(input())
t = input()
op = [[c == 'R' for c in t]]
ans = [0]
for d in range(n):
k = 3 ** d
nop = []
nans = []
for g in range(3):
for i in range(k):
opn = []
h = g
for o in op[i]:
if o == 0:
if len(opn) > 0 and opn[-1] == 0:
opn.pop()
else:
opn.append(0)
if h != 0:
h = 3 - h
else:
h += 1
if h == 3:
h = 0
opn.append(1)
nop.append(opn)
nans.append(h * k + ans[i])
op = nop
ans = nans
print(*ans)
D - Guess the Password
問題
- インタラクティブ問題。入力は与えられない
- クエリを投げて、パスワード $S$ を特定せよ
- パスワードの制約
- 英小文字・英大文字・数字からなる
- 長さは1文字以上128文字以下
- クエリ
- 入力: パスワードの制約に適する文字列 $T$
- 出力: $S$ と $T$ のレーベンシュタイン距離
- 投げられるクエリは850回まで
解法
文字数の特定
まず、使える62文字がそれぞれ何文字あるかを特定する。
'aaaaa…a' という1種の文字だけの128文字のクエリを投げると、「128-(その文字が使われる回数)」が返ってくる。
これを62文字に繰り返すと各文字の使用回数がわかり、その合計で $S$ の文字数もわかる。
部分列のマージ
'a' が3回、'b'が2回使われることがわかったとする。
次は、これが $S$ に出てくる順は 'aaabb' なのか 'ababa' なのか 'baaba' なのか、つまり部分列を特定する。
一般に、$S$ の中に $T$ が部分列で現れるなら、クエリの答えは $|S|-|T|$ となる。
現れない場合、$T$ の要素を置換や削除対象にせねばならず、どうしても $|S|-|T|$ より多くなる。
これにより、部分列かどうかが判定できる。
'aaa' に 'b'を位置を1つずつずらしながら仮追加していき、位置を特定する。
×: Sの部分列でない ○: Sの部分列である baaa → × bを1つずらす abaa → ○ このbは確定、次のbの位置の探索に移る abbaa → × ababa → × これが違うなら、abaab 確定
また、これは単独文字種に限定しなくても「$S$ の部分列であることがわかっている文字列」同士でも成り立つ。
（ただし2つの文字列に同じ文字が使われていない場合、という条件が付くが、 単独文字の部分列からはじめてマージを繰り返していく上では、被ることはない）
これで、全てが1つになるまでマージを繰り返していけば、それが答えとなる。
クエリ回数
まず各文字の使用回数の特定で62回かかる。
次にマージだが、2つの部分列を $P,Q$ として、1回のマージに最悪で $|P|+|Q|-1$ かかる。
よって、なるべく小さい部分列を優先的に結合して、大きいのは後回しにしたい。
$P,Q$ の一方に、ある部分列が使われるのを1回（両方なら2回）として、
- ①長さが $\dfrac{|S|}{2}$ 以上の部分列が使われるのは、高々2回である
- ②長さが $\dfrac{|S|}{4}$ 以上の部分列が使われるのは、高々4回である（①を除く）
- ③長さが $\dfrac{|S|}{8}$ 以上の部分列が使われるのは、高々8回である（①②を除く）
- …
なので、だいたい $|S|\log_2{|S|}$ と見積もれる。
実際に計算するとこれは $|S|=128$ で896回となりオーバーしてしまうのだが、
- マージ1回のクエリ数 $|P|+|Q|-1$ の'-1'を含めると、マージは最悪127回あるので、実際は769回
- 文字数は62文字なので、いくつかの文字は最初から2個以上ある（いくらかは最初からマージされた状態と見なせる）
より、間に合う。
ヒープキューなどで文字数が短い部分列から取り出せるようにしておき、先頭2つをマージして結果を戻す、を繰り返せばよい。
import string
from heapq import heapify, heappop, heappush
STR = string.ascii_letters + string.digits
counter = {}
for c in STR:
print(f'? {c * 128}')
a = int(input())
if a == 128:
continue
counter[c] = 128 - a
l = sum(counter.values())
q = [(cnt, [c] * cnt) for c, cnt in counter.items()]
heapify(q)
while len(q) > 1:
l1, t1 = heappop(q)
l2, t2 = heappop(q)
i = 0
j = 0
while i < len(t1) and j < l2:
t1.insert(i, t2[j])
s = ''.join(t1)
print(f'? {s}')
a = int(input())
if len(t1) > l - a:
t1.pop(i)
else:
j += 1
i += 1
if j < len(t2):
t1.extend(t2[j:])
heappush(q, (l1 + l2, t1))
_, t = q[0]
s = ''.join(t)
print(f'! {s}')
