n-knuu's logs

憧れ駆動。だいたい競プロ

SnackDown Online Qualifier 2016

SnackDown Online Qualifier 2016にe-monさんと出ました。
1問解けば次に進めますが、僕とe-monさんで2問ずつ解きました。

Kitchen Timetable

僕が解いた。

  • 問題

各人が料理を始めるタイムテーブルA_1, ..., A_N(A_1 < A_2 < ... < A_N)と、料理の完成にかかる時間B_1, ..., B_Nが与えられる。ある人が料理を始めてから、次の人が始めるまでに料理が終わらない場合は、途中で打ち切られ、次の人が料理を始める。
最後まで完成できる人は何人か?

  • 解法

Aから料理できる時間を計算してBと比較するだけ。O(N)

  • コード


Better Maximal Sum(MMSUM)

e-monさんが解いた

  • 問題

数列Aから1つだけ要素を取り除けるときの、Aの最大の部分連続列の和を求めよ。

  • 解法

{S[i], E[i]}を、{iで始まる, iで終わる}最大の部分連続列の和とすると、答えは、max{max{E[i], E[i-1]+S[i+1]} for i in 1 to N}で求められる。
{S[i], E[i]}に関しては、数列Aを{後ろから, 前から}見ていって、{S[i]=max(A[i], S[i+1] + A[i], E[i+1]=max(A[i+1], E[i]+A[i+1])}と更新していくことで、O(N)で求められる。

  • コード


K-good Words

  • 問題

アルファベット小文字の列Sが与えられる。各文字種x_1, ..., x_nごとに数を数えたとき、任意の文字種x_i, x_jに対して、abs(S.count(x_i) - S.count(x_j)) <= Kが成り立つとき、SはK-goodな単語であるとする。SとKが与えられたとき、Sから文字をいくつか削除してK-goodにしたいとき、最小何文字削除すればよいか?

  • 解法

文字種ごとのカウント数の列をソートしたものをc_1, c_2, ..., c_nとする。このときの答えは、あるc_iを決めたときにc_1, ..., c_(i-1)に対応する文字列を全て削除し、j > i かつ c_j - c_i > Kとなるc_jを全てc_i + K以下にした場合の削除した文字数が最小になるときの削除した文字数である。今回はnが26以下なので、O(n^2)などで容易に求められるが、尺取り法でO(n)でも求められる。
結局はO(|S| + n log(n) + n)

  • コード