AtCoder Beginner Contest 189 C,D,E,F問題メモ

AtCoder Beginner Contest 189

C - Mandarin Orange

• $N$ 個の皿があり、$i$ 番目の皿には $a_i$ 個のオレンジがのっている
• 以下の方法でオレンジを食べることができる
  • $l \le r$ を満たす $(l,r)$ を選ぶ
  • 皿 $l～r$ について、それぞれの皿からオレンジを同じ数だけ食べる
    • 当然、各皿にのっている以上のオレンジを食べることはできない
• 食べることのできるオレンジの最大数を求めよ
• $1 \le N \le 10^4$

要は、ヒストグラムみたいな表から最大の長方形の面積を見つける問題となる。

• DPL_3_C < Library < Courses | Aizu Online Judge

この問題では制約的に $l,r$ の組を全て調べる $O(N^2)$ 解法が通る。

また、std::set のように以下の両方を満たせるデータ構造を使うと、

• ソート順を保ったまま値を入れられる
• lower_bound, upper_bound（ある値より小さい最大の値、大きい最小の値）を取得できる

$a_i$ が小さい方から順に $i$ を値として入れていって、自身を入れた時点のlower, upperを取得すれば、幅（upper - lower - 1）、高さ $a_i$ の長方形を作ることができる。
この場合、計算量は $O(N \log{N})$ となる。

また、スタックを用いて管理すると $O(N)$ でも計算できる。

• ALGORITHM NOTE ヒストグラム中の最大の長方形の面積

Python3

D - Logical Expression

• $N$ 個の文字列 $S_1～S_N$ が与えられ、各文字列は 'AND' または 'OR' である
• $N+1$ 個のブール値変数 $x_0～x_N$ をこれでつなぎ、前から計算することを考える
  • 例: $x_0 \ AND \ x_1 \ OR \ x_2 \ AND \ ... \ OR \ x_N$
• $x_0～x_N$ の決め方は $2^{N+1}$ 通りあるが、この内全体がTrueになるものの個数を求めよ
• $1 \le N \le 60$

公式解説では後ろから再帰的に求めていっている。

前からでもDPできる。

• $DP[i][j:0/1] = 1～i$ 番目の要素を使って、全体が $j=0$:Falseになる, $1$:Trueになるパターンの個数

最初は $x_0$ だけがあり、True,Falseそれぞれ1通りずつ。 $DP[0] = [1,1]$

直前までの結果 $DP[i-1]$ に $S_i, x_i$ を反映して更新するとき、

Si = AND なら
  直前までの結果がFalseなら
    xi がFalseなら → False
    xi がTrue なら → False
  直前までの結果がTrueなら
    xi がFalseなら → False
    xi がTrue なら → True
    
  →ここから、
  DP[i][0] = 2*DP[i-1][0] + DP[i-1][1]
  DP[i][1] = DP[i-1][1]
    
Si = OR なら
  直前までの結果がFalseなら
    xi がFalseなら → False
    xi がTrue なら → True
  直前までの結果がTrueなら
    xi がFalseなら → True
    xi がTrue なら → True

  →ここから、
  DP[i][0] = DP[i-1][0]
  DP[i][1] = DP[i-1][0] + 2*DP[i-1][1]

という遷移を実装すればよい。

Python3

E - Rotate and Flip

• $N$ 個の二次元平面上に駒があり、$i$ 番目は $(x_i,y_i)$
• この駒に対して行う操作が $M$ 個、与えられる
• 操作
  • '1': 全ての駒を原点を中心に時計回りに90度回転させた位置に移動する
  • '2': 全ての駒を原点を中心に反時計回りに90度回転させた位置に移動する
  • '3 p': 全ての駒を、直線 $x=p$ について対称な位置に移動する
  • '4 p': 全ての駒を、直線 $y=p$ について対称な位置に移動する
• 続いてクエリが $Q$ 個与えられる
  • それぞれ、$A_i$ 番目の操作を行った直後に駒 $B_i$ がある座標を出力せよ
• $1 \le N,M,Q \le 2 \times 10^5$

操作は、1,2が回転移動、3,4が平行移動＋対称移動の操作となっている。

これらの操作はアフィン変換といって、$(x,y,1)$ というベクトルに、操作ごとに所定の行列をかけることで、操作後の座標を得られるような性質を持つ。

• アフィン変換の意味と４つの基本要素 - 具体例で学ぶ数学

つまり、複数回操作したら以下のように表すことができ、

