ABC257解説（G問題まで） - 競プロ勉強メモ

注意事項

ACコードとして載せてある言語は、全てPyPy3(7.3.0)を使用しております。

有名アルゴリズムを用いる際は、他のサイトやブログへのリンクを貼らせて頂いておりますので、詳しい解説等が知りたい方はそちらを参照して頂ければと思います。

ABC257のリンク↓

atcoder.jp

A - A to Z String 2

問題概要

Aを $N$ 個、Bを $N$ 個、…、Zを $N$ 個をこの順に並べてできる文字列のX文字目を出力せよ。

制約

$1 \le N \le 200$
$1 \le X \le N \times 26$
入力は全て整数

考えたこと

0-indexedで考えると、 $[0, N), [N, 2N), ..., [25N, 26N)$ の各区間がA, B, ..., Zになる。よって、 $X$ がそれらの区間のうちどれに入っているかを求めればよさそう。具体的には、以下の式によって求めることができる：

$\lfloor (X-1)/N \rfloor = k \Leftrightarrow X \in [kN, (k+1)N)$

あとはこの $k$ を英大文字に変換したい。PyPy3ならord()で文字コードを取得、chr()で文字コードを文字に変換できるので、chr( $k$ + ord("A"))とすればよい。

ACコード

https://atcoder.jp/contests/abc257/submissions/32825247

B - 1D Pawn

問題概要

左右1列に並んだ長さ $N$ のマス目がある。また、 $K$ 個のコマがマス目上に置かれており、コマ $i$ はマス $A_i$ に置かれている。

これらのコマに対し、操作を $Q$ 回行う。 $i$ 回目の操作では以下を行う：

コマ $L_i$ を1つ右に動かす。
ただし、そのように動かせない場合、すなわちコマ $L_i$ が「マス $N$ にある」または「1つ右のマスに別のコマがある」場合は何も行わない。

$Q$ 回の操作が終わった後の各コマの位置を出力せよ。

制約

$1 \le K \le N \le 200$
$1 \le A_1 \lt A_2 \lt \dots \lt A_K \le N$
$1 \le Q \le 1000$
$1 \le L_i \le K$
入力は全て整数

考えたこと

言われた通りのシミュレーションをすればよさそう。

実装上の留意点

実際に「マス目」を持つ必要はなく、各コマの位置を持った配列 $A$ 上で行えばよい。コマ $L_i$ の右隣のマスに既にコマがあるかどうかは、 $A [ L_{i+1} ] = A [ L_i ] + 1$ であるかどうかで判定できる。このとき、配列外参照に気を付ける。

更に、「番兵」を設置するというテクニックがある。仮想的に、マス $N+1$ にコマ $K+1$ を配置しておけば、前述の配列外参照や「マス $N$ にある」かの判定で場合分けがいらなくなる。

ACコード

https://atcoder.jp/contests/abc257/submissions/32825798

C - Robot Takahashi

問題概要

子供と大人が合わせて $N$ 人おり、人 $i$ の体重は $W_i$ である。また、0, 1からなる長さ $N$ の文字列 $S$ が与えられ、 $S_i$ が0なら人 $i$ は子供、1なら人 $i$ は大人であることを表している。

ロボットである高橋君は、設定された実数 $X$ に応じて、体重が $X$ 未満の人を”子供”、X以上の人を"大人"と判定する。適切に実数 $X$ を定めたときの、高橋君によって子供か大人か正しく判定される人数の最大値を求めよ。

制約

$1 \le N \le 2 \times 10^5$
$Sは0, 1からなる長さNの文字列$
$1 \le W_i \le 10^9$
入力は全て整数

考えたこと

「とりあえず何かを決め打って結果を観察してみる」のが、解法を考える上での鉄則。今回は $X$ を決め打った時の高橋君の判定結果を観察してみると、 $W$ を予め昇順にソートしておけば下図のような判定結果が得られることがわかる。

このとき正しく判定される人数は「左の区間内にある子供の数」+「右の区間内の大人の数」のはず。これは愚直に求めようとすると $O(N)$ となるが、子供を0, 大人1とした数列の累積和を予め求めておけば、 $O(1)$ で求めることができる。（「子供の数」は「区間の長さ」-「大人の数」で求まる。）

あとはこれを $X$ 、すなわち境目の位置について全探索すればよいので、全体 $O(N)$ で解けました。

ACコード

