AtCoder Regular Contest 195 (Div. 2) B,C,D,E問題メモ

AtCoder Regular Contest 195 (Div. 2)

B - Uniform Sum

• 数列 $A=(A_1,\dots,A_N)$, $B=(B_1,\dots,B_N)$ があります。各要素は $-1$ または非負整数です。
• これらに対して、以下の $3$ 種類の操作を、任意の順番で任意の回数だけ行うことができます。
  • $A_i = -1$ を満たす $i$ を選び、$A_i$ を任意の非負整数に置き換える。
  • $B_i = -1$ を満たす $i$ を選び、$B_i$ を任意の非負整数に置き換える。
  • 数列 $A$ の要素を任意の順番に並び替える。

• 操作の結果、$A$, $B$ の全ての要素が非負であり、なおかつ $A_1 + B_1 = A_2 + B_2 = \dots = A_N + B_N$ となるようにできるかを判定してください。

• $2 \leq N \leq 2000$
• $-1 \leq A_i \leq 10^9$
• $-1 \leq B_i \leq 10^9$
• 入力される値は全て整数

まず $-1$ 含みのまま $(A_i,B_i)$ のペアを決めてから、$-1$ を置き換える、という手順と考えてもよい。

初期状態で $-1$ が $A,B$ あわせて $k$ 個あったとする。
$k \ge N$ ならば可能。ペアとする $(A_i,B_i)$ の少なくとも一方を必ず $-1$ にでき、和を自由に揃えられるので。

「$-1$ でない値」のことを、★と表記する。
$k \lt N$ の場合、少なくとも $N-k$ 個のペアは、和を操作できない $(★,★)$ とならざるを得ない。

ここで、ペアの和とする目標値 $T$ を仮に決める。以下をともに満たす $T$ が存在すれば良い。

• $A,B$ にはじめから存在する非負整数の最大値を $m$ として、$T \ge m$
  • $m$ を含むペアの和は、$m$ 以下にはできないので
• $(★,★)$ のペアで、和が $T$ となるものを、重複せず $N-k$ 個作れる

重複せず、というのが少し注意を要する。同じ値はまとめて考慮しなければならない。
「$C_A(x):=A$ の中で $x$ が登場する回数」（$C_B(x)$ も同様に定義）とすると、 以下の畳み込みによって「$D_i :=$ 和が $i$ となる $(★,★)$ の個数」を数えられる。

• $\displaystyle D_i = \sum_{x+y=i} \min(C_A(x),C_B(y))$

$N \le 2000$ なので、愚直に $O(N^2)$ かけて $x,y$ のペアを回して間に合う。

$i \ge m$ かつ $D_i \ge N-k$ なる $i$ があれば可能と判定できる。

Python3

C - Hamiltonian Pieces

• 縦 $10^9$ マス、横 $10^9$ マスの盤と、$R$ 個の赤い駒、$B$ 個の青い駒があります。ただし、$2\leq R+B$ が成り立ちます。盤の上から $r$ 行目、左から $c$ 列目のマスを、マス $(r,c)$ と呼びます。赤い駒は $1$ 手で縦横に $1$ マス、青い駒は $1$ 手で斜めに $1$ マス移動することができます。より正確には、マス $(r,c)$ にある赤い駒はマス $(r+1,c),(r,c+1),(r-1,c),(r,c-1)$ に、マス $(r,c)$ にある青い駒はマス $(r+1,c+1),(r+1,c-1),(r-1,c+1),(r-1,c-1)$ に、移動先のマスが存在すればそれぞれ $1$ 手で移動することができます。
• この盤に、$(R+B)$ 個全ての駒を任意の順番で $1$ つずつ置きます。ただし、以下の条件を満たすように置かなければいけません。
  • $1$ つのマスに置かれる駒は高々 $1$ 個である。
  • 各 $i$ $(1 \leq i \leq R+B-1)$ について、$i$ 番目に置かれる駒は $(i+1)$ 番目に置かれる駒のあるマスに $1$ 手で移動することができる。
  • $(R+B)$ 番目に置かれる駒は $1$ 番目に置かれる駒のあるマスに $1$ 手で移動することができる。

