AGC019F - Yes or No が簡単に見えるかもしれない別解
想定解とは異なる解法で解いたのでメモを残しておきます。
（恐らく、対応する日本語記事はないと思ったため）
問題概要
N+M 個のマルバツ問題があり、そのうち N 個の問題の答えはマル、M 個の問題の答えはバツということを知っています。
問題がランダムな順序で出題されるとしたとき、最適戦略を取った場合に正解できる問題の数を期待値を答えてください。
グリッドへの言いかえ
まず、グリッド上での問題に言い替えます。
「N×M のグリッドについて、左下の端点から右上の端点に、右または上のみの移動で進む経路の内 1 つが選ばれる。各頂点において、次に右へ進むか上へ進むかを予想した場合に予想を何回当てられるか」
という問題になります。
最適戦略
最適戦略はシンプルで、
「右と上のうち、残りの移動回数が多い方を予想する。ただし、残りが等しい場合はどちらを予想してもよい」
という戦略になります。
この戦略の模式図（N=6, M=4）は下図の通りです。
このとき、緑色の矢印が最適戦略で宣言する向きです。
ただし、右と上の残りの移動回数が同じところを橙色の頂点で表現しており、その頂点ではどちらの向きを宣言してもよいです。
経路に対する正解数
ある経路について正解できる回数を考えます。
例えば、下図太線のような経路を考えます。
このような経路において、
- 赤色の矢印：必ず正解できる（元々、緑色の矢印だった）
- 黒色の矢印：必ず正解できない
- 青色の矢印：1/2の確率で正解できる（橙色の頂点から右に進む経路の数と上に進む経路の数は等しいため）
となります。よって、正解数の期待値は（赤色の矢印の数）＋1/2 ×（青色の矢印の数）です。
数え上げ
後は、全ての経路に対して、（赤色の矢印の数）＋1/2 ×（青色の矢印の数）の総和が求められれば答えが求まります。
赤色の矢印の数については、以下の事実が成り立ちます。
「任意の経路について、赤色の矢印の数は常にmax(N,M)となる」
（経路をいい感じに折り返してみれば、直感的に分かると思います）
青色の矢印の数については、「全ての経路に対して橙色の頂点を訪れる回数の総和」を計算して1/2倍すればよいです。
期待値の線形性を用いると、「各橙色の頂点を通る回数」を計算できればよく、これは combination(2*i, i) * combination(N+M-2*i,N-i) になるため、（前処理を覗いて） O(max(N,M)) で計算できます。
以上より、この問題は解けました。コードはかなりシンプルになります。
問題の感想
必ず勝てる回数に注目すると見通しが一気に開けるところが非常に面白いと感じました。
記事を書いた感想
1年半前の夏に電車に揺られながら思いついたのが懐かしいなぁ・・・
前々から(1年半前から)書こうと思っていましたが、ずっとダラダラしていてようやく書きました。
初めて解法記事を書いたので、フィードバックをもらえると嬉しいです。
