ferinの競プロ帳

競プロについてのメモ

codeforces #403 Div2 A, B, C

codeforces.com

A問題

問題概要

 n組の靴下が袋の中に入っておりそれぞれペアごとに揃えたんすにしまいたい。袋の中から1つずつ取り出して机に並べる。そして、靴下が組になった時点でたんすにしまう。袋から取り出す順番が与えられる。机に並ぶ最大の靴下の数を求めよ。

解法

 実際にシミュレーションを行う。すでに机に並んでいる靴下を袋から取り出した場合、机に並んでいる枚数は1枚減る。逆に机の上には存在しない靴下を袋から取り出した場合、机に並ぶ枚数は1枚増える。O(n)で n <= 10^5なので実行時間は間に合う。


B問題

問題概要

 1次元座標上にn(n <= 60000)人の人が存在する。i番目の人は座標x[i](1 <= x[i] <= 10^9)に存在し最高速度v[i](1 <= v[i] <= 10^9)で動くすることができる。n人の人が一点に集まるときにかかる最短時間を求めよ。

解法

 ある時間tのときにn人の人が一点に集まることが可能か判定することを考える。i番目の人はx[i]-v[i]*tからx[i]+v[i]*tの範囲へと動くことができる。n人の範囲に共通部分が存在すれば可能であり、存在しなければ不可能である。ぎりぎりで可能なtが求めるべき最短時間となる。よって二分探索でtの範囲を狭めて行くことで求めることができる。二分探索を一回行うごとに範囲は1/2になるため、二分探索をn回行ったとき1/(2^n)に範囲が狭まる。200回行うと1/(2^200) ≒ 1/(10^3)^20 = 10^-60 に範囲が狭まる。この問題で許容される誤差は10^-6なため、十分正確な範囲で求まると考えられる。


C問題

問題概要

 n頂点の木が与えられる。各頂点に色を塗っていく。頂点a, b, cが接続されているとき頂点a, b, cは異なる色で塗らなければならない。このとき最小の色数で塗り分ける方法を示せ。

解法

 頂点vの子を塗ることを考える。このとき、頂点vおよび頂点vの親の色では塗ることができない。これら以外の色で小さい数の色から順に塗っていくことで条件にあった塗り分けが可能である。木の根から各頂点に順番に深さ優先探索していくことで答えを求めることができる。