AGC 021

AtCoder Grand Contest 021 - AtCoder

A - Digit Sum 2

たとえば123456の場合、以下の最大値を求めれば良い。

123456 → 21
123449 → 23
123399 → 27
122999 → 32
119999 → 38
 99999 → 45

下 $k$ 桁を'9'とする数値は、以下で求められる。

n - n % (10 ** k) - 1

B: Holes - AtCoder Grand Contest 021 | AtCoder

• 原点を中心として $x,y \le 10^6$ の範囲にいくつかの穴が開いてる
• 原点を中心とした超々々々でかい円上（$r=10\uparrow\uparrow 4$）に、ランダムで玉を落とす
• 玉は最も近い穴に落ちる
• 各穴について、玉が落ちる確率を、精度 $10^{-5}$ で求めよ

ボロノイ分割にとらわれかけたが、問題の条件からもっと単純に考えてよかった。

玉を落とす範囲は無限と考えていいくらい大きいので、ボロノイ分割した時に他の点に囲われる点の確率は0に収束する。 なので、凸包を構成する頂点についてだけ考えればよい。

凸包の各辺に垂直二等分線を引き、各凸包頂点を挟む垂直二等分線のなす角が360°に対して占める割合が、そのまま確率になる。

厳密には原点に対してのズレがあるが、玉を落とす広大な範囲に比べれば無視できる。（以下の図で線分をわずかに平行移動したところで、面積の変化は誤差の範囲である）

ただし、与えられた点が一直線上に並ぶ場合、最も端の2点が0.5ずつの確率になる。

pythonでは、scipy.spatial.ConvexHullが使える。 自力で凸包とかの実装しなくていい分、ライブラリが豊富なpython向きの解法。

$(x_1,y_1),(x_2,y_2)$ の2点の垂直二等分線の角度は、$np.arctan2(x_2-x_1, y_1-y_2)$ で求められる。

解法1の中で適当に「誤差の範囲である」とか言ったが、本当に誤差が条件の範囲内に収まるかは検証が必要。

解法2は、許容される誤差（$10^{-5}$）から考えて十分な精度での全探索を行う。

十分に大きい $r$ と任意の $\theta$ に対し、極座標 $(r, \theta)$ に落ちた玉が入る穴は、「$x_i \cos{\theta} + y_i \sin(\theta)$ が最大となる $i$」となる。（要は、原点からの $\theta$ の向きのベクトル成分が最大の点）

必要な精度を担保するには、角度を許容誤差の2倍（20万）に分割して調べればよい。不安なら少し増やして25万くらいにする。

こういう演算は、pythonならnumpyでさくっとまとめて計算したいところだが、残念ながら全てを一度に持たせるとメモリが制限を超えてしまった。

MLEになるなら適宜分割すればいいじゃない。

もしくは、dtypeをサイズの少ないものに変更する。NumPyのデフォルトは64bit。この場合、減らしすぎるとそれはそれで計算誤差が発生するが、ひとまず32bitにしても大丈夫だった。16bitまで落とすとさすがにWAだった。

• 参考: suwakotaro氏回答

C: Tiling - AtCoder Grand Contest 021 | AtCoder

• 縦x横が $N \times M$ の盤面がある
• 横2縦1のタイルを $A$ 枚、横1縦2のタイルを $B$ 枚敷き詰めたい
• 可能か判定し、可能なら一例を示せ

同種のタイルを2枚ずつ組み合わせて $2 \times 2$ のパーツを敷き詰めるように考えると、AとBを同一に考えられるので考察が楽になる。

<>    ^^
<> or vv

端っこの部分の処理が肝。

$N$ が奇数の場合、あらかじめ一番下に $A$ のタイルを敷き詰めておいても、$B$ が置ける枚数は変わらない。
$M$ が奇数の場合、あらかじめ一番右に $B$ のタイルを敷き詰めて置いても、$A$ が置ける枚数は変わらない。

....^
....v
....^
....v
<><>.

