Codeforces Round 604

問題：https://codeforces.com/contest/1264

A. Beautiful Regional Contest

金メダルは最大得点のみとしてよいです（そうでない解があれば一部を銀に変えても解になる）．銀メダルはそれより多い人数で切れる最初のところとしてよいです．

• https://codeforces.com/contest/1264/submission/223718995

B. Beautiful Sequence

始点と終点を決めると $x,x+1$ の間をうつる回数が決まります．よって eulerian trail を作る問題になります．

• https://codeforces.com/contest/1264/submission/223719007

C. Beautiful Mirrors with queries

答はチェックポイント間の期待値の和です．答の差分更新をすることにすると，$2$ つのチェックポイントの場合が解ければよいです．例えば各点を出る回数の和と考えます．各点を出る回数は，そこから先の成功率の積の逆数となります．総積と suffix product sum の組のようなものをセグメント木で計算します．

• https://codeforces.com/contest/1264/submission/218412345

D. Beautiful Bracket Sequence

最大深さ部分列は，ある場所から手前の “(” と後ろの “)” を全部とる，というような解になります．すると，あるひとつの “(” を固定したときにそれを含むような “?” の置換方法の計算式を作れます．これは二項係数の区間和になるため，それを場所ごとに足せばよいです．

• https://codeforces.com/contest/1264/submission/254024404

E. Beautiful League

トーナメントグラフにおける三すくみの個数は，各頂点の次数だけから求まります．これは，同じ頂点から出ている辺の 2 つ組をダブルカウントする（頂点の 3 つ組から数える・始点から数える）ことで分かります．結局頂点次数を $d_i$ として $(\genfrac{}{}{0ex}{}{d_i}{2})$ の総和を最小化する問題になります．コストが下凸なので，これは最小費用流で解けます．（コストは $1+2+\dots +(d_i-1)$ ですが，最小化なので各コスト $k$ を自由な順でとると言い換えてよいので，単にコスト $1,2,3,\dots$ のアイテムがひとつずつあると見なせます）．

• https://codeforces.com/contest/1264/submission/223718793

F. Beautiful Fibonacci Problem

$a=1,n={10}^7-1,d=1$ のときに作れればその部分列で満たすものが作れるので，入力の等差数列は $1,2,3,\dots$ であるとしてよいです．

フィボナッチ数は代数的整数 $a,b$ を使って $(a^n-b^n)/(a-b)$ と書けるので，まずは普通の等比数列 $a^n$ のときに何ができるかを考えました．$N={10}^6$ に対して $a^n=1+N(\mathrm{mod}{N}^2)$ となる $n$ が見つかれば $a^{kn}=1+kN(\mathrm{mod}{N}^2)$ となり作れています．

同じようなことをしようとします．$t=(1+\sqrt{5})/2$ として $t^n=a_n+b_{n}t$ としたときに $a_n=F[n-1],b_n=F[n]$ が成り立ちます．$t^n=1(\mathrm{mod}N)$ となる $n$ をとって調整することで，$t^n=1+N+bNt(\mathrm{mod}{N}^2)$ のような状況を見つけることができます．

• https://codeforces.com/contest/1264/submission/304692662