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

n-knuu's logs

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

SRM540 div.1 250 ImportantSequence

topcoder

久しぶりに練習会に参加して、1完だった

問題

数列A = [a_1, a_2, ..., a_n]に対して、+と-のどちらかを間に挿入し、数列 B = [a_1 op_1 a_2, a_2 op_2 a_3, ..., a_(n-1) op_(n-1) a_n]とする。
(例) A = [1, 7, 5, 3]で、op = [-, +, +]とするとB = [-6, 12, 8]となる。
Aの各要素が正の整数であるとして、opとBが与えられたときに、もとの数列Aは何通りありうるか?(無数にある場合は-1と答えよ)

制約

Bの要素数は50以下

  • 10^9 <= B_i <= 10^9

解法

a_1 = kと置くと、a_2, ..., a_nはkを使って表せる。
例えば、上の例のopとBだと、A = [k, k+6, 6-k, k+2]と表せる。
ここでAの各要素は位置以上でないとダメなので、a_i >= 1という形のkに関する連立一次不等式を解けばよい。

具体的な計算方法は、kの符号と式A_iの定数項cと、kの下限lbと上限ubを持っておき(初期値はそれぞれ、kの符号は正、c=0、lb=1、ub=INF)
op[i]が+なら、符号を反転しc=B[i]-c
op[i]が-なら、符号はそのままでc=c-B[i]
として、
符号が正ならlb=max(lb, 1-c)、負ならub=min(ub, c-1)とする。(これは連立不等式を解いた形からわかる)

最後まで計算して、ubがINFなら答えは無数にあるので-1、lb > ubなら答えは0、それ以外は答えはub-lb+1となる。
上限は計算途中で2^31を超えることがあるので注意*1

計算量

O(|B|)

コード


感想

連立一次不等式を解く問題は以前にもあったので覚えていた

*1:pythonを使う場合は特に気にしなくて大丈夫だけど