要は、ヒストグラムみたいな表から最大の長方形の面積を見つける問題となる。
この問題では制約的に l,r の組を全て調べる O(N2) 解法が通る。
また、std::set のように以下の両方を満たせるデータ構造を使うと、
ai が小さい方から順に i を値として入れていって、自身を入れた時点のlower, upperを取得すれば、幅(upper - lower - 1)、高さ ai の長方形を作ることができる。
この場合、計算量は O(NlogN) となる。
また、スタックを用いて管理すると O(N) でも計算できる。
公式解説では後ろから再帰的に求めていっている。
前からでもDPできる。
最初は x0 だけがあり、True,Falseそれぞれ1通りずつ。 DP[0]=[1,1]
直前までの結果 DP[i−1] に Si,xi を反映して更新するとき、
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]
という遷移を実装すればよい。
'1
': 全ての駒を原点を中心に時計回りに90度回転させた位置に移動する'2
': 全ての駒を原点を中心に反時計回りに90度回転させた位置に移動する'3 p
': 全ての駒を、直線 x=p について対称な位置に移動する'4 p
': 全ての駒を、直線 y=p について対称な位置に移動する操作は、1,2が回転移動、3,4が平行移動+対称移動の操作となっている。
これらの操作はアフィン変換といって、(x,y,1) というベクトルに、操作ごとに所定の行列をかけることで、操作後の座標を得られるような性質を持つ。
つまり、複数回操作したら以下のように表すことができ、
(p3q3c3r3s3d3001)(p2q2c2r2s2d2001)(p1q1c1r1s1d1001)(xy1)
行列のかけ算はどこから計算してもよいので、操作を表す行列の方を1から順に先に計算して保存しておけば、 後から (xi,yi,1) を放り込んでやれば複数回の操作をまとめて行ったのと同じことになる。
実装では、行列をスムーズに扱えるかちょっと自信がなかったので、単純化して実装した。
今回の操作においては、上記の行列で p,q,r,s の4つのうち、(p,s) か (q,r) のいずれかは両方0になっている。
(90度以外の回転などをすると、両方に非0の値が入ってくる)
これを利用して、「o
: (p,s),(q,r) のどちらが0かフラグ」を含む5つの値を管理することで、行列と同様の情報を持たせた。
まぁ、ぱっと見で DP[i]=i マス目までにかかる回数期待値、みたいなのを行いそうではあるが、一筋縄ではいかない。
これは循環する要素のあるDPとなっている。
このようなDPは埋め方に工夫が必要になる。
今回の場合、
なので、確率が十分に低くなり、期待値に与える影響が小さくなるまで、繰り返し計算する、という方針をとる。
ただ、結果的に前者と似たような実装が必要になったので、前者の方がスマートと思う。
(解法2に、前者の方法も書いた)
さて、ではどれくらい繰り返せばよいかというと、スタートに戻る確率が高いほど、期待値に与える影響が小さくなるスピードが遅くなる。
ゴールに行ける確率が(0では無い場合で)低いのは、例えば M=2 で、10個のスタートに戻るマスが2つおきにある場合など。約99.99987%でスタートに戻る。
これは例えば 105 回スタートに戻ってもまだゴールできない確率は88%近くあり、期待値に与える影響はなかなか小さくならない。
1回スタートに戻るごとに O(N) かけて計算していては間に合わない。
高速化の必要がある。
K の制約が小さいのは、このように意地悪なケースで指数的に回数が増えてしまい、精度を保つのが難しくなるからと思われる。
ここで、期待値は一次式の形で表現できることを利用する。
何回スタートに戻されたか、という点で分けて考察する。
t 回スタートに戻されてマス0にいる時の、回数期待値を Et、確率を Pt とする。
また、t ごとに、以下の2つのDPを考える。
DPE[0]=Et,DPP[0]=Pt であり、また、DPの遷移は以下のようになる。
従って、遷移を見ると「DPE の各要素、DPP の各要素」「今回の t でスタートに戻される場合の回数期待値 Et+1、確率 Pt+1」「今回の t でゴールする場合の回数期待値、確率」は、全て Et,Pt の一次式の形で表せることがわかる。
ただしゴールはオーバーしてもいいので、「ちょうどマス i に止まる」場合と遷移が微妙に異なる点に注意。
この a~i の係数はスタートに何回戻されても(DPの遷移が同じで)不変なので、O(N) で1回だけ求めてやれば、後は t ごとに O(1) で次々と計算していける。
これで、十分に期待値への影響が小さくなるまで計算を回すことが可能になった。
上記では DPE,DPP で説明したが、実際には各マスへの回数期待値、確率を aEt+bPt,cPt と表現したときの a,b,c をそれぞれDPで計算する。
また、各遷移において、自身の M マス手前までの連続区間の和が必要になるので、最初から累積和で保持しておくとよい。
これは難しかった。
1次式の係数をDPするのは同じだけど、繰り返し収束するまで計算しなくてもいいし、より正確な値が出る解法。
先頭からではなく、末尾からおこなう。
これを、DP[0]=x として、ax+b の形で計算する。DP[N]=0x+0 となる。
遷移を考える。
i がスタートに戻るマスだった場合、最初からもう一回遊べるドンなので、残り回数期待値は x そのものになる。つまり、a=1,b=0 となる。
それ以外の場合、i から j に行くときの残り回数は DP[j]+1。これが j=1~M についてそれぞれ確率 1M で発生するので、
係数 a,b についてばらすと、
となる。累積和で管理しておけばよい。添字が N をオーバーする分については、DP[j]=0x+0 なので累積和には影響しない。
これをもとにDPを計算していくと、DP[0] が2通りで表せるようになる(x=DPa[0]x+DPb[0])。これをとくと答え。
ただし、必ずスタートに戻されてしまう場合、a=1 となる。その場合は-1を出力する。
先頭からだと、ルーレット1回分の加算値が確率になるので、期待値と確率を両方持たないといけないけど、末尾からだと1でよいので、こっちの方が計算楽だった。
先頭からやったって DP[0] を2通りの方法で表せるんじゃ無いの、と思うんだけど、なんか答えが合わなくなる。後ろからだとできるのに、違いは何なんだろうか。
解法1のように前からDPを行うが、 1次式で行う必要は無く、「1周目で」到達する場合の回数期待値と確率を直接求めればよい。
幾何分布の公式から「確率 p で成功してスコア X、1−p で失敗してスコア Y を得る試行を、はじめて成功させるまでに得るスコア期待値」を算出できる。
DPの遷移は以下のようになる。
最終マスのみ遷移が変わるのでそこに留意して、以下が求められる。
これで求められるのは、確率を反映して平均された期待値 (たとえば確率 1/2 で 3、1/4 で 5 になる変数があったら、32+54=114)だが、 これを確率で割ることで確率反映前の重み付き平均回数 113 にする。
その上で、各周目でゴールする回数期待値を考えると、
この無限和をとればよいので、|1−p|<1 の条件下で
という、単純な数式となる。
これを計算してやれば、答えとなる。
この問題では循環が常に「スタートに戻る」で、成功するときも失敗するときも常に同じ状態から開始しているので簡単な公式に落ち着いたが、 これが「マス x に飛ぶ」などだったら、やはり末尾からDPの方が汎用性はあるか。
二分探索により、DP[0] を仮定することでも、求めることができる。
P と仮定して末尾から埋めていって、最終的に求めた結果 DP[0]<P ならば、最初の見積もりが大きすぎたので、次は小さい数で試す。
計算量は答えとしてあり得る上限を C として、O(NlogC) となり、一次式DPなどと比較するとlogが付く分だけ若干重い。
二分探索が可能であるためには、「本当の答えより小さい P を指定した場合は必ず DP[0]>P となり、大きい P を指定した場合は必ず DP[0]<P となる」必要がある。
遷移を見ると、DPの各値は足し算と割られる数としての割り算しかされないので、真の値を T として P=T+k で DP[0] を求めたとき、差分の k の符号は変わらないことがいえる。
別の表現をすると、解法2のように1次式DPで DP[0]=aP+b と表せる際、(ゴールできる可能性があれば)a<1 なので、
となり、k の符号と、P−DP[0] の符号は一致することがわかる。
P と DP[0] の大小関係で次の範囲を決めるので、もし、中盤で偶然、演算誤差により次の探索範囲を誤ってしまえば、答えが離れたものとなってしまう。
誤差のなるべく出ない方法で評価をする必要がある。
例えばこの問題の例では、DP に累積和の値を直接持たせると、最終的な値が最大で 1017 くらいになるため誤差が大きくなり、いくつかのテストケースでWAとなった。
尺取法のように、幅 M の DP の合計値を別で管理して、スライドさせた時の差分を更新していく方法なら、値は 1011 くらいとなるので大丈夫だった。
どうしても誤差をなくすのが難しい場合、|P−DP[0]| がある程度小さければ次は [L,P),[P,R) 両方の範囲を試す、などの方法が考えられる。
二分探索なら、1次式DPでは解けないような問題でも解くことができる。
例えば「スタートに戻るマスを踏むと5回休みとなるが、いつでも自主的にスタートに戻ることもできて、その場合はペナルティなしで再スタートできる」みたいなルールとする。
スタートに戻るマスを踏む確率が高そうなマスに止まってしまったら自主的に戻るのが正しい場合もあり得そうだが、 結局どちらがよいかの比較を行う際、1次式DPだと「3x+5 と 4x+4 はどちらが得?」みたいな比較ができない。
二分探索なら、具体的な数値が入っているので比較でき、最適な戦略をとった場合の期待値を求めることができる。