• 条件を満たす $(R+B)$ 個の駒の置き方が存在するかを判定し、存在するならばその一例を示してください。
• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1\leq T\leq 10^5$
• $0 \leq R, B$
• $2 \leq R + B \leq 2 \times 10^5$
• すべてのテストケースにわたる $R+B$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

手先での構築方法を見つけるのは、適当に試行錯誤していればそこまで難しくない。
ただ、最初に見つけた構築方法が場合分けが多いもので、プログラムに落とし込むのが面倒だった。
公式Editorialにあるような方法の方が、実装が楽だったね。

グリッド問題の典型、$i+j$ の偶奇を考えると、赤いコマ $R$ は偶数個でないと不可能。
また、$R=0$ の場合、45度傾けると同じ事が言えるので、$B$ は偶数でないと不可能。
それ以外は可能。以下、可能とする。

いずれかが $0$ の時は、普通に長方形に配置すればいい。

両方とも正の時は、以下のようにすれば良い。

B=1
❶②③④⑤
  ⑨⑧⑦⑥

B=1より大きい奇数
①❷⓰❹⓮⑥⑦⑧⑨    ○: 赤いコマ（上下移動）
  ⓱❸⓯❺⓭⑫⑪⑩    ●: 青いコマ（斜め移動）

B=偶数
①❸⓱❺⓯⑦⑧⑨⑩
❷⓲❹⓰❻⓮⑬⑫⑪

$B$ を $4$ で割ったあまりが $1,2$ の場合は上のように、右側の赤いコマの通過順が1行目→2行目となるが、 $0,3$ の場合は2行目→1行目の順になるので、計4通りの場合を考慮する必要がある。

Python3

D - Swap and Erase

• 数列 $A = (A_1,\ldots,A_N)$ があります。これに対して、以下の $2$ 種類の操作を、任意の順番で任意の回数だけ行うことができます。
  • 操作直前の $A$ の長さを $K$ とする。$1\leq i\leq K-1$ を満たす整数 $i$ を選び、$A$ の第 $i$ 項と第 $(i+1)$ 項を入れ替える。
  • 操作直前の $A$ の長さを $K$ とする。$1\leq i\leq K$ かつ $A$ の第 $1$ 項から第 $i$ 項の値が全て等しいような整数 $i$ を選び、$A$ の第 $1$ 項から第 $i$ 項までを全て削除する。

• $A$ を空の数列にするために必要な合計操作回数の最小値を求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて解いてください。

• $1\leq T\leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• すべてのテストケースにわたる $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

先に必要な入れ替え操作を全て完了させてから、削除していく、という操作手順に限定しても問題ない。

入れ替え操作しても、得になるケースが限られる。

1 1 1 2 1 2 2 2        もともと削除に4回かかるところ、
       v               1回のswap操作で、消す回数を2にでき、1回分お得
1 1 1 1 2 2 2 2

1 1 2 1 3 2 4 3 4 4    もともと削除に8回かかるところ、
     v   v   v         3回のswap操作で、消す回数を4にでき、1回分お得
1 1 1 2 2 3 3 4 4 4

swapで入れ替える2つが両方とも「最終的に、別の同じ数字とくっついて、まとめて消せる＝消す回数が1減る」というような状況にならない限り、入れ替えるメリットはない。

仮に、「同じ数字が、2回以上、swap対象に選ばれることはない」ことが言えれば嬉しい。

何故かというと、各swapが互いに干渉せず、順番が関係なくなるので、先頭から順にDPが可能になるからである。
（swapの順番が関係あると、後ろ→前という操作順を考慮する必要があり、DPできない）

そして実際にこれは、証明できる。（めっちゃややこしい）

• 公式Editorial

よって、

• $\mathrm{DP}[i,j]:=A_1～A_i$ を全て消すのに必要な（swap回数 + 消す回数）の最小値で、$j=0$ のとき直前（$i-1$ と $i$）をswapしていないもの、$j=1$ のときswapしたもの

というDPで、答えを求められる。

Python3

E - Random Tree Distance

• 整数列 $A = (A_2,A_3,\ldots,A_N)$ があります。また、各 $i$ $(2 \leq i \leq N)$ について $1 \leq P_i \leq i-1$ を満たす整数列 $P=(P_2, P_3, \ldots ,P_N)$ に対して、頂点 $1$ を根とする $N$ 頂点の重み付き木 $T(P)$ を以下のように定義します。
  • 各 $i$ $(2 \leq i \leq N)$ について、$i$ の親が $P_i$ であり、$i$ と $P_i$ を結ぶ辺の重みが $A_i$ であるような根付き木