$$\left( \begin{array}{rrr} p_3 & q_3 & c_3 \\ r_3 & s_3 & d_3 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{rrr} p_2 & q_2 & c_2 \\ r_2 & s_2 & d_2 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{rrr} p_1 & q_1 & c_1 \\ r_1 & s_1 & d_1 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{rrr} x \\ y \\ 1 \end{array} \right)$$

行列のかけ算はどこから計算してもよいので、操作を表す行列の方を1から順に先に計算して保存しておけば、 後から $(x_i,y_i,1)$ を放り込んでやれば複数回の操作をまとめて行ったのと同じことになる。

実装では、行列をスムーズに扱えるかちょっと自信がなかったので、単純化して実装した。

今回の操作においては、上記の行列で $p,q,r,s$ の4つのうち、$(p,s)$ か $(q,r)$ のいずれかは両方0になっている。
（90度以外の回転などをすると、両方に非0の値が入ってくる）

これを利用して、「o: $(p,s),(q,r)$ のどちらが0かフラグ」を含む5つの値を管理することで、行列と同様の情報を持たせた。

Python3

F - Sugoroku2

• $0～N$ の $N+1$ 個のマスと、$1～M$ の目が等確率で出るルーレットですごろくをする
  • マス0がスタート、$N$ がゴール
  • マス $N$ へはぴったりで無くとも、越したらゴールとする
• $K$ 個のマス $A_1,A_2,...,A_K$ は「スタートに戻る」マスで、強制的にマス0に戻される
• ゴールまでに回すルーレットの回数期待値を求めよ
• 絶対誤差または相対誤差が $10^{-3}$ 以内なら正解とする
• $1 \le N,M \le 10^5$
• $0 \le K \le 10$

まぁ、ぱっと見で $DP[i] = i$ マス目までにかかる回数期待値、みたいなのを行いそうではあるが、一筋縄ではいかない。

これは循環する要素のあるDPとなっている。

• $DP[i]$ を求めるのに $DP[i-1]$ などが必要
• $DP[i-1]$ を求めるのに $DP[i-2]$ などが必要
• ……
• $DP[0]$ を求めるのに $DP[i]$ などが必要

このようなDPは埋め方に工夫が必要になる。

• ちょうどいい値を $x$ とおいて、$x$ を使った式の形でDPを求めていき、何らかの値を $x$ を使った2通りの表現で表すことができたら方程式を解いて $x$ が求められる
• 誤差が収束するまで繰り返し計算する

今回の場合、

• 誤差が比較的ゆるゆるでもOK
• ループごとに指数的に確率は低くなっていき、逆にルーレットを回す回数は線形でしか増加しないので、収束することが明らか

なので、確率が十分に低くなり、期待値に与える影響が小さくなるまで、繰り返し計算する、という方針をとる。

ただ、結果的に前者と似たような実装が必要になったので、前者の方がスマートと思う。
（解法2に、前者の方法も書いた）

さて、ではどれくらい繰り返せばよいかというと、スタートに戻る確率が高いほど、期待値に与える影響が小さくなるスピードが遅くなる。

ゴールに行ける確率が（0では無い場合で）低いのは、例えば $M=2$ で、10個のスタートに戻るマスが2つおきにある場合など。約99.99987%でスタートに戻る。

これは例えば $10^5$ 回スタートに戻ってもまだゴールできない確率は88%近くあり、期待値に与える影響はなかなか小さくならない。
1回スタートに戻るごとに $O(N)$ かけて計算していては間に合わない。
高速化の必要がある。

$K$ の制約が小さいのは、このように意地悪なケースで指数的に回数が増えてしまい、精度を保つのが難しくなるからと思われる。

ここで、期待値は一次式の形で表現できることを利用する。
何回スタートに戻されたか、という点で分けて考察する。

$t$ 回スタートに戻されてマス0にいる時の、回数期待値を $E_t$、確率を $P_t$ とする。

また、$t$ ごとに、以下の2つのDPを考える。

• $DP_E[i]=$ 現在考慮中の $t$ において、マス $i$ に止まる回数期待値
• $DP_P[i]=$ 現在考慮中の $t$ において、マス $i$ に止まる確率

$DP_E[0]=E_t, DP_P[0]=P_t$ であり、また、DPの遷移は以下のようになる。

• $DP_E[i]$
  • マス $j$ からルーレットを回して $i$ に止まる回数期待値は、$f(j)=\dfrac{DP_E[j] + DP_P[j]}{M}$（※到達可能な場合のみ）
    • ここで $DP_P$ を足すのは、「確率 $DP_P[j]$ で止まれるマスから、あと1回ルーレットを回す」ことを表現している
  • $DP_E[i]=f(i-1)+f(i-2)+...+f(i-M)$
  • ただし、スタートに戻るマスの場合は0
