Educational Codeforces Round 86

スポンサーリンク

A. Road To Zero

操作 1 で $x=y$ にしたあと,どちらかの操作で $1$ ずつ減らしていきます.

B. Binary Period

周期 2 での解を作ることはできて,010101… とすれば $2$ 文字にひとつずつ選んで $t$ を作れるからです.周期 1 でできるかは判定します.

C. Yet Another Counting Problem

周期 $ab$ があります.

D. Multiple Testcases

大きいものから順に貪欲に処理していきます.

E. Placing Rooks

置かれていない行と,置かれていない列がともに存在するとダメです.

すべての行に置かれているとします.$K$ の条件は何かを置いた列数がいくつであるかを表しますとなります.よって写像 $\{1,\ldots,n\}\longrightarrow \{1,\ldots,n\}$ の個数を値域の大きさが与えられて数える問題になります.包除原理で数えられます.

F. Make It Ascending

操作は,「集合に分割」「代表元を選んでそこに集める」となります.最終的に代表元のところだけ左から見て,sum が増加列になっていなければいけません.

ひとつめの集合から順に作っていくことを考えて dp します.「今まで使った要素全体の集合」「代表元の場所」に対して,作った集合の個数・最後の集合の総和が必要そうです.集合の個数の方が状態が少ないので「今まで使った要素全体の集合」「代表元の場所」「作った集合の個数」をキーにして,「最後の集合の総和」を値にします.計算量 $O(N^2\cdot 3^N)$ で実装できます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました