2020/2/12

2019-2020 ACM-ICPC Latin American Regional L

最大値

達成可能な大きさと不可能な大きさの境涯がある→二分探索 O(NM)で判定

判定部分のセグ木はいらなかった(RMを求める範囲が単調なのでスライドさせていけばよい)

 

Codeforces 1303 C

アルファベットを頂点、passwordの中で隣接している文字間に辺を貼った時、パスグラフができればok

復元は次数1の頂点からDFSをすればよい

 

Codeforces 1303 D

可能不可能

二進数で考える

ある桁を他の桁の数で補う時、上の桁をdivideして持ってくるor下の桁を足して持ってくる ことができる

下の桁が余っているときは下から補うのが真に得 そうでない場合は最も近い上の桁をdivideする

→一番下の桁から見ていけば貪欲に漸次決定できる

 

ある程度強いサンプルを自分で作らないと嘘に気づけないのでサンプルは積極的に作ろう