2012-01-03から1日間の記事一覧

TopCoder SRM 386 DIv1 Easy CandidateKeys

問題 tableの列はattributeと呼ばれる。 行はentryと呼ばれる。 attributeの部分集合で、どのentryのペアについても、そのattributeのentryのうち異なるものが少なくとも一つあるものをsuper keyと呼ぶ。 super keyのうち、他のsuper keyを部分集合として含…

TopCoder SRM 387 DIv1 Medium IntervalSubsets

問題 n個の区間が与えられる。 それぞれの開始はstart[i]であり、終了はfinish[i]である。 この区間から、次の条件を満たす部分集合を選びたい。 部分集合に属する、どの二つの異なる区間も交わっていない(共通部分を持たない) 部分集合に属さない区間を、…

TopCoder SRM 387 Div1 Easy MarblesRegroupingEasy

問題 n個の箱にそれぞれi種類目のマーブルがboxes[i][j]個入っている。 何度か操作を繰り返して、次の状態を満たすようにしたい。 一つのjoker boxを決める。 joker box以外の箱は、空であるか一種類のマーブルしか入っていない。 一種類のマーブルは、joker…

TopCoder SRM 388 Div1 Medium InformFriends

問題 N人の友達がいる。 N人のそれぞれが互いに友達であるかはfriends[]により与えられる。 友達に噂を出来るだけ多くの個数だけ伝えたい。 一人の友達につき、伝えられる噂の数は1つだけである。 噂を聞いた友達は、自分の友達にだけその噂を伝える(その友…

TopCoder SRM 389 Div1 Easy

問題 ある整数の素因数が全てk以下であるとき、その数はk-smoothであるという。 与えられた整数N以下の正の整数のうちk-smoothであるものの数を求めよ。 制約条件 N≦200000 k≦200000

TopCoder SRM 389 Div1 Medium GuitarChords

問題 音階には12種類があり、それぞれの名前は、 A, A#, B, C, C#, D, D#, E, F, F#, G, G# である。 G#の一つ上の音はAである。12の倍数個だけ離れた音は同じ音階である。 今、何も抑えないとそれぞれstrings[i]の音がなるギターがある。 これを、フレット…

TopCoder SRM 390 Div1 Medium PaintingBoards

問題 板が一列に並んでいて、それぞれの長さはboardLength[i]である。 何人かがこの板に色を塗る。 それぞれの人が一秒間に塗る板の長さはpainterSpeed[i]である。 それぞれの人は、一枚または連続する何枚かの板を担当することができる。 全ての板の色を塗…