ABC125に参加しました
はじめに
結果はABDの3完でした
C問題が難しくてTLEが取れませんでした
Twitter見てると累積和の応用で解けるらしいのでその辺をよく勉強していなかったことが悔やまれます
以下僕の解法です
A問題
0.5のことは考えてやらなくてもいいです
[T/A] * Bで答えが出ます
B問題
V - C < 0の時は宝石を買っても損してしまうので選ばないと考えます
後は選んだやつを全部足してやればX - Yの最大値が得られます
inputの仕方を間違えないようにしましょう
C問題
問題を見てすぐに、「ははーん、書き換えるやつは他の入力された数字にすればいいから、結局抜いてしまえばいいわけだな」と思って意気揚々と考え始めましたが、考えても考えてもO(N^2)から小さくすることが出来ずTLE
解答はないです
すみません
累積和に関する知識が不足しているので勉強します
D問題
あるパネルをひっくり返すとそれに隣接するパネルもひっくり返るようなミニゲームしたことありませんか？
今回は正が表、負が裏と考えて、右隣のやつが連動すると考えて実験していくと、負の数または０が偶数個入力されたときは全ての値を正の数または０にすることが出来ます
また奇数個の場合はどれかが負の数または０を取るので絶対値が小さい奴を引いてやればいいです
結局解答は
偶数個の時
|A1|+|A2|+......+|An|
奇数個の時
|A1|+|A2|+......+|An| - 2 * min(|A1|, |A2|, ......,|An|)
となります
32bit整数型に収まらないこともあるらしいのでlong long型にしましょう
終わりに
緑パフォ、やったぜ。
初の時間中D問題ACでした、うれしい
最近は解ける問題が増えてきたので参加するのが楽しいです
今回の競技時間中、順位表から見てD問題をACしてる人の数がとても多く、問題文を見てみたら簡単だったので解きましたが、そもそもDも見ておく癖をつけておくべきだったと思います
今後の戦略に生かしていくことが多く見つかったABCでした
GW頑張って精進してゆきます
ここまで読んでいただきありがとうございました