• $Q$ 個のクエリが与えられるので、順に処理してください。$i$ 番目のクエリは以下の通りです。
  • $1$ 以上 $N$ 以下の整数 $u_i,v_i$ が与えられる。$P$ としてあり得る $(N-1)!$ 通りの数列全てについての木 $T(P)$ での頂点 $u_i$ と頂点 $v_i$ の距離の総和を $998244353$ で割った余りを出力する。ただし、頂点 $u_i$ と頂点 $v_i$ の距離とは、この $2$ 頂点を結ぶ唯一の（同じ頂点を $2$ 回以上通らない）パスに含まれる辺の重みの総和である。

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i \lt v_i \leq N$
• 入力される値は全て整数

「全ての状態における総和」は、「確率」「期待値」をまず考えて、そこに全状態数 $(N-1)!$ をかけると考えやすくなる場合がある。
今回も、特に関係の無い頂点の状態をいちいち倍加するのが面倒なので、確率で考えると少しスムーズになる。

主客転倒して、クエリ $(u,v)$（$u \lt v$）において「$A_i$ が加算される確率 $P(i)$」を考える。

$u-v$ 間を結ぶパスには使われ得ない。$P(i)=0$

必ず使われる。$P(v)=1$ である。

$i$ は（$u$ の祖先にはなり得ないので）$v$ の祖先になった時のみ、$A_i$ が寄与する。

これは、$P(i)=\dfrac{1}{i}$ である。

「$v$ から親を遡っていく中で、はじめて $i$ 以下の頂点になった時、それが $i$ である確率は？」と考えると、理解しやすい。

$u$ が $v$ の祖先である場合のみ、寄与しない。

$u$ が $v$ の祖先である確率は $\dfrac{1}{u}$ のため、それ以外の $P(u)=\dfrac{u-1}{u}$ となる。

ここが一番ややこしい。かつ、実験エスパーなのであんまり綺麗な求め方ではない。

$A_i$ がコストに含まれるには、$\mathrm{LCA}(u,v) \lt i$ で、かつ $i$ が $u,v$ のいずれかの祖先になっていればよい。
いずれか、というのが厄介なので、まずは区別せずに以下の式を考える。

• $f(x,u):=$ 頂点 $u$ の祖先に $x$ がある確率

$f$ 自体は既に $u \lt i \lt v$ の項で説明したように $\dfrac{1}{x}$ になるのだが、 ここで $x$ および $x～u$ の間で経由した頂点を「実は $u$ でなく $v$ の祖先だった」と捉えなおして分配してもよい。
それぞれにつき2通り、計 $2^{止まった頂点数}$ の分配の仕方がある。

x=2  u=6

■uからxに至るまでに経由する頂点の一例
    ...  --A2--②  --A3--③  --A5--⑤  --A6--⑥
                 ↓

■分配の仕方の一例
uの祖先  --A2--②------------------------A6--ⓤ
vの祖先  ------------A3--③----A5--⑤------------A?--...--ⓥ

よって、以下を考えると

• $f'(x,u,c):=$ 頂点 $u$ の $c$ 個上の祖先に $x$ がある確率
• $\displaystyle g(x,u):= \sum_{c}f'(x,u,c) \times 2^c$

クエリ $(u,v)$ に $A_i$ が寄与する確率は、以下になる。

• $Q(u,v,i) = g(i,u) \times (i-1) \times f(u,v)$

軽い説明

$O(N^2)$ などかけて小さいケースで愚直を試すと、これはなんと、$i$ のみに依存するっぽいことがわかる。

• $Q(u,v,i)=\dfrac{i-1}{i(i+1)/2}=P(i)$（クエリに依らない）

よって、これを各 $A_i$ とかけあわせて前からの累積和を取っておくと、 各クエリに対して $\displaystyle \sum_{i=2}^{u-1}P(i)$ が $O(1)$ で求められる。

以上で全てであり、各場合の(確率 $\times A_i$) を事前計算しておくと、クエリに $O(1)$ または $O(\log{MOD})$ で求められる。

Python3