AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）E,G問題メモ

AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）

E - Expansion Packs

• $N$ 枚のカードが入ったパックが無限にあります。
• 各パックについて、$i$ 枚目に入っているカードは $P_i\%$ の確率でレアです。各カードがレアであることは他のカードがレアであることと独立です。
• これからパックを一つずつ開封していき、開封したパックに入っているすべてのカードを手に入れます。
• レアカードを合計 $X$ 枚以上手に入れるまでパックを開封するとき、開封するパックの個数の期待値を求めてください。

• $1 \leq N \leq 5000$
• $1 \leq X \leq 5000$
• $1 \leq P_i \leq 100$
• 入力される値はすべて整数

2つのDPの組合せ。

まず、1つのパックに入っているレアの枚数毎に、確率を求める。

• $\mathrm{DP_P}[i,j]:=$ 1つのパックの中で、$i$ 枚目までを見て、レアがちょうど $j$ 枚出ている確率

$\mathrm{DP_P}[0,0]=1$ から開始する。
$\mathrm{DP_P}[i-1,j]$ からは $P_i \%$ の確率で $\mathrm{DP_P}[i,j+1]$ に、$100-P_i \%$ の確率で $\mathrm{DP_P}[i,j]$ に遷移する。

          ...  j  j+1 ...
i-1           ○
    x(100-Pi)%↓↘xPi%
i             ○  ○

$O(N^2)$ で全て求まる。
$\mathrm{DP_P}[N,j]$ を、以降、$R_j$ と表す。これを使って次のDPをする。

• $\mathrm{DP_E}[k]:=$ 今までにレアカードが $k$ 枚出ている状態から $X$ 枚出るまでに開封するパックの個数期待値

初期値として $\mathrm{DP_E}[k]=0$（$k \ge X$）は確定してして、$k=X-1,X-2,...,0$ を求めていく。

$\mathrm{DP_E}[k]$ からは、下記のように $N+1$ 通りに、それぞれの確率で遷移する。

     k      k+1  k+2  ...  k+N
  ┌○--R1-->○   ○        ○
