Codeforces Round 1090

A. The 67th Integer Problem

$x$ 以上の何かを出力すればよく,例えば $x$ を出力すればよいです.

B. The 67th 6-7 Integer Problem

$7$ 通り全部計算すればよいです.

C. The 67th Permutation Problem

$3N-1,3N-3,3N-5,\ldots$ が中央値になるようにするのが最適です.

D. The 67th OEIS Problem

$1\times 3,3\times 5,5\times 7,\ldots$.

E. The 67th XOR Problem

残る値としてありうるものが,$a_i\oplus a_j (i\neq j)$ の形の数全体であることが,帰納法で証明できます.

F. The 67th Tree Problem

根の偶奇は確定します.根以外について数えたものを改めて $x,y$ とします.

$x,y\geq 0$ が必要です.また $x\leq y$ が必要です.これは even subtree の子に odd subtree が存在しなければいけないからです.

これは十分条件もあり,根に頂点数 $1,2$ の subtree を適切につけていけばよいです.\

G. The 67th Iteration of “Counting is Fun”

$b_i$ 未満の人がすべて正しくなるように決めたとして,自身も正しくなるようにする方法の個数.

というのをすべての $i$ についてかければよいです.

$b_i=0$ のときは,$a_i=0$ の $1$ 通り.それ以外では,両端の min が大事です.

自身を $b$,自身が両端の min を $a$ とします.$b\leq a$ ならば解なし.$b=a+1$ なら,時刻 $b-1$ までに座った人数が $a_i$ の上限.$b>a+1$ ならば,時刻 $b$ で条件達成していて条件 $b-1$ には条件達成していなかったというところから $a_i$ の上下限がでます.

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