Codechef May Challenge 2018 参加日記
久しぶりのプロコンは今回からDiv1/2に分かれたCodechef。Div1で344位/633人の結果だった。ていうかDiv2でいいのに・・・。
サイズMの配列A、Bと整数Nが与えられる。次の最終resultを、10^9+7でModして答えよ。
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
1 <= M <= 10^5
1 <= N <= 10^5
いくつか列挙するとパターンが見える。たとえば
A = [ a, b, c ]
B = [ d, e, f ]
だとすると、iが1のときは
a, d, (a+d), (a+2d), (2a+3d), (3a+5d), (5a+8d), ...
a, e, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
a, f, (a+e), (a+2e), (2a+3e), (3a+5e), (5a+ 8e), ...
のようになる。つまりAの各要素xについて
x * fib(n-3) * m
が最終回答になり、同様にBの各要素yについては
y * fib(n-2) * m
が回答になる。これを足し合わせればよい。（N<=2のときは別途計算）
https://www.codechef.com/viewsolution/18432901
要素がDistinctな整数列Aが与えられる。Aの要素Xがについて、次のサーチアルゴリズムで正しいXの位置が求められるようにするためには、最小で何回、要素を交換することが必要か。なお数列Aは１つのみだが、クエリはQ回問われる。
integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid
正しい二分探索経路上で、Xの左と右それぞれについて、
左：Xより大きいもの
右：Xより小さいもの
が交換しなけらばならない要素とわかる。まずこの左右から交換するべきなので、最終回答に左と右の差を加える。
その次に余ったもの（左もしくは右にあるもの）を、有効な要素と交換していけばよい。
有効な候補の有無は、あらかじめAをソートしておけばLowerBound/UpperBoundで効率よく探すことができる。
https://www.codechef.com/viewsolution/18435496
整数列Aの任意の要素に-1を掛けることができるとき、連続する長さ2以上の部分列が、必ず合計1以上になるようにしたい。最終的な数列の要素の合計を最小化せよ。
本番ではDFS+枝刈りで部分点だった。
よく考えると、ある要素iに注目しているとき、条件が成立するのは
・i-2が正、i-1が正
・i-2が負、i-1が正
・i-2が正、i-1が負
のパターンしかない。上からそれぞれdp_a, dp_b, dp_cとすると
dp_a[i] = min (dp_a[i-1], dp_b[i-1]) + A[i]
dp_b[i] = dp_c[i - 1] + A[i] (A[i] > A[i-1]のとき)
dp_c[i] = min (dp_a[i-1], dp_b[i-1]) - A[i] (A[i-1] > A[i] + A[i-2]のとき）
dp_c[i] = dp_a[i-1] - A[i] (a[i] + a[i-2] >= A[i-1] > A[i] のとき)
と式を立てることができる。
※参考実装
https://www.codechef.com/viewsolution/18500660
