Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 125

全完(ただし4WA)。

今の自分にいえることはただ一つ。

落 ち 着 け

各問題

A - Biscuit Generator

切り捨て除算で T / A をすると生産された回数がでるので、それに一回あたりの生産枚数 B をかければよいです。

(2019-06-03 追記) +0.5というのは、閉区間であることを擬似的に表しているんですね。最近知りました。罠じゃなかった。

T も A も整数なので 0.5 を足そうが足すまいが結果には影響しません。なので式にに含めなくてよいです。むしろ含めると、小数を扱わなければならなくなるため処理が面倒なことになります。

つまり、罠ですw

B - Resale

それぞれの宝石に対して、X - Y を計算して、結果が正のものだけを合算すればそれが答えです。

forとifの、いつものB問題ですけど、ほんのちょっと問題文読み解くのが難しかった気がします。(私だけ?)

C - GCD on Blackboard

最適解かどうかはわかりませんが、私の解法は以下の通り。

配列を2つ用意して、片方は1からN-1までの累積GCDを、もう片方にはNから2までの累積GCDを入れていきます。 つまり、9 6 3 4 6という列があったとして、A[0]には9と6のGCDである3を、A[1]にはA[0]と3のGCDである3を、というふうに累積和っぽく格納していきます。 で、2つの配列をうまく組み合わせると、1からNのうちひとつだけが除かれた状態のGCDが取れるので、それらのうちの最大のものがそのまま答えになります。

ただし、注意が必要なのはN=2のときはGCDを取るのではなくて、単にmax(A1, A2)が答えになるという点ですね。

https://atcoder.jp/contests/abc125/submissions/5156890

なお、私の4WAのほとんどは、単なるソースコードの編集ミスです・・・。on_ これで順位を160くらい落として泣きそうです・・・。

D - Flipping Signs

基本的に操作によって負数の偶奇は変化しないですが、うまく位置を取ると増やしたり減らしたりは自在にできます。 なので、最初の列に負数が奇数個なら、最終的に負数を1つにでき、絶対値が最小のものだけを負数としてほかは正数として合算します。 最初の列に負数が偶数個なら、すべてを正数として合算します。

ただし、0があると話が別で、0に-1を掛けても0なのでこれはマイナスを吸収してしまいます。ので・・・

と思っていたのですが、合計を出す時に「負数が奇数個なら絶対値が最小のものだけを負数として」扱うことにしました。しかし、0が含まれている列の場合、それは0です。なので足そうが引こうが結果が変わりません。 つまり、結局のところ0の有無は結果には影響しないのでした。無駄なロジックを書いてしまった・・・。

まとめ

今回DよりCのほうが難しかったですよね?(editorialによると、DはDPが想定解だったっぽい?)

つまらないミスで4WAも出してしまいましたが、結果は初の水色パフォ!! このまま水色になってしまいたい。

f:id:mdstoy:20190427230452p:plain

f:id:mdstoy:20190427230800p:plain