ARC170で検索すると、スターウォーズに出てくる宇宙戦闘機が出てくる。
満たさないものを数える。
要素が1~10しかないので、ちょっと長くなれば何かしらの等差数列はできてしまいそう。
少なくとも同じ整数が3つ出てきたら公差0の等差数列なので、長さ($r-l+1$)が21以上になることはない。
なので、全ての $(l, r)$ の組の個数 $\dfrac{N(N+1)}{2}$ をとりあえずの答えとして、
とすれば、残ったものが答え。
$l$ を固定した時の $r$ がそこまで長くならないので愚直に調べても大丈夫という、 計算量の適切な見積もり(または直感)が必要な問題。
あり得る最大の“等差数列ができない区間の長さ”を $k$ として、$O(N k^2)$ などで計算できる。
$m(i)=mex(A_1,A_2,...,A_i)$ とする。
S 0 1 0 0 1 0 1 1 Aの例 2 0 3 5 1 2 4 6 m(i) 0 1 1 1 4 4 6 7
$S_i=1$ の時、$A_i$ は $m(i-1)$ で一意に決まっている。
一方、$S_i=0$ の時、$m(i-1)$ 以外なら何を置いてもよい。
$S_i=0$ の時に $m(i)+1$ とか $m(i)+2$ とかが埋められてたら、 次に $S_i=1$ で $m(i)$ が埋められたとき、その次のMexは一度にたくさん増えることもある。
S 0 1 0 0 1 Aの例 2 0 3 5 1 m(i) 0 1 1 1 4 ^ ^ ←次のMexの1より1~2多い 2,3がここで埋められているため、 ^ ←その後に1が埋められると、次のMexは一気に4まで飛ぶ
この性質のために、DPをするにしても「現在のMex」をキーとしても、次のMexを特定できないためあまり上手くいかない。
もし、$N$ より $M$ の方が十分大きければ、
なので、$M^{Sに出てくる0の個数}$ が答えとなる。
その方法で上手くいかないのは、$M$ が小さくて、$S_i=1$ でMexを更新したいのに次のMexが $M+1$ 以上となってしまう場合。
S 0 1 0 0 1 0 1 1 Aの例 2 0 3 5 1 2 4 x ←M=5 のとき、6を置けなくて破綻 m(i) 0 1 1 1 4 4 6
破綻するのは、それまでに $0~M$ が全て出現しているのに、$S_i=1$ が来てしまった場合。
つまり、「$0~M$ のうち、出現した種類数」を管理することで、破綻するかどうかを判別可能となる。
で、$DP[N,1~M]$ の和が答え。$M$ 自体はでかい可能性があるが、 実質取り得る値は最大 $N$ なので、DP配列は $N \times \min(N,M)$ だけ用意しておけばよい。
使う知識は「三角形が作れる ⇔ 3辺の長さ $a,b,c$ で一番長い辺を $c$ として、$a+b \gt c$」のみ。
だが、細かな場合分けがなかなか難しい。
無理なケース、可能なケースを洗い出してみて、なるべく簡潔に全てのパターンを網羅できる考え方にまとめあげたい。
Alice 1手目, Bob, Alice 2手目が出すカードの整数を、それぞれ $a,b,c$ とする。
まず $a$ を固定して全通り試す。
各 $a$ に対し $b$ を、$a$ より小さい場合と大きい場合で分け、どのような $c$ に対しても勝てる $b$ があるか調べる。
最長辺の候補は、$a$ か $c$。
三角形を作れなくなるのは以下の2通り。
|------a------| a >= b+c1 |--b--||--c1-| |------a------||--b--| a+b <= c2 |----------c2----------|
Bobにとって、$b$ は $B$ の中で最も小さい数 $B_{min}$ を使うとしてよい。
Aliceにとって、$c_1$ は $a$ の次に大きい数、$c_2$ は $a$ の次に小さい数を使うことにしてよい。
$b,c$ ともに $a$ に対する最適なカード候補が確定するので、実際に確認する。
最長辺の候補は、$b$ か $c$。
三角形を作れなくなるのは以下の2通り。
① |--a--||--c1--| a+c1 >= b |-------b-------| ② |--a--||------b------| a+b <= c2 |----------c2----------|
こちらは、$a \gt b$ の場合と比較して少々難しい。
$B_{min}$ のような、「$b,c$ はこれを選んどきゃいい」みたいな決定版が無い。
$c_1,c_2$ を、$A$ の大きさ順で隣り合う数とする。
この間の“ちょうどいい” $b$ を出されたとき、
「$c_1$ 以下を出したら①になるし、$c_2$ 以上を出したら②になる」という事態に陥り、Aliceは負ける。
ちょうどいい $b$ の範囲とは、$c_1+a \le b \le c_2-a$ となる。
つまり、$c_1,c_2$ を互いに $a$ ずつ縮めた範囲となる。
c1 c2 |--a--> <--a--| |----| ←この間にbが存在したらBobの勝ち c1=Amax |--a--> |---------... ←または、c1がAmaxの場合、こうなる
いずれにしても、「Aliceは $X$ 以下の $a$ を出したら負ける」という形の制約となる。
各 $b$ につき、$A$ の中で $b$ に最も近い両側の $c_1,c_2$ を調べれば、$X$ が分かる。
では、$X$ より大きな $a$ を出せば $a \le b$ の条件下ではAliceは負けることが無い……かというと、そうではない。
$c_1,c_2$ と $a$ が、同じカードとなる場合がある。
c0 c1=a c2 |--a--> <--a--| |----| ←この間にbは存在しなくても、、 |--a--> <--a--| c1をaとして使ってしまった場合、 |---------------| ←bが存在したらAliceが負ける範囲はこっちになる
これは、$a$ を全探索する時に両隣の数を確認し、$c_0+a,c_2-a$ の間に $b$ が存在しないかを確認すればよい。
まとめると、
なんか問題文は複雑だが、大部分はBFSやDFSでいつもやっていることの説明に過ぎない。
「先頭に追加するか、末尾に追加するか確率的に選択される」という点が変わっている。
グラフが円状なので、$Q$ には終始、高々2要素しか入っていることはない。
結局、「時計回りルートと反時計回りルート、どちらの探索を進めるかが確率的に選択される」という問題になる。
直前に進めたルートと同じルートを確率 $p \ (=\frac{P}{100})$ で進め、反対のルートを $q \ (=1-p)$ で進めることになる。
2本のルートしかないので、$D_v$ が取り得る値は、 時計回りルートの $v-1$ か、反時計回りルートの $N-v+1$ しかない。
Dvの値の一例 ⑧--①--② 1--0--1 | | | | ⑦ ③ 2 2 | | | | ⑥--⑤--④ 3--4--5
「グリッドを左上から右下まで最短距離で移動する経路の数え上げや確率に帰着させる」的な言い換えはよくあるが、 この問題もできるっちゃできる。(ただし、後述の通りTLEとなる)
今回の場合、下移動を時計回り、右移動を反時計回りに1進むことに対応させられる。
(合計 $N-1$ 回移動した箇所のマスに進む確率)×(それぞれの場合のDの合計)を、各マスについて合計すれば答えとなるのだが、
ただ、$N$ の上限が $10^{18}$ なので、そのままでは無理っぽい。
まぁ、ひょっとしたら上手くまとめられるかもしれないし、イメージをつかむつもりで進めてみる。
N=5 時計回り 反時計回り Dの合計 □□□□■ ← 0,1,2,3,4 0 10 □□□■ ← 0,1,2,3 0,1 7 □□■ ← 0,1,2 0,1,2 6 □■ ← 0,1 0,1,2,3 7 ■ ← 0 0,1,2,3,4 10
ちょっと特殊なのが、右に進む、下に進むに対して進む確率が決まっているわけではなく、 「直前の方向を継承する場合に $p$、方向転換をする場合に $q$」の確率で選択されるということ。
なので、あまり一般的な経路数え上げのセオリーは使えない。
一応、以下のDPで計算できるし、
もう少し考えると、1から埋めていかなくても、 「どの列で方向転換するか」「方向転換した列で、それぞれ何回下がったか」により、組合せで求められはする。
ただ、$e$ のループで $O(N)$ かかるし、仮にこれが求められたとして、1頂点ずつ求めていったらさらに $O(N)$ かかる。
まとめて綺麗な形にする方法もパッと見えない。
別のアプローチが必要となる。
前述の通り、「時計回りルートと反時計回りルートの移動回数が $(x,y)$ となる確率」を求めて、 そこに「その時の $D$ の和」をかける方針だとTLEなので、 どうにかして「移動回数が $(x,y)$ となる確率 × その時の $D$ の和」の $x=1~N-1$ の総和を直接的に求める、ということをしないといけない。
ここで解説を読むが、まぁ、これは思いつかないわ、という感じ。
何らかの積の形になっているものを、選び方として捉えなおす方法を「積の和典型」と呼ぶが、これもその一種かな。
「直前の方向」と合わせて6通りの状態を管理することで、$6 \times 6$ 行列で遷移を表現できる。
直前↓直前→ 0 1 2 0 1 2 直前↓ 0 p p p q 空欄は0 1 p p q 2 p q 直前→ 0 q q q p 1 q q p 2 q p
この遷移行列を $A$ として、$A^{N-1}$ の「直前→、0個選択」状態から、 「直前↓、2個選択」「直前→、2個選択」状態への和が、$L$ 成分の答えとなる。
同様のことを $R$ 成分でも行うことで、最終的な答えとなる。
今度は→移動から2個選ぶことになる。