れんしゅうちょう。

■ Problem C. Candy Splitting 23:32

問題

かなり好みな問題。

問題はかなりすらすら読めた。Bから逃げてきた自分には嬉しい。

足し算出来ないのに二進?とか思ったら繰り上がり出来ないとか見えたので、xorだなーとか考えて、例っぽいのをirbで試してみたら合ってた。

去年に引き続きbitの問題うひひひとか思ってた。

a xor b = c ⇔ a xor c = b

を考慮して、とりあえず全部のxor求めといて、後で弟にやる分xorすればそれぞれの山の(弟が考える)合計が求まるなーとか考えた。

泣かない判定めんどいなーと思ったら、それぞれの山の合計A,Bが同じ⇔AxorB=0なので、全部のxorが0かどうか考えればいいだけ。

全部のxorが0ならどう分けてもふた山の合計は等しくなるので、一番小さいのだけ弟にあげればよいという事に気付く。

geti
c=getia.sort
a = c.inject(&:^)
unless a.zero?
    "NO"
else
    c.inject(&:+)-c[0]
end

入力は問題文読みながら書いてたので、sortまで書いてあった。

c.inject(&:+)-c.minにすればO(n)になるけど、O(NlogN)でも余裕なのでそのまま提出。smallをAC→そのままlarge投げてDへ。

しかし、Sean鬼畜すぎてPatrick涙目すぎる。

ツイートする