TCO 2011 Qualification Round 1

大敗...。

250

N人の集団に対して、この中に嘘つきは少なくとも何人いるか、という問いを行った結果が与えられるので、何人が嘘つきか答えよ、という問題。矛盾するときはその旨答える。

K人の嘘つきがいるとすると、Kよりも大きい値を答えた人間がちょうどK人いないとおかしい。これを計算するだけ。ソートしてやると嘘つきとそうでない人との線引きができるが、実際にはちっとも楽にならないのでソートしない方がいい。

500

N個のものがあるので、重複を許してランダムに選択して並べるとき、長さLの位置にくる確率をそれぞれについて求めよ、という問題。長さがLに届かないような選択である確率は別途DPしておいて、届くときにそれぞれのものが選択される確率をかけてやればいいだけ。長さがKのときのそれぞれの確率でDPするとTLEするが、一番重たいループを回る回数が減った方が遅いので良く分からない...。

1000

AとBからなる文字列のprefixとsuffixが指定されている。文字列のスコアを、同じ文字が連続すると-1、違う文字が隣接していれば+1という風に求め、途中で負にならないように定義するとき、目的のスコアになる最短な文字列のうち辞書順で最初のものを答えよ、という問題。

条件分岐して書くだけ。ある程度は探索を入れて効率良くコードを書きましょうね、というだけのお話。基本はやるだけ。