R0│↑\-----R2----^         ^
  └┘ `----------RN--------'

もらうDPで考えると、$\displaystyle \mathrm{DP_E}[k]=1+\sum_{j=0}^{N}\mathrm{DP_E}[k+j] R_j$

整理して、$\displaystyle \mathrm{DP_E}[k]=\frac{1+\sum_{j=1}^{N}\mathrm{DP_E}[k+j] R_j}{1-R_0}$

これで $O(NX)$ で $\mathrm{DP_E}[0]$ が求まり、それが答えとなる。

Python3

G - Tile Distance 3

• $xy$ 座標平面上に以下のように $1 \times K$ または $K \times 1$ のタイルが無限に敷き詰められています。
  • （厳密な定義は問題ページ参照）

y|
_|_____|_|_|_|_____|_    例) K=3
_| | | |_____| | | |_
_| | | |_____| | | |_
_|_|_|_|_____|_|_|_|_
 |_____| | | |_____|      ^
 |_____| | | |_____|      K
_O_____|_|_|_|_____|__x   v 
 | | | |     | | | |
 
 <--K-->

• $(S_x + 0.5, S_y + 0.5)$ を含むタイルから隣接しているタイルに移動することを繰り返して $(T_x + 0.5, T_y + 0.5)$ を含むタイルに移動するとき、隣接するタイルに移動する回数の最小値を求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \leq T \leq 10^4$
• $2 \leq K \leq 10^{16}$
• $-10^{16} \leq S_x, S_y, T_x, T_y \leq 10^{16}$
• 入力される値はすべて整数

場合分け地獄。

以下、$K \times K$ ごとに同じ向きのタイルが敷き詰められた領域のことを単に「領域」と呼ぶ。
また、横向きのタイルが敷き詰められているのを「横領域」、縦向きを「縦領域」とする。
また、領域を1マスと考えて左から $i$ 番目、下から $j$ 番目の領域を $\langle i,j \rangle$ とする。（0-indexed）

少しでも場合分けを減らすため、反転・平行移動して、 始点を $\langle 0,0 \rangle$、終点を始点より右上に来るように揃える。

• $0 \le S_x \lt K$
• $0 \le S_y \lt K$
• $S_x \le T_x$
• $S_y \le T_y$

この時、必要に応じて座標を反転させる必要があるのだが、少し注意を要する。
たとえば $S_x$ と $T_x$ との大小関係を入れ替えるため $y$ 軸にしたがって左右反転させたいとき、 今回のグリッドの定義では $0$ は正側に属しているので、$S_x$ のちょうど対象の位置は $-S_x-1$ となる。

... -4 -3 -2 -1| 0  1  2  3  4
    □ □ □ □|□ □ □ □ □

また、そのままだと必ず横領域か縦領域かが入れ替わってしまうので、$+K$ して隣に移動し、領域の種類が変わらないようにする。

• 本問題における、答えが変わらないような左右反転処理
  • $S_x → -S_x-1+K$
  • $T_x → -T_x-1+K$

$y$ 座標を反転させる場合も同様。

左右・上下反転後、$K$ 単位で平行移動して $S_x,S_y$ を領域 $\langle 0,0 \rangle$ 内に持ってくる。
さらに、「（反転や平行移動前の）$S$ の初期位置が縦領域だった」場合はナナメ45度線で反転させる（$x,y$ を入れ替える）。
これでやっと、答えが初期状態と一致するままで、$S_x～T_y$ の条件を揃えることができる。

面倒ではあるが、こういう問題は絶対見落としが発生するので、愚直コードを書いて実験する。

K=4, Sx=0, Sy=0
_10__10__10__10|  9|  9|  9|  9|_10__10__10__10|  9|  9|  9|  9|_10__10__10__10
_10__10__10__10|  9|  9|  9|  9|_10__10__10__10|  9|  9|  9|  9|_10__10__10__10
__9___9___9___9|  9|  9|  9|  9|__9___9___9___9|  9|  9|  9|  9|__9___9___9___9
__8___8___8___8|__9|__9|__9|__9|__8___8___8___8|__9|__9|__9|__9|__8___8___8___8
  7|  7|  7|  7|__8___8___8___8|  7|  7|  7|  7|__8___8___8___8|  7|  8|  9|  9
  7|  7|  7|  7|__8___8___8___8|  7|  7|  7|  7|__8___8___8___8|  7|  8|  9|  9
  7|  7|  7|  7|__7___7___7___7|  7|  7|  7|  7|__7___7___7___7|  7|  8|  9|  9
__7|__7|__7|__7|__6___6___6___6|__7|__7|__7|__7|__6___6___6___6|__7|__8|__9|__9
__6___6___6___6|  5|  5|  5|  5|__6___6___6___6|  5|  6|  7|  7|__8___8___8___8
__6___6___6___6|  5|  5|  5|  5|__6___6___6___6|  5|  6|  7|  7|__8___8___8___8
__5___5___5___5|  5|  5|  5|  5|__5___5___5___5|  5|  6|  7|  7|__8___8___8___8
__4___4___4___4|__5|__5|__5|__5|__4___4___4___4|__5|__6|__7|__7|__8___8___8___8
  3|  3|  3|  3|__4___4___4___4|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
  3|  3|  3|  3|__4___4___4___4|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
  3|  3|  3|  3|__3___3___3___3|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
__3|__3|__3|__3|__2___2___2___2|__3|__4|__5|__5|__6___6___6___6|__7|__8|__9|__9
__2___2___2___2|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__2___2___2___2|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__1___1___1___1|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__s___0___0___0|__1|__2|__3|__3|__4___4___4___4|__5|__6|__7|__7|__8___8___8___8

領域全てが同じコストの箇所と、「2,3,4,4」「5,6,7,7」のような箇所が混在する。

もう一例
K=4, Sx=0, Sy=3
__8___8___8___8|  7|  7|  7|  7|__8___8___8___8|  7|  7|  7|  7|__8___8___8___8
__8___8___8___8|  7|  7|  7|  7|__8___8___8___8|  7|  7|  7|  7|__8___8___8___8
__7___7___7___7|  7|  7|  7|  7|__7___7___7___7|  7|  7|  7|  7|__8___8___8___8
__6___6___6___6|__7|__7|__7|__7|__6___6___6___6|__7|__7|__7|__7|__8___8___8___8
  5|  5|  5|  5|__6___6___6___6|  5|  5|  5|  5|__6___6___6___6|  7|  8|  9|  9
  5|  5|  5|  5|__6___6___6___6|  5|  5|  5|  5|__6___6___6___6|  7|  8|  9|  9
  5|  5|  5|  5|__5___5___5___5|  5|  5|  5|  5|__6___6___6___6|  7|  8|  9|  9
__5|__5|__5|__5|__4___4___4___4|__5|__5|__5|__5|__6___6___6___6|__7|__8|__9|__9
__4___4___4___4|  3|  3|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__4___4___4___4|  3|  3|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__3___3___3___3|  3|  3|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__2___2___2___2|__3|__3|__3|__3|__4___4___4___4|__5|__6|__7|__7|__8___8___8___8
  1|  1|  1|  1|__2___2___2___2|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
  1|  1|  1|  1|__2___2___2___2|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
  1|  1|  1|  1|__2___2___2___2|  3|  4|  5|  5|__6___6___6___6|  7|  8|  9|  9
__1|__1|__1|__1|__2___2___2___2|__3|__4|__5|__5|__6___6___6___6|__7|__8|__9|__9
  s___0___0___0|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__1___1___1___1|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__2___2___2___2|  1|  2|  3|  3|__4___4___4___4|  5|  6|  7|  7|__8___8___8___8
__2___2___2___2|__1|__2|__3|__3|__4___4___4___4|__5|__6|__7|__7|__8___8___8___8

(0,0)開始     (0,3)開始
▲△▲△▲    ▲△▲△△    領域毎にまとめるとこんな感じ
△▲△▲■    △▲△△■    □: 領域が全て同じコスト、始点位置でコスト一緒
▲△▲■□    ▲△△■□    ■: 領域内で違うコスト、始点位置でコスト一緒
△▲■□■    △△■□■    △: 領域が全て同じコスト、始点位置でコストが異なる
▲■□■□    ▲■□■□    ▲: 領域内で違うコスト、始点位置でコストが異なる

市松模様っぽくなりつつも、対角線を境に□と△が切り替わる。また対角線上の△と▲も異なる。（$\langle 0,0 \rangle$ だけ少し違うが、これは例外処理で）

実験を参考に実際の移動方法を考えてみると、 基本はナナメ移動がコスト2で $\langle i+1,j+1 \rangle$ へ2領域分移動できて速い。
だが、ナナメ移動にも2種類ある。

①                       ②                   
_|_____|_|_|_|#####|_    _|_____|_|_|#|_____|_    実験結果を追っていくと、
_| | | |_____|#| | |_    _| | |#|#####| | | |_    終点に近づくまでは、
_| | | |_____|#| | |_    _| | |#|_____| | | |_    (0,0)始点は①、
_|_|_|_|#####|#|_|_|_    _|_|_|#|_____|_|_|_|_    (0,3)始点は②で移動するのが最短っぽい
 |_____|#| | |_____|      |s####| | | |_____| 
 |_____|#| | |_____|      |_____| | | |_____| 
_|s####|#|_|_|_____|_    _|_____|_|_|_|_____|_
 | | | |     | | | |      | | | |     | | | | 

②はいつでも①に移れるが、①はコストを余分に2かけないと②になれない。
行ける範囲も②の方が広い。（新しい横領域に入るとき、①は一番下しか選択肢がないが、②は好きな位置に入れる）

これが、上記の例で始点が $(0,0)$ と $(0,3)$ だった場合で、一部コストと□■の配置が異なった原因となっている。

• ②は
  • $S_y$ が $K-1$（領域の中で一番上）の時に使える。
  • $S_y$ が $K-2$（領域中の上から2番目）の時に、コスト1かけて使える。
  • $S_y$ が $K-3$ 以下の時はコスト2かかるため、①で移動しておいて最後に必要なら移行するのと変わらない。

これは、終点が、領域内でコストが変わる箇所にある場合も当てはまる。$1,2$ 列(行)目に $T_x$ ($T_y$) があると、他よりコストが安くなる。

よって、コストに関わってくる要素は以下となる。

• $(T_x,T_y)$ が属する領域 $\langle i,j \rangle$ における $i$ と $j$ の大小関係と、横領域か縦領域か
• $S_y$ が領域の上から2行目までにあるか
• $T_x$ または $T_y$ が、領域の左から/下から2行目までにあるか

それぞれで場合分けして、上記の実験結果も参考にコストを求められる。

いつぞやのABC でも似た問題が出題されたことがあり、 その時にも同様のコーナーケースがあったが、$K=2$ の時は少し異なる移動方法となる。

_10__10| 10| 10|_11__11| 11| 11|_12__12| 12| 12|_13__13
__9___9|_10|_10|_10__10|_11|_11|_11__11|_12|_12|_12__12
  8|  8|__9___9|  9|  9|_10__10| 10| 10|_11__11| 11| 12
__8|__8|__8___8|__9|__9|__9___9|_10|_10|_10__10|_11|_12
__7___7|  7|  7|__8___8|  8|  8|__9___9|  9| 10|_11__11
__6___6|__7|__7|__7___7|__8|__8|__8___8|__9|_10|_11__11
  5|  5|__6___6|  6|  6|__7___7|  7|  8|__9___9| 10| 11
__5|__5|__5___5|__6|__6|__6___6|__7|__8|__9___9|_10|_11
__4___4|  4|  4|__5___5|  5|  6|__7___7|  8|  9|_10__10
__3___3|__4|__4|__4___4|__5|__6|__7___7|__8|__9|_10__10
  2|  2|__3___3|  3|  4|__5___5|  6|  7|__8___8|  9| 10
__2|__2|__2___2|__3|__4|__5___5|__6|__7|__8___8|__9|_10
__1___1|  1|  2|__3___3|  4|  5|__6___6|  7|  8|__9___9
__s___0|__1|__2|__3___3|__4|__5|__6___6|__7|__8|__9___9

ナナメ移動が速いのは変わらないのだが、$(T_x,T_y)$ と同じ 行 or 列 の領域まで移動したら、そこからは縦/横移動に移る。

$K \ge 3$ の場合はくねくね移動が速い。2つ左（または上）の領域に移動するのにコスト4かかる。

_|_____|_|_|_|_____|_
_| | | |_____| | | |_
_| | | |_____| | | |_
_|_|_|#|#####|_|_|#|#
 |#####| | |#|#####| 
 |_____| | | |_____| 
_|_____|_|_|_|_____|_
 | | | |     | | | | 

一方、$K=2$ の場合は突っ切るとコスト3で移動できる。

_|_|_|___|_|_|_
 |###|#|#|###|#
_|___|_|_|___|_
 | | |   | | |

そのため、対角線から離れた箇所に移動するコストが変わってくる。

Python3