• $DP_P[i]$
  • マス $j$ からルーレットを回して $i$ に止まる確率は、$g(j)=\dfrac{DP_P[j]}{M}$（※到達可能な場合のみ）
  • $DP_E[i]=g(i-1)+g(i-2)+...+g(i-M)$
  • ただし、スタートに戻るマスの場合は0

従って、遷移を見ると「$DP_E$ の各要素、$DP_P$ の各要素」「今回の $t$ でスタートに戻される場合の回数期待値 $E_{t+1}$、確率 $P_{t+1}$」「今回の $t$ でゴールする場合の回数期待値、確率」は、全て $E_t,P_t$ の一次式の形で表せることがわかる。

• $DP_E$ の各要素: $aE_t+bP_t$
• $DP_P$ の各要素: $cP_t$
• $E_{t+1}$: $dE_t+eP_t$
• $P_{t+1}$: $fP_t$
• ゴールする回数期待値: $gE_t+hP_t$
• ゴールする確率: $iP_t$

ただしゴールはオーバーしてもいいので、「ちょうどマス $i$ に止まる」場合と遷移が微妙に異なる点に注意。

この $a～i$ の係数はスタートに何回戻されても（DPの遷移が同じで）不変なので、$O(N)$ で1回だけ求めてやれば、後は $t$ ごとに $O(1)$ で次々と計算していける。

これで、十分に期待値への影響が小さくなるまで計算を回すことが可能になった。

上記では $DP_E,DP_P$ で説明したが、実際には各マスへの回数期待値、確率を $aE_t+bP_t, cP_t$ と表現したときの $a,b,c$ をそれぞれDPで計算する。

また、各遷移において、自身の $M$ マス手前までの連続区間の和が必要になるので、最初から累積和で保持しておくとよい。

Python3

これは難しかった。

1次式の係数をDPするのは同じだけど、繰り返し収束するまで計算しなくてもいいし、より正確な値が出る解法。

先頭からではなく、末尾からおこなう。

• $DP[i]=$ マス $i$ からのゴールまでの残り回数期待値

これを、$DP[0]=x$ として、$ax+b$ の形で計算する。$DP[N]=0x+0$ となる。

遷移を考える。

$i$ がスタートに戻るマスだった場合、最初からもう一回遊べるドンなので、残り回数期待値は $x$ そのものになる。つまり、$a=1,b=0$ となる。

それ以外の場合、$i$ から $j$ に行くときの残り回数は $DP[j]+1$。これが $j=1～M$ についてそれぞれ確率 $\dfrac{1}{M}$ で発生するので、

• $DP[i]=\dfrac{DP[i+1]+DP[i+2]+...+DP[i+M]}{M}+1$

係数 $a,b$ についてばらすと、

• $DP_a[i]=\dfrac{DP_a[i+1]+DP_a[i+2]+...+DP_a[i+M]}{M}$
• $DP_b[i]=\dfrac{DP_b[i+1]+DP_b[i+2]+...+DP_b[i+M]}{M}+1$

となる。累積和で管理しておけばよい。添字が $N$ をオーバーする分については、$DP[j]=0x+0$ なので累積和には影響しない。

これをもとにDPを計算していくと、$DP[0]$ が2通りで表せるようになる（$x=DP_a[0]x+DP_b[0]$）。これをとくと答え。

ただし、必ずスタートに戻されてしまう場合、$a=1$ となる。その場合は-1を出力する。

Python3

先頭からだと、ルーレット1回分の加算値が確率になるので、期待値と確率を両方持たないといけないけど、末尾からだと1でよいので、こっちの方が計算楽だった。

先頭からやったって $DP[0]$ を2通りの方法で表せるんじゃ無いの、と思うんだけど、なんか答えが合わなくなる。後ろからだとできるのに、違いは何なんだろうか。

解法1のように前からDPを行うが、 1次式で行う必要は無く、「1周目で」到達する場合の回数期待値と確率を直接求めればよい。

幾何分布の公式から「確率 $p$ で成功してスコア $X$、$1-p$ で失敗してスコア $Y$ を得る試行を、はじめて成功させるまでに得るスコア期待値」を算出できる。

DPの遷移は以下のようになる。

