Codeforces Round 1016

スポンサーリンク

A. Ideal Generator

$k$ が偶数だと奇数が作れないため NO.そうでなければ $(1,1,x,1,1)$ みたいなのを考えれば YES だと分かります.

B. Expensive Number

商を最小化というのは,商を $1$ にすることになります(残り 1 桁まで削ると満たす).

すると残せるものは $0000a$ の形のものです.

C. Simple Repetition

$k=1$ と $x=1$ は愚直に判定します.

$k>1$ かつ $x>1$ ならば $x$ より大きな $x$ の倍数になるので素数ではありません.

D. Skibidi Table

2 つの問題がありますが,どちらも四方向のどこにあるかを判定して再帰的に解きます.

E. Min Max MEX

二分探索します.union が全体という条件は外してよく,手前から貪欲にとっていきます.

F. Hackers and Neural Networks

無駄に複雑設定で読解が大変ですが,入力は場所ごとに $a$ と一致するかの $01$ 列としてよいです.

すべての行が $0$ であるような列があるならば不可能です.

そうでない場合,行にある $0$ の個数の最小値を $k$ として,コスト $n+2k$ が最小できます.達成するにはその行を連打して全ての列を埋めたあと,$0$ の列をひとつずつ削除・選択すればよいです.$n+2k$ 以上必要なのは,最初 $k$ 回の操作は必ず外れを引く可能性があることから分かります.

G. Shorten the Array

尺取りします.判定は最後に追加した要素と何かという組だけで行えばよく,binary trie を使えばできます.

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