AtCoder Beginner Contest 125 の解説
久しぶりに全完したような気がしますが、酷いミスが多すぎて喜べません…考察はすぐに生えたのにミスを量産してしまいました。具体的には
C…forの範囲をi <= n にしていてWA。正しくは i < n。
D…総和 - 最小*2 の所を、総和 - 最小 にしてしまった。
です。いやこれで15分ロスしてるんですが…悲しい…ということで解説です
A
T/A*Bを出力すれば良いです。
B
問題文に「一つも選ばなくてもよいです」と書いてある。宝石を取るメリットがある時(Vi > Ciのとき)は取っていき、その総和を計算すればいいです。
C
i番目を選んで数字を好きなものに変えるとします。
その時、「i番目以外全ての数字の最大公約数」と同じ値にしてあげるのが一番いい手です。例えば 1 10 10 10 10 で、1番目の数字「1」を書き換える場合、他の4つの最大公約数の「10」に書き換えてあげると答えは10になります。
よく考えてみると「i番目を書き換える時の最大の値は、i番目を除いた全ての数字の最大公約数」ということが分かります。一つの数字だけ無視できる、みたいな感じになります。
なのでこの問題は、「どの数字を無視すれば、最大公約数が最大になるか」のような問題にもっていけます。
このように、点線の丸以外の全ての数字の最大公約数は、左部分と右部分に分けてgcd(左の部分, 右の部分)と計算することができます。配列の扱いに十分注意して下さい。
D
Dのほうが簡単だったかも…？
隣り合った二つのプラマイを反転させる時、
① +と-→-と+（左右が入れ替わる！）
② -と-→+と+（マイナスを消した）
というふうなパターンに分けることができます。
- - + + - + のようなものは、①のパターンを使いまくることで右に寄せることができます。
②番を使うことでマイナスを消していけますが、一度に消せるのは2つずつなので、マイナスの数が
・偶数…全てプラスにできる
・奇数…ひとつだけマイナスになってしまう
という風になります。①番を使いまくれば一番被害が少ない数字（絶対値が一番小さい数字）をマイナスにすることで、最大値にすることができます。
はい。急いで書いたのでクオリティが低いです。すいません。