• $DP_E[0]=0$
• $DP_P[0]=1$
• $DP_E[i]=f(i-1)+f(i-2)+...+f(i-M)$、ただし $f(j)=\dfrac{DP_E[j]+DP_P[j]}{M}$
• $DP_P[i]=g(i-1)+g(i-2)+...+g(i-M)$、ただし $g(j)=\dfrac{DP_P[j]}{M}$
• スタートに戻るマスはともに0

最終マスのみ遷移が変わるのでそこに留意して、以下が求められる。

• $x$: 1周でゴールする回数期待値
• $p$: 1周でゴールする確率
• $y$: 1周でスタートに戻る回数期待値（＝スタートに戻るマスの $DP_E$ に入るはずだった値の合計）

これで求められるのは、確率を反映して平均された期待値 （たとえば確率 $1/2$ で $3$、$1/4$ で $5$ になる変数があったら、$\dfrac{3}{2}+\dfrac{5}{4}=\dfrac{11}{4}$）だが、 これを確率で割ることで確率反映前の重み付き平均回数 $\dfrac{11}{3}$ にする。

• $X=x/p$
• $Y=y/(1-p)$

その上で、各周目でゴールする回数期待値を考えると、

• 1周: $pX$
• 2周: $p(1-p)(X+Y)$
• 3周: $p(1-p)^2(X+2Y)$
• …
• t+1周: $p(1-p)^t(X+tY)$

この無限和をとればよいので、$|1-p|<1$ の条件下で

• $\displaystyle \sum_{t=0}^{\infty}p(1-p)^t(X+tY)=\frac{pX+(1-p)Y}{p}=\frac{x+y}{p}$

という、単純な数式となる。

• 導出: Geometric distribution - Wikipedia

これを計算してやれば、答えとなる。

この問題では循環が常に「スタートに戻る」で、成功するときも失敗するときも常に同じ状態から開始しているので簡単な公式に落ち着いたが、 これが「マス $x$ に飛ぶ」などだったら、やはり末尾からDPの方が汎用性はあるか。

二分探索により、$DP[0]$ を仮定することでも、求めることができる。

$P$ と仮定して末尾から埋めていって、最終的に求めた結果 $DP[0] \lt P$ ならば、最初の見積もりが大きすぎたので、次は小さい数で試す。
計算量は答えとしてあり得る上限を $C$ として、$O(N \log{C})$ となり、一次式DPなどと比較するとlogが付く分だけ若干重い。

二分探索が可能であるためには、「本当の答えより小さい $P$ を指定した場合は必ず $DP[0] \gt P$ となり、大きい $P$ を指定した場合は必ず $DP[0] \lt P$ となる」必要がある。

遷移を見ると、DPの各値は足し算と割られる数としての割り算しかされないので、真の値を $T$ として $P=T+k$ で $DP[0]$ を求めたとき、差分の $k$ の符号は変わらないことがいえる。

別の表現をすると、解法2のように1次式DPで $DP[0]=aP+b$ と表せる際、（ゴールできる可能性があれば）$a \lt 1$ なので、

• $T=aT+b$
• $P-(aP+b)=(T+k)-(a(T+k)+b) = (1-a)k$

となり、$k$ の符号と、$P-DP[0]$ の符号は一致することがわかる。

$P$ と $DP[0]$ の大小関係で次の範囲を決めるので、もし、中盤で偶然、演算誤差により次の探索範囲を誤ってしまえば、答えが離れたものとなってしまう。

誤差のなるべく出ない方法で評価をする必要がある。

例えばこの問題の例では、$DP$ に累積和の値を直接持たせると、最終的な値が最大で $10^{17}$ くらいになるため誤差が大きくなり、いくつかのテストケースでWAとなった。
尺取法のように、幅 $M$ の $DP$ の合計値を別で管理して、スライドさせた時の差分を更新していく方法なら、値は $10^{11}$ くらいとなるので大丈夫だった。

どうしても誤差をなくすのが難しい場合、$|P - DP[0]|$ がある程度小さければ次は $[L,P),[P,R)$ 両方の範囲を試す、などの方法が考えられる。

二分探索なら、1次式DPでは解けないような問題でも解くことができる。

例えば「スタートに戻るマスを踏むと5回休みとなるが、いつでも自主的にスタートに戻ることもできて、その場合はペナルティなしで再スタートできる」みたいなルールとする。

スタートに戻るマスを踏む確率が高そうなマスに止まってしまったら自主的に戻るのが正しい場合もあり得そうだが、 結局どちらがよいかの比較を行う際、1次式DPだと「$3x+5$ と $4x+4$ はどちらが得？」みたいな比較ができない。

二分探索なら、具体的な数値が入っているので比較でき、最適な戦略をとった場合の期待値を求めることができる。