Educational Codeforces Round 73

スポンサーリンク

A. 2048 Game

$2048$ 以下のものの総和が $2048$ 以上であることが必要十分です.

B. Knights

単に $i+j$ の偶奇によって色を変えれば明らかに最大値を達成できています.

C. Perfect Team

二分探索します.判定問題では $c,m$ を $1$ 人ずつ割り当てたあと,残った人を適当に割り当てることを考えます.

D. Make The Fence Great Again

各 $i$ に対する操作は $2$ 回以下としてよいです.これは,他の部分を固定して $i$ に対する操作だけ調整することを考えれば分かります.あとは最後の要素に対する操作回数について dp できます.

E. Game With String

まず B 手番のときについて考えます.$[b,a)$ の長さがあれば B 勝ちです.その長さ以外で操作可能なところを可能な限り操作して,他になくなったらそれに着手すればよいです.

すると,$[2b,\infty)$ の長さがある場合も B 勝ちです.長さ $b$ の区間を残すような初手をとればよいです.

どちらもにも該当しない場合はすべての長さが $[a,2b)$ で,どちらのプレイヤも $1$ 回とるだけの区間です.この場合はそのような区間の個数の偶奇で決まります.

これで B 手番の場合の判定ができました.問題は A 手番ですが,これは A の初手を全探索して B が負けるような状況に追い込めるかどうかを判定すればよいです.

F. Choose a Square

$k$ をインクリメントしながら $ans[i] = score([k,i]\times [k,i])$ を管理します.座圧してからこれを行うと,遅延セグメント木で区間加算と区間 max をできればよいことが分かります.

G. Graph And Numbers

包除原理を考えます.禁止する数の集合を決めて数えます.それぞれは独立集合の数え上げや二部グラフ判定程度の典型的な問題になります.

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