C - Swiss-System Tournament

純粋にシミュレーションをすればよく、プログラムのコンテストってこういうのを言うんじゃないかと思った次第です。

普通のトーナメントのように勝ったもの同士が戦うのではないようですが...

詳しくは提出コードを見てほしいのですが、肝となるのは、「 Playerクラスが1ラウンド(トーナメント的な言い方だと1回戦?)終わるたびに、順位別にソートされる。同勝数ならNoが小さい方が先」の一点だけです。

Playerクラスという「エントリーNo, 勝数、出す手」をまとめたクラスでオブジェクト指向っぽく書くと、スッキリと実装できた気がします。

D - Between Two Arrays

難しかった。ので、解説を見て理解した範囲で書いていきます。間違ってたらすみません。

問題文を紐解くと以下のようになります。
$a_i,b_i$に挟まれる形で$c_i$が存在して、しかも$c_{i-1} \le c_i$でないといけません。

以下の例から、dpテーブルを書いてみます。
a ={1,2}
b= {2,4}

答えから書くと、$(c_1, c_2)$は(1,2), (1,3), (1,4), (2,2), (2,3), (2,4)の6つあります。

テーブル内の空の欄は値0です。公式解説のdpの更新式にあるotherwiseの要素に該当します。

欄1個が、「数列cのi番目までの要素が確定したとき、i番目の要素がjである組の個数」となります。
例えば、$dp_{1,1}$は$(c_1, c_2)=(1, ?)$のように1番目までの要素が確定して、1番目が1である組の個数です。この時点で$c_2$は未定なので?です。

計算は赤線のように、i-1番目の列から値を足し込んでいきます。
例えば、$dp_{2,2}$は2番目までの要素が確定して、2番目が2である組の個数です。この時点で先程の?の要素が確定していきます。

このようにi-1番目の列で?だった要素が確定していきます。総和を取ればdpテーブルの欄が一つ埋まります。

答えはi番目の列(一番右の列)の欄の値(組み合わせ数)の総和です。数列cの最後の要素がjとなる組の数を足し込むことになります。

ここでdpテーブル高速化の話になります。 dpテーブルの欄を一つ埋めるのに、i-1番目の列から0~jの欄の要素を足し込むことになるので、無駄が発生します。

ここで、例えば$dp_{2,3}$の計算を考えます。

累積和の考え方で、直前に計算した$dp_{2,2}$の要素を使ってしまえば、再度足し込む必要がありません。図4,5を比較してみてください

これでテーブルの更新が高速化できました。

dpっぽいかなと思えど、更新式が思いつかない、といういつものパターンでした。