読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 175/176/177

yukicoder

初めてのyukicoder参加。
176で詰まり結果1問どまりです。
177を先にやればよかった。

175 simpleDNA

- 問題概要

A,Bを好きなだけ使ってL文字の解のうち、指定された終端3文字を含む文字列は何文字あるか答えよ。

- 解法

指定された終端3文字の種類をNとすると、
i文字目に考えうる文字はA,Bの2通りなのでN*(1<<(L-3))が解です。

176 2種類の切手

- 問題概要

整数A,B,Tが与えられる。
AとBを好きなだけ足し合わせてできるT以上の値の最小値を求めよ。

- 解法

大きい方がBになるようスワップする。
Bが0個、1個、、、T/B+1個の場合について条件を満たす最小のAの個数を求めて最小値を求めればよい。
が、Bの値がとても小さいときに痛い目を見る。
そこで、AとBの最小公倍数について考える。
解をCとすると、
C=k*lcm(A,B)+a*A+b*Bと表せる。
このとき,kの満たす条件はk*lcm(A,B) \le T \le Cである。
さらに、lcm(A,B)/B > b,lcm(A,B)/A > aが成り立つ。
したがって、k *lcm(A,B) \le T < (k+2)*lcm(A,B))が成り立つ。
これを満たす最小のkが求まれば探索範囲はT-lcm(A,B)*kとしてかなり狭まる。
0 \le \frac{T}{lcm(A,B)}-k \le 2
\frac{T}{lcm(A,B)}-k ={0 or 1 or 2}
k = min(\frac{T}{lcm(A,B}-{0 or 1 or 2})=\frac{T}{lcm(A,B)}-2
kが求まりました。
AとBでTができるかを求める問題をAとBで2*lcm(A,B)を置き換えることができます。
これであとはBの個数を全通り試せば計算量はO(\sqrt{T})となります。

177 制作進行の宮森あおいです!

- 問題概要

W枚の原稿を仕上げたい。
N人の原画マンはそれぞれ仕上げることのできる原稿の上限枚数がある。
同様に、M人の作画監督(原画をチェックする人)の担当できる原稿にも上限枚数がある。
ただし相性の悪い作画監督原画マンの組み合わせが存在するため、どの原稿をどの原画マンに任せどの作画監督に回せばいいか考えなくてはならない。
W枚仕上げることができるかどうか答えよ。

- 解法

グラフに落とすことで最大フローに帰着できます。
始点の宮森、終点の宮森を作る。
始点の宮森から各原画マンに担当できる上限枚数の重みの辺を引っ張る。
同様に終点の宮森へ各作画監督の担当できる上限枚数の重みの辺を引っ張る。
これで宮森以外の人が上限枚数を超えて担当することはなくなる。
次に全ての原画マンから全ての作画監督へ無限大の重みの辺を引っ張る。
ここでは、原画マンから作画監督へ渡す量が10000を超えることはないため10000でよい。
最後に、相性の悪い組み合わせの辺の重みを0にする。
あとはBFSを使って最大フローを求めるだけです。
計算量はO(WNM)