数学寄りのセットだったこともあり、比較的良い出来だったように思います。これまでは解けたと思ってもバグ取りが終わらず点数に繋げられない回が多かったのですが、今回は大きな事故もなく順調に分かった問題を点数に結び付けられたという意味で、順位とは関係なく気分的に満足です。問題Cは、恐らく競プロ界隈での典型的な出題形式に慣れていなかったことが原因で、上位層が省略しているであろう部分の考察に相当な時間を費やしてしまいました。練習していけばまだ上に行けるということになりますね。勝できる可能性があるかを判定する。残り試合分、勝率数を上乗せした後判定する。残り試合数を数えず、敗北数だけに注目してもよいようです。pythonで、部分文字列のカウントは、.count()メソッドで行うことができます。勝必要だとして、ゲーム回数の期待値を$E_{m,n}$とします。\frac{b}{100}E_{m,n-1}\]が成り立つことがすぐに分かります。$E_{m,n}$の計算量が$O(mn)$となり、本問題は解くことができません。「漸化式を解く」必要がありそうです。\frac{b}{a+b}E_{m,n-1}\]となり。F_{m,n-1}$という型の漸化式に帰着できます。よって$F$は二項係数の平行移動の重ね合わせとなり、漸化式を解くことができます。k(m+n)$の漸化式を作ると定数項が消せる。\frac{(a+b)^{m+n}}{a^mb^n}G_{m,n}$と置けばよい。)ここから、既約分数表示を求めるところで頭を悩ませます。初めは「出題からして、明示公式が作れば約分できないことが明白になるのだろう」とか思っていたけど、どうも約分についての評価が全くできません。別の問題を解いたあと、もっと易しく解ける仕組みがあるはずだと思い再考。考えると、約分の影響は無視できます。Q$が定数倍ずれても問題ないです($Q$が$p$で割れるときだけ例外)。これに気づいて気が楽になったのか、明示公式を作る部分についてもよりシンプルな方法が見つかります。$100$回に$a+b$回だけ状態が遷移するので、引き分けがないとして解いて答を$\frac{100}{a+b}$倍すればよいです。$\frac{b}{a+b}$という分数を触っていました。この2つの気づきを得られれば、後は自然に$O(N)$になりました。解説では、「約分は無視できる」という要素について完全スルー...おそらく典型的な出題形式なのでしょうwここにずっと苦しめられたよ...経験不足ですね。———-後日気づいたことですが、そもそも「分子と分母を求める」必要すらありませんね。次のような環準同型(和・差・積を保つ写像)があります。分母)の形で持つ必要は一切なく、分数が出てきたら順次$\mathbb{Z}/p\mathbb{Z}$に移しておけば問題ないです。Minimum簡単そうに見えましたが、具体例を紙で検証している最中に「あれ?最小値だっけ最大値だっけ?」みたいなことを繰り返したため、いったん後回しにしましたw次数1の頂点については、その頂点の書き込み方さえ決めてしまえば、残りの頂点の書き込み方・得られる得点は完全に大きさが1つ小さいときの問題として扱えそうです。小さい数は端に置きたいとは自然に思えたため、このことと組み合わせて証明を考えます。「そのときのminの合計値が、$c$の小さい方から$N-1$個の和に等しい」ことが帰納的に分かります。帰納法による証明によくあることですが、成り立つべき命題さえきちんと定式化出来てしまいさえすれば、証明自体は易しかったです。個人的にはCよりも易しい問題でした。Progressionシンプルな整数論の割に、見たことはない。一応「等差数列の積・アルゴリズム」とかその英語でgoogle検索するも、パッとは見つからずw「長さ$2^k$のものだけ事前計算してはどうだろう」「始点が$d$未満のときだけでよい」など考えたけれど、必要な事前計算が$O(N^2)$になってしまう($N=100003$)。そもそも$d=1$を解かなければいけない。階乗は全部分かる必要がある。$n!$を事前計算なしに効率よく求める方法、あるいは事前計算を大幅に抑える方法は聞いたことがない。大なり小なり、階乗の一覧あるいはそれに準ずる何かは作る必要があるだろう。この時点でかなりきつい。階乗をひととおり作るだけで$O(N)$あるので、せいぜいそれの定数倍、$\log(N)$倍の類の事前計算で精一杯。解けるとすれば、階乗だけ事前計算をして、それを上手に使うくらいしか方法がないだろう。分かった!!「解法があるとすれば」という逆算の発想で、偶然思いつけたというよりも、ある意味では「思いつくべくして思いつけた」という自己評価。