Codeforces Global Round 1

スポンサーリンク

A. Parity

$b$ が偶数なら末尾,そうでなければ sum.

B. Tape

隙間のうちいくつを埋める必要がある,となるため隙間の長さをソートして貪欲にとります.

C. Meaningless Operations

$a \mathrm{AND} b=0$ の場合を考えることで,$a$ の topbit を $k$ として $b=2^{k+1}-1-a$ という戦略が見つかります.これで $a\neq 2^{k+1}-1$ の場合は自明な上界が達成できます.

$a=2^k-1$ の場合は別に前計算しておけばよいです.

D. Jongmah

各 $x$ に対して,連番 $(x,x+1,x+2)$ を使うのは $0,1,2$ 回のどれかとしてよいです.なぜなら $3$ 回使うパターンは $(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)$ に変換できるからです.

$0,1,2$ からなる列に関する最適化問題になります.これは dp で解けます.

E. Magic Stones

差分をとる,つまり $a$ の代わりに $b_i=a_{i+1}-a_i$ で定まる $b$ を考えると,$a$ に対する問題文の操作は $b$ に対する隣接スワップになります.

F. Nearest Leaf

dfs で木を移動しながら,「ans[i] := i までの距離」を管理します.

すると,必要な操作は部分木加算となりますが,番号付けが dfs 順であるためこれは区間加算です.よって区間加算と区間最小値ができる遅延セグメント木で解けます.

G. Tree-Tac-Toe

先手の勝利条件を列挙していきます.

次数 $4$ 以上の点があればその近くだけで勝てます.次数 $3$ の点で葉でない方向が $2$ つあるならばその近くだけで勝てます.

これを除外すると,ほぼパスで,直径の端点の近くだけに葉がついているようなグラフが問題だとわかります.パスの中央付近の初期状態が白いときも先手勝ちです.

結局,とてもグラフが小さいときの例外を除けば,考えるべきは「パス」「ただし端点の隣には葉をつけられる」「葉は白いかも,他は無色」くらいです.パスの長さを除けば有限通りの場合を考察すればよくて,もう少し場合分けすれば解けます.

H. Modest Substrings

ある substring が modest かを判定しようとすると,「決まり字」のポイントがあります.つまり,$1$ 文字ずつ見ていってある substring に到達した瞬間に modest だと決まります.

[123,456] なら,「2**」「3**」「13*」「14*」などです.

「$n$ が十分小さくて,$n$ 文字目まで見たときにこれを suffix として持つならば +1 点」というようなルールが $O(|L|+|R|)$ 個得られます.ルールの生成は,通常は $l$ や $r$ との lcp の次の文字が決まり字となることから行います.最大長さのところに注意したり,$1$ 文字目の leading zero に注意する必要はあります.

これらのルールから Trie を作れば,Aho-Corasick オートマトンにおいて,「何文字目までにこの頂点の部分木(suffix link tree に関する)を通れば $+1$ 点」という形でルールを記述できます.得点の最大化は dp で行えます.

辞書順最小構築が問われています.これは,「何文字時点で trie のどの頂点に居る」という状態に対して「そこ以降で獲得可能な最大スコア」を持つ dp を考えて,後ろから計算していけばよいです.

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