Codeforces Round #603 (Div. 2) (Virtual) 解説感想

2020/10/15 21:00~から2時間. URL:https://codeforces.com/contest/1263

所感:

A-Dで4完. Eは通せなかったがコーナーとバグにしっかり配慮してペナ0だったのがよかった.

A. Sweet Problem $t$

まず「異なる２つを選ぶ」という制約を無視すると、総和/2を切り下げした値が答えになる。

それを加味した上でその制約を入れて考え直すと、一番大きい値が半分以上である場合順当なペアの割り当てができないことがわかる。

したがって、一番大きい値をペアが作れるくらいまで減らすのがよい。

実装を楽するならソートして(小さい２値の和)*2が一番楽そう。

B. PIN Codes

少し難しかった。

まず制約がN <= 10なこと、かつある桁のPINの通り数が１０あることから答えは最大でも９であることがわかる。

より簡単に考えると、変更する桁を固定するのがよさそう。そう考えると一番上の桁を固定して、それ以降の桁で各数字をグループ分けしてなるべく振り分けないような操作が考えられた。

よってグループ分けした際に、桁に対して使用済みflagを管理して一致している数を今ある数と被らないように振り分け直す、という方法で行った。

C. Everyone is a Winner!

こちらは典型。平方を考えると数の分布は√Nまで存在が保証され、逆にそれ以降は徐々に間隔が広まっていくという性質がある。(y = 1/xのようなグラフをイメージ。過去問で得た知見だったため詳しく解説ができない(すまねえ))

なので1~√Nまでsetに入れて、さらにそれを割った数もsetに入れる。最後に0を入れればOK.

D. Secret Passwords

ちょっと焦った。UnionFindで分類分けする問題。

各文字列について行うと, N = 2e5なのでN^2でTLEしてしまう。

しかし、ここで「ある文字が同じなら等価」ということを考える。

言い換えると、ある文字列の中に、例えばaとbが入っていた場合、他のaもしくはbを含む文字列はこの文字列と等価であることがわかる。

従って、文字列内で異なる文字がある場合それらをマージしていけばいいことがわかる。

文字列の長さは高々50なので余裕で通る。

E. Editor

難しい。今回は未upsolveなので飛ばします。

F. Economic Difficulties

そこそこ好きな問題。

配列の各位置について、上の木の根もしくは下の木の根とどちらかに連結にさせていき、最終的にすべてを連結にさせたとき最小のコストはいくらか、という問題に言い換えられる。(コストはノード数、大体すなわち根からの距離-1)

ここで考えることは、単純な深さを考えた場合はただのdpでいけるが、木であるためもしかしたらショートカットができるかもしれない(祖先が根でない場合、明らかに距離より小さい値がコストになる)ということだった。

その値は、上もしくは下の木について、最後に使ったノードの位置がどこか、という情報があればいいので祖先をLCAで求めることでdp[現在位置][上の木の最終ノード][下の木の最終ノード]でdpを更新していくことでN^3logNで求まる。

……間に合わないじゃん。

頑張ってNを落とす考察をする。

結局30分ぐらいかかったが、よくよく考えるとdpの各状態に対して、最終ノードの片方は必ず直前のノードになっているということがわかる。

したがって、持つべきdpの状態はdp[現在位置][対になる木の最終ノード][上か下か]だけを保持していけばよかった。これでN^2logNなのでAC.

kaikey’s diary