A. Biscuit Generator

切り捨てをする． 解答例

$k$回生産できるとすると$k$は$Ak \le T$を満たす最大の整数．$k \le T/A$と変形すると切り捨てだと分かりやすい気がする．

B. Resale

制約が小さいので全探索してしまった．$2^{20}$は$10^6$程度なので間に合う． 解答例

実際は価値＞コストでさえあれば手に入れてしまって損しないから，そのようにすればよい．AtCoderのOCamlは古いのでmap2が使えず1CE． 解答例

C. GCD on Blackboard

過去問演習 (No Need) の経験が生きた：理解できなくて記事に書けなかった累積和版の解答をおぼろげに覚えていたおかげで速答できた（添字の凡ミスで1WA）． 解答例

制約から$O(N)$くらいで解きたいので，とりあえず配列の中身を順番に見る方向で考える．ひとまず$i$番目を書き換えるか否かですべて試す方針を思いついた．しかしこの場合，$i$番目以外の全整数のgcdが得られなければならない． 毎回愚直に計算すると$O(N \times N \log max \{A\})$掛かり間に合わないため工夫が必要．

これは最初に右方向と左方向にそれぞれ累積gcdを取っておけばよい（それぞれ配列$LR,RL$とする）．すると$i$番目より左の整数のgcdは$LR[i-1]$，右は$RL[i+1]$で得られる．これは構築に$O(N \log max \{A\})$，取得に$O(1)$しか掛からないから，全$i$についての試行に掛かる時間計算量は$O(N)$となり間に合う．

gcdの計算量は$O($小さいほうの桁数$)$，すなわち$O(\log \min \{p,q\})$．

別解: Segment Tree

1位の方がSegment Treeを使っていたので真似してみた．確かにintに対する$\gcd$には単位元$0$が存在するし，結合則$\gcd(\gcd(a,b),c) = \gcd(a,\gcd(b,c))$が成立するからモノイドである．今回は更新はしないが，それでも$[l,r]$に対する演算結果を取れるので便利． 解答例

現在のSegment Treeの実装はOCamlとして汚い上にかなり遅いのでこれも何とかしたい．

D. Flipping Signs

このような隣り合う2つをひっくり返すような問題は何度か見たことがあったので経験が生きた． 解答例

editorialにあるように添字$i=l,...,r$について操作を行えば$a[l],a[r]$の符号だけを反転可能であるから，これを繰り返すことで「添字を2つ選んでそこの符号を反転させる操作ができる」と見做せる．したがって負数が偶数個であればすべてを正にできる．奇数個であれば1つの整数は負のままとなるが，負にする整数は絶対値が最小なものを選ぶのが最適なのでそのようにする（負にするにはペア(現在負の整数, 負にしたい整数)に対して先の操作を行えばよい）．

別解: 動的計画法 (editorial)

$i$番目を負にするか正にするか選ぶときに$i-1$番目以前の状態自体には関心が無い（和だけあればよい）から，和が最大な状態だけを選ぶことで状態を纏めることができる． 解答例

まず前に操作をしたときとそれ以外とでそれぞれ別のdp配列$dpp, dpn$を用意することが必要（名前はpositiveとnegativeの意味）．このとき$dpn[0]$はあり得ないことに注意^[1]．

遷移を考える．まず操作をしないとき，すなわち$dpp[i]$について考える．前に操作をしていなかった場合はそのまま$a[i]$を加算することになるから，$dpp[i-1]+a[i]$．前に操作をしていた場合は「操作をした場合のdp配列」である$dpn$から$a[i]$を引くことになる：$dpn[i-1]-a[i]$．これらの最大値を採用すればよい．

つぎに操作をする場合，すなわち$dpn[i]$の更新について考える．前に操作をしていなかった場合は$a[i]$は反転していないから，反転は計1回であり$dpp[i-1]-a[i]$．前にも操作をしていた場合は$a[i]$は一度反転しているから再度反転させることになり，翻って元のままの$a[i]$となる：$dpn[i-1]+a[i]$．

---

1. 値を極端に小さくしてそのような場合が採用されないようにすればよい．min_int (AtCoderなどの64bit環境では$-2^{62}$)とすると何か引かれたときに負方向にオーバーフローして極端に大きくなってしまうため，$-2^{60}$などを採用するべき．和の最大および最小値は$\pm 10^9 \times 10^5 = \pm 10^{14}$でしかないからここから出た結果が$0$を超えることも負方向にオーバーフローすることもない． ↩︎