Codeforces Round #695 (Div. 2)

A

98765...(一敗)(適当すぎ)

前の桁の数を貪欲に大きくしたいのでs[0]は9

このときs[1]は0か8になる、8の方がよい

このときs[2]は7か9になる、9の方がよい

→後ろが定まる

 

簡単枠でも考察の道筋はちゃんと意識しましょう()

 

 

B

昔のAtCoderの問題で見たことあるような気がするが、考察で大変なことに

 

階差数列の隣接項の符号を見て差分更新できる?

細かい場合分けで燃えそう

階差の符号を取り出していじってみる、ある数の値を変えるとき、左右の数と同じにするのが最適?

変え先の数を全探索、階差を変更して差分更新

 

場合分けを頑張る方針は詰めるのに時間がかかりがち、早めに探索を考えた方がよさそう

探索は基本方針なので詰まったらまず考えるべき

 

C

ある数の寄与分に注目して考えると、異なる集合に数が存在する限り、ある数の係数の符号を反転する操作ができることがわかる

なるべく多くの数の係数を+にしたいが、全て+は無理

何もしない数を固定すると、他の集合の数全てに対して一度は操作を行うことから、答えが6通りに絞れる→全部書く

 

D

グリッド上の経路数に落ちそうな気がする?

落ちない、DPを考える

aの各項の係数がわかれば差分更新ができるので、係数が欲しい

dp[i][j]:=i回の移動後にjにいるパスの数 が計算できる

パスごとにある位置を通る回数を求めるのは難しそう

主客転倒を試す、i回移動したときにある位置を通るパスの数を考えると、dpの値から計算が可能

 

AtCoderにありそうな言い換え

 

E

適当な根付き木を考える

根となりうる頂点の条件を列挙したい、木を書いて明らかな性質を整理する

根を端点とするパス上に同じ数が3つある場合→0

 

同じ数が根を端点とするパス上に2つある場合...(1)

→そのパスの内側の連結成分にある頂点のみ、根となる可能性がある

同じ数が根を通らないパス上に2つある場合...(2)

→その数より上にある頂点のみ、根となる可能性がある

 

それぞれの条件を満たすものの積集合が欲しい

愚直に求めるのは大変そう、ABC187-Eに似ているので包除で実装を楽にしたい

 

 

(2)...

根になりうる部分の形は複雑、一方で根となりえない部分はいくつかの部分木状になっているので、こっちを求める方が楽そう

見ている頂点vに書かれた数をxとして、(vを根とする部分木以下にあるxの数)<(全体のxの数)となっている場合、v以下は全てfalse

 

これで(2)の条件を満たさない部分と、(1)の条件を満たさない部分の一部(下側)はfalseになった

 

残りの(1)を満たさない部分を全てfalseにしたい

imosができる形ではないので、(1)を満たす部分をtrueにすることを考える

↑実は頑張るとimosでできる形になっている(!)

 

falseの位置をimosで求めることを考える

true=0、false>0として状態を持つと、それぞれの数について、条件を満たすものの積集合が取れる

ある頂点vに書かれた数をxとする、vの子cの部分木にxが含まれるものがある場合、

根に+1、cに-1をセットし、上から伝搬していけばよい

 

ある頂点vの上側を全て処理←出来ないと思ってたけど、根が決まっていれば根にimosで普通にできた(気づき)