$A,B$ の残りを $A',B'$ 枚とし、残りの盤面に置けるか考える。

$2 \times 2$ のパーツは、$C=A'/2 + B'/2$ 個存在する（/は切り捨ての割り算）。また、端数を $R_A,R_B$ とする（$R_A,R_B=0,1$）

盤面には $D=(N/2)*(M/2)$ のパーツを置ける。

明らかに無理

明らかに無理

可能

残り $2 \times 2$ の盤面に$A,B$を1個ずつは置けないので普通は無理。

だが「$N,M$ が共に奇数」の場合に限り、既に端に敷き詰めたタイルをずらすことで置けるケースがある。要は$3 \times 3$ の盤面に、$A,B$ を各2個置くので、

....^
....v
..<>^
..^.v
<>v<>

この右下の $3 \times 3$ のように、4畳半の畳の敷き方をすればよい。

端数にも $2 \times 2$ のスペースを宛がうことで可能

端数にも $2 \times 2$ のスペースを宛がうことで可能

D - Reversed LCS

• 文字列 $T$ がある
• 逆順にしたものを $T'$ とする
• $T$ を $K$ 文字まで任意に変更してよい
• $T$ と $T'$ の最長共通部分列を最大化し、長さを求めよ

いかにもなDP問題だけど、個人的にDP問題は何をやってるのかわかんなくなってくる。

$T$ をabcabcabcとする。$T'$ はcbacbacbaとなる。

これの最長共通部分列は複数あるが、例えばbcbcb, bcbabなどになる。bcbabは回文ではないが、同じ5文字でbcbcbという回文部分列が存在する。これは必ず存在すると言える。

何故か。

回文でない共通部分列bcbabを考える。$T$ と $T'$ で、それぞれが出現する位置は以下になる。

     abcabcabc
T →  12 3 45
      5 432 1  ← T'

この時、どこかですれ違うポイントがある。無い場合でも、端っこですれ違うと見做す。この場合、3番目のbですれ違う。

すると、$T$ の部分列の1～3番目を取ってきて、$T'$ の部分列の1～2番目を取ってきて逆向けにくっつけたものも、$T,T'$の共通部分列として存在する。逆に $T'$ の3～5番目の逆と、$T$ の4～5番目をくっつけたものも同じ。

これらは回文であり、いずれかは少なくとも元の部分文字列の長さ以上である。

     abcabcabc
T →  12 3
          2 1 ← T'  => bc bc b
T →       45
      5 43    ← T'  => ba ba b

なので、回文でない共通部分列があったとしても、その長さ以上の、回文である共通部分列が必ず存在する。

問題の答えとしては長さを求めればよいので、回文部分列のみ考えてよいということになる。

単純な最長共通部分列問題は、以下のサイトなどで解説されている。

• 最長増加部分列・最長共通部分列
• 最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー

しかし今回は、以下の条件の下で行うので、上記の方法では上手くいかない。

• $K$ 文字まで任意に変更してよい
  • あくまで元の文字列は1つなので、一方の変更がもう一方に影響してしまう
• 探すのは回文限定で良い

この場合、$dp[l][r][p]$ として、$T$ の $l$ ～ $r$ 文字目を切り出した文字列で、$p$ 回まで変更を加えてできる最長共通部分列の長さを求めるとよいらしい。

正直、何故この場合はこういった解法がいいのか、というのが全然理解できてないが、やってみたらなるほど上手くいく。

計算量は、$l,r$ が $|T|$ に依存し、$p$ が $K$ に依存するので、$O(|T|^2K)$

$K$ が $|T|$ の半分以上の場合、$T$ の後半を前半の逆順にまるっと変更してしまうことで $T$ 自体を回文＝最長共通部分列にできるので、答えは $|T|$ となる。

$T_i$ を、$T$ の $i$ 番目の文字とすると、

$dp[l][r][p]$ は、$dp[l+1][r-1][p]$ に $2$ を足したものとなる。

   l       r
   ↓      ↓