https://atcoder.jp/contests/abc257/submissions/32826576

D - Jumping Takahashi 2

問題概要

2次元平面上に $N$ 個のジャンプ台がある。ジャンプ台 $i$ は $(x_i, y_i)$ にあり、パワーは $P_i$ である。

高橋君のジャンプ力を $S$ とすると、高橋君は以下の条件を満たす場合に限りジャンプ台 $i$ からジャンプ台 $j$ に移動できる：

$P_i S \ge |x_i - x_j| + |y_i - y_j| (= manhattan(i, j))$

条件「適切に始点となるジャンプ台を1つ選べば、どのジャンプ台にも始点から0回以上の移動で到達できる」…（※）を満たす整数 $S$ の最小値を求めよ。

制約

$2 \le N \le 200$
$-10^9 \le x_i, y_i \le 10^9$
$1 \le P_i \le 10^9$
$(x_i, y_i) \neq (x_j, y_j) (i \neq j)$
入力は全て整数

考えたこと

$S$ を決め打つと、各ジャンプ台の組 $(i, j)$ についてジャンプ台 $i$ からジャンプ台 $j$ に移動できるかが条件式から定まり、 $N$ 頂点 $O(N^2)$ 辺の有向グラフが構築できる。このグラフが条件（※）を満たしているかは、BFSを始点を変えながら $N$ 回試すことで $O(N^3)$ で判定できる。

また、 $S$ は条件（※）について単調性がある。すなわち、ある値で（※）を満たした場合、それより大きい値でも必ず（※）を満たす。

「単調性がある」かつ「真偽判定が高速にできる」ときの境目を見つける問題（例えば条件を満たす最大値や最小値を求める問題）では、決め打ち二分探索が有効。すなわち、 $S$ を解としてあり得る範囲で二分探索すれば、 $O( (\text{判定の計算量}) \times log(\text{解の範囲}) )$ で解ける。

では解の範囲は具体的にいくらだろう。下界は明らかに0としてよい。上界は最も遠い2ヵ所にジャンプ台を配置すればよさそう。 $(10^9, 10^9)$ と $(-10^9, -10^9)$ のマンハッタン距離は $4 \times 10^9$ で、 $P = 1$ のとき $S$ は最大となるはず。よって、上界は $4 \times 10^9$ とわかる。

以上より、 $O(N^3 log ( max( |x_i|, |y_i| ) )$ で解けました。

実装上の留意点

二分探索には色々書く流儀があるが、「めぐる式二分探索」を強くお勧めする。

別解

二分探索をせずワーシャル・フロイド法を応用することで $O(N^3)$ で解く解法があるらしい。

まず、各ジャンプ台を頂点とし、ジャンプ台の組 $(i, j)$ について $i$ から $j$ に重み $\lceil manhattan(i, j)/P_i \rceil$ の有向辺を張ったグラフを考える。このグラフ上で、ある(i, j)パス上の辺の重みの最大値は、そのパスを使うための $S$ の最小値を表している。(i, j)パスは当然複数個考えられるが、それらの「パス上の辺の重みの最大値」の最小値を $dp [ i ] [ j ]$ と定義し、これを求めたい。

（仮にこのdpテーブルが求まったとき、解は $\underset{i}{min} ( \underset{j}{max} ( dp [i ] [j ] ) )$ となる。）

ワーシャルフロイド法は「中継点として使ったのが $k$ までとしたときの暫定dpテーブル」をin-placeに求めていく。本来の遷移式は

$dp [ i ] [ j ] = min ( dp [ i ] [ j ], dp [ i ] [ k ]+dp [ k ] [ j ] )$

として最短距離を求めていくが、これを

$dp [ i ] [ j ] = min ( dp [ i ] [ j ], max ( dp [ i ] [ k ], dp [ k ] [ j ] ) )$

と書き換えるだけでいい（らしい）。はえーすっごい。

ACコード

本解法（決め打ち二分探索）

https://atcoder.jp/contests/abc257/submissions/32828959

別解（ワーシャル・フロイド風）

https://atcoder.jp/contests/abc257/submissions/32828081

E - Addition and Multiplication 2

問題概要

整数 $x = 0$ がある。この $x$ に対して、以下の操作を好きな回数行える。

整数 $i ( 1 \le i \le 9)$ を選ぶ。 $C_i$ 円を払い、 $x$ を $10x + i$ に置き換える。

$N$ 円の予算で得られる $x$ の最大値を求めよ。

制約

$1 \le N \le 10^6$
$1 \le C \le N$
入力は全て整数

考えたこと

できる限り大きい数字を作りたいときは

桁数を大きくする。
上位の桁に大きい数字を置く。

の優先順位で考えればよい。

予算 $N$ 円内で桁数を最大化したければ、最も安い数字をできる限り使うのが明らかに最適。よって、求める解の桁数 $K$ は $C_m = \underset{i}{min}(C_i)$ として

$K = \lfloor N/C_m \rfloor$

だとわかる。

あとは、この桁数が達成できる範囲で9, 8, ..., 1と順に貪欲に使っていけばよい。現状の予算と残り桁数をそれぞれ $n, k$ として、while文で $\lfloor (n - C_i )/C_m \rfloor = k-1$ である限り整数 $i$ を使う、と言う形で書くだけ。

実装上の留意点

$K$ は最大で $10^6$ となるので、 $x$ はintではなくlistで持つ。

ACコード

https://atcoder.jp/contests/abc257/submissions/32830865

発展的な話題

予算 $N$ 円を「ぴったり使い切る」必要がある場合はどうすればいいだろう？

結論を言ってしまうと、以下のdpで解ける：

$dp [ i ] [ j ] := 数字iまでを使って残り予算がjのときの、xの最大桁数$

$（ただし、数字は1, 2, ..., 9と昇順に見ていくものとする。）$

数字を昇順に見ていくのは不自然に思えるかもしれないが、これがdpテーブルを埋めた後に効いてくる。

dp遷移を考えよう。

単純に考えると、数字 $i$ まで使って残り予算が $j$ の状態からは、

$i+1を0個使って、数字i+1まで使って予算がjの状態になり、\\桁数が0増える。$
$i+1を1個使って、数字i+1まで使って予算がj-C_{i+1}の状態になり、 \\桁数が1増える。$
$i+1を2個使って、数字i+1まで使って予算がj-2C_{i+1}の状態になり、\\桁数が2増える。$
$\dots$

という遷移が考えられるため、これを使ってmaxで更新していけばよさそう。

しかし、これを愚直に行うと各 $(i, j)$ の組に対して $O(N)$ の遷移が発生し、全体 $O(N^2)$ となるため間に合わない。

そこで、遷移を次のように捉えてみる：

数字 $i$ を使うか決めるフェーズで残り予算が $j$ の状態からは、

追加で $i$ を1つ使う。
$i$ を使うフェーズを終了し、 $i+1$ を使うフェーズに移る。

とする。これなら各 $(i, j)$ の組に対して遷移は $O(1)$ となり間に合う。

（この遷移の工夫は、個数制限なしナップザック問題とかで有名。）

さて、これで無事dpテーブルが埋め終わったので、あとは $dp [ 9 ] [ N ]$ を見れば答えが…書いてない！それはそうで、まだ $x$ の桁数を求めただけで具体的な $x$ の値は何も求めていない。なので、ここからはdp復元を行う。

$dp [ 9 ] [ N ]$ からスタートし、「そこに書き込まれた数はどこから来たか？」を考える。先ほどの遷移を逆に辿ればよく、 $dp [ 9 ] [ N-C_9 ] = dp [ 9 ] [ N ]-1$ であれば移動、そうでないなら $dp [ 8 ] [ N ]$ に移動、とすればよい。

ここでdpテーブルを埋める際に数字を昇順に見た効果が出る。もし $dp [ i ] [ j-C_i ] = dp [ i-1 ] [ j ]-1 = dp [ i ] [ j ]-1$ であれば、どっちに進んでも最終的に $dp [ 1 ] [ 0 ]$ に到達できてしまうが、ここで優先的に $dp [ i ] [ j-C_i ]$ に進むと決めることで「上位の桁に大きい数字を置く」が実現でき、最適解 $x$ が自然に復元できる。

以上より、 $O(N)$ で解けました。

例題：

atcoder.jp

F - Teleporter Setting

問題概要

$N$ 個の町と $M$ 個のテレポーターがある。テレポーター $i$ は2つの町 $U_i, V_i$ を双方向に結んでいて、使用することで一方の町からもう一方の町へ1分で移動できる。しかし、 $U_i = 0$ のときは $U_i$ 側の繋げ先が未定であることを表している。

$i = 1, 2, \dots, N$ それぞれについて、繋げ先が未定のテレポーターを全て町 $i$ に繋げたときの、町 $1$ から町 $N$ への最低所要時間を求めよ。（移動できない場合は-1を出力）

制約

$2 \le N \le 3 \times 10^5$
$1 \le M \le 3 \times 10^5$
$0 \le U_i \lt V_i \le N$
$(U_i, V_i) \neq (U_j, V_j) (i \neq j)$
入力は全て整数

考えたこと

各 $i$ についてBFSすれば $O( N ( N+M ) )$ で解けるが、当然間に合わないのでどうにか「どの $i$ についても使いまわせる情報」を見つけたい。

どの $i$ についても成り立つ性質として、「繋げ先が未定のテレポーターは全て同一の頂点 $i$ に繋がれている」という点に注目する。これを、入力に合わせて「仮想頂点 $0$ に繋いでいる」と捉えてあげた $N+1$ 頂点のグラフを考えてみよう。

このグラフにおいて、繋げ先が未定のテレポーターの繋げ先を $i$ とすることは、2頂点 $(i, 0)$ 間に重み0の辺を張ることで表現できる。

このようにして構築したグラフにおいて、 $1 \text{-} N$ 間の最短経路は必ず以下の図に示す3パターンのどれかになる：

ここで、青で示した省略部分の距離は、予め頂点 $1$ と $N$ からそれぞれBFSしておくことで前計算ができる。これを配列 $dist_1, dist_N$ とおくと、各 $i$ についての求める解は

$min(dist_1 [ i ]+dist_N [ 0 ], dist_1 [ 0 ]+dist_N [ i ], dist_1 [ N ])$

となる。

以上より、 $O(N+M)$ で解けました。

ACコード

https://atcoder.jp/contests/abc257/submissions/32746559

G - Prefix Concatenation

問題概要

英子文字からなる2つの文字列 $S, T$ が与えられる。

（相異なってもよい） $S$ の接頭辞を $k$ 個連結することで $T$ と一致させられるような最小の正整数 $k$ を求めよ。（不可能な場合は-1を出力）

例：　 $S$ = aba, $T$ = ababaab　なら、 $T$ = ab + aba + ab より、 $k=3$

制約

$1 \le |S| \le 5 \times 10^5$
$1 \le |T| \le 5 \times 10^5$
$S, Tは英子文字のみからなる文字列$

考えたこと

Z-algorithmを使うことで

$Z [ i ] := Tのi文字目から始めて、最大何文字がSの接頭辞と一致するか？$

を $O(|S|+|T|)$ で求めることができる。

これを使えば問題をDAG上の最短経路問題に言い換えることができる。すなわち、 $i = 0, 1, \dots , |T|-1$ について、頂点 $i$ から頂点 $i+1, i+2, \dots , i+Z [ i ]$ に有向辺を張ったグラフにおいて、頂点 $0$ から頂点 $|T|$ までの最短経路を求めればよい。

DAG上の最短距離はdpで求まるのが通説。しかし、今回のグラフは辺の本数が $O(|S| |T|)$ なので、

$dp [ i ] := 頂点0から頂点iまでの最短距離$

という単純なdpでは間に合わない。

そこで、次のようなdpを考える：

$dp [ i ] := 頂点0からの距離がi以下である最大の頂点$

初期化：

$dp[ i ] = \left \{ \begin{array}{l} 0 \ \ (\text{if} \ i = 0) \\ \infty \ \ (\text{else}) \end{array} \right.$

このdpテーブルを、頂点 $i = 0$ から順に見ていくことでin-placeに更新していく。

頂点 $i-1$ まで見終わって、その時点での暫定的なdpテーブルが求まっているとする。（このdpテーブルはグラフがDAGであることと定義より単調増加であることが保証される。）

頂点 $i$ を見るとき、まずdpテーブルから「 $i$ 以上で最左の要素」を求め（求め方は後述）、そのindexを $j$ とおく。このとき、 $j$ は頂点 $i$ 以上に到達するまでの最小移動回数を表している。

頂点 $i$ からは頂点 $i+1, i+2, \dots , i+Z [ i ]$ に移動できる。ということは、距離 $j+1$ 以下である最大の頂点は $i+Z [ i ]$ に（暫定の $dp [ j+1 ]$ より大きければ）更新できる。ただし、初期化を $\infty$ で行っているため、その場合は特別に必ず更新するようにする。