...○xx..xx○...
     ~~~~~~
  dp[l+1][r-1]  

$dp[l][r][p]$ は、以下のうちの最大のものとなる。

• $dp[l+1][r][p]$
• $dp[l][r-1][p]$
• $dp[l+1][r-1][p-1]+2$（$p \ge 1$）

   l       r
   ↓      ↓
...○xx..xx△...
     ~~~~~~~~   dp[l+1][r][p]
   ~~~~~~~~     dp[l][r-1][p]
     ~~~~~~     dp[l+1][r-1][p-1]+2 (l,r,どちらか1文字変更)

なので、dpを行う中で $l,r$ の値を埋める際には、これらの情報が既に求められている必要がある。

それには、以下のループを回すとよい。$r$ をインクリメントしつつ、$l$ を $r$ から1までデクリメントする。

for r in 1..n:
    for l in r..1:
        // Fill dp[l][r]

$O(|T|^2K)=300^2 \times 150=1.35 \times 10^7$ となり、配列参照の多いDPで、pythonではあまり余裕が無い。

DPで値の入り得ない部分に無駄な配列を作らない、ループ中で繰り返し参照される配列はローカル変数に溜める、などで高速化を図る。けどすっごい読みにくくなるので、あまりやりたくない。

E - Ball Eat Chameleons

• $N$ 匹のカメレオン
• 色は青か赤。最初はみんな青
• $K$ 個の青か赤のボールを順番に1個ずつ投げ入れる
  • ボールがカメレオンのどれかに食べられてから、次のボールを投げ入れる
• ボールを食べたカメレオンは、以下の基準で変色する
  • 青いカメレオンは、今まで食べた赤いボールの数が青より真に大きくなった時、赤に変色
  • 赤いカメレオンは、今まで食べた青いボールの数が赤より真に大きくなった時、青に変色
  • それ以外では変色しない
• 全てのボールを投げ終えた後、全てのカメレオンが赤になっていた
• ボールの投げ入れる順番としてあり得るものは何通りか、$\mod{998244353}$ で答えよ

経路数え上げ問題。

詳細は解説や解説放送参照

全てのカメレオンは最初青なので、1回は赤いボールを食べないといけないが、$n>k$ の場合足りない。よって0

カメレオンが1匹の場合は、$2^{k-1}$ で求められる。変化の法則には対称性があるので、全てのボールを1匹が食べた時、最終的に赤/青になる組み合わせは等しく投げ入れ方の総数 $2^k$ の半分になる。

${}_n C_r \equiv \frac{n!}{r!(n-r)!} \mod{m}$ を繰り返し計算する。これを高速に求めるために、事前計算として、以下を求めておく。

• $k! \mod{m}$（共通の分子になる）
• $j!^{-1} \mod{m} \ \ (1 \le j \le k)$（分母になる）

すると、${}_n C_r \equiv n! \times r!^{-1} \times (n-r)!^{-1} \mod m$ で求められる。

これらを高速に用意したい。

$k! \mod{m}$ は、純粋に1からかけ算を繰り返して求めていくしか無い？ 一応、$k > m/2$ の時はわずかに高速化できる手法（Wilson's theorem）はあるが、今回の場合 $k$ はそこまで大きくはならないので使えない。

$\mod{m}$ における $a$ の逆数は、$a$ と $m$ が互いに素ならフェルマーの小定理より $a^{m-2} \mod{m}$ で計算できる。しかし、$1!$～$k!$ の全てでこの計算をしていると間に合わない（$k \le 5\times 10^5$）。

まず $k!^{-1} \mod{m}$ を計算し、そこに $k$ をかけると $(k-1)!^{-1}$、さらに $k-1$ をかけると $(k-2)!^{-1}$ ……が求まることを利用すると、より効率的に全ての逆数を求められる。

• Share a method to find the multiplicative inverse of 1~n mod p - Codeforces