全完で通過。
しかしAとBのsmallを1ミスするというふがいなさ。
以下、各問題での思考の推移と駄コード。
コード類はテンプレ除いてあります。
各ケースについての処理を書いてる感じです。
OrangeとBlueのロボットがなんか動くから、シミュレーションせよと。
問題文は比較的読めた。
各要求に対して、1回で更新しようとしてバグらせて、sampleが通らない状況に。
一度頭を冷やす為、Bへ行く。
その後Bで詰み、C→Dを経て帰ってくる。
ボタンが100までしか無い事に気付き、毎秒でシミュレートする事にしたら、10分で解けた。
と思いきや、smallでWA.
更新処理を何か修正してsmallをAC→そのままlargeも提出。
q = gets.split(" ") n = q.shift.to_i seq=[] for i in 0...n seq.push [q[i*2],q[i*2+1].to_i] end posO=1 posB=1 seqO=seq.find_all{|a|a[0]=="O"}.map{|a|a[1]} seqB=seq.find_all{|a|a[0]=="B"}.map{|a|a[1]} res = 0 until seq.empty? res += 1 flg = false if !seqO.empty? if posO < seqO[0] posO += 1 elsif posO > seqO[0] posO -= 1 elsif seq[0][0] == "O" flg = true seq.shift seqO.shift end end if !seqB.empty? if posB < seqB[0] posB += 1 elsif posB > seqB[0] posB -= 1 elsif seq[0][0] == "B" && !flg seq.shift seqB.shift end end end res
ifとunlessが混在していてなんかアレですね。
ついでに、posO <=> seqO[0]とかを使えば格好良かった気がします。
まぁバグの温床になりそうですが。
あと、OrangeのOとゼロが見にくくて死ねばいいと思いましたまる。
Redとかにして下さいよ、Google先生･･･
一瞬まどまぎかと思ったのは自分だけでは無いハズ。
問題を理解するのに異常に手間取った。
Aを解けずにBに来たので、泣きそうになった。
英語だと、三文くらい読むと前に書いてあった事を忘れるので、
与えられるのがelement listではなくて、与えられたのを生成してelement listに入れていくという事を忘れていた。
どういう順番でcombine、opposedしていくのか解らず、sampleの#3が解らないという状況に。
何回か書いてアレー?となって、頭を冷やす為にCへ行って、D→Aを経て戻ってくる。
結局ただ左から順にpushして処理すればいいだけだという事に気付き、なんとか書いて提出。
smallでWAをもらい、何か直して提出。smallでACってそのままlargeも投げた。
input = gets.split(" ") comb = [] opp = [] inv = "" input.shift.to_i.times do comb.push input.shift end input.shift.to_i.times do opp.push input.shift end comb.map!{|a|[a,[a[1],a[0],a[2]].join]}.flatten! opp.map!{|a|[a,[a[1],a[0]].join]}.flatten! inv = input.shift.split("") unless input.shift.to_i.zero? res = [] until inv.empty? res.push inv.shift unless res.size < 2 i = comb.index{|x|x[0..1]==res[-2..-1].join("")} unless i.nil? res.pop res.pop res.push comb[i][2] next end res = [] if opp.any?{|x|x[1]==res[-1] && res.any?{|y|y==x[0]}} end end "["+res.join(", ")+"]"
combもoppも、順不同なので、最初から両方の順番を突っ込んでおくと楽。
ex:"QFT"→"QFT","FQT"
かなり好みな問題。
問題はかなりすらすら読めた。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涙目すぎる。
"Algorithms are not Goro's strength; strength is Goro's strength."
駄洒落かよ･･･
問題文は比較的読みやすかった。
明らかに既に揃っている所は固定した方が良いのと、ランダムに並べ替えるという事で、あるべき場所でない個数kを用いて、E(k)と表せるだろうと考える。
サンプル見てたら、E(k)=k (k=2,4)が解る。
E(3)は手動で解いたら3だった。
E(k)=kっぽいなーと思いつつsampleの下を読むと、4の時は2つずつ押さえるとか書いてあって、自分が想定していた
「常に"あるべき場所"のだけ全部固定、それ以外をシャッフル」
が正しくないかもしれないと思いつつE(4)をその手法で計算すると4に。
E(5)を漸化式立てながら計算すると、5になる。
漸化式が見えたので、E(k)=kを仮定して変形しまくると、次が成立すれば良い事が解る。
ここで、a_kはモンモール数です。
とりあえずこれを用いて100程度まで正しい事を確認してみました。
$a=[] def a(n) return $a[n] unless $a[n].nil? return 1 if n.zero? return 0 if n == 1 return 1 if n == 2 return $a[n] = (n-1) * (a(n-1) + a(n-2)) end def C(n,k) res = 1 for i in 0...k res *= n-i res /= i+1 end res end def factorial(n) return 1 if n.zero? return n*factorial(n-1) end def f(n) res = 0 for k in 0...n res += (n-k) * C(n,k) * a(k) end res end for n in 1..100 p n unless f(n)==factorial(n) end
何も表示されないので正しいようです。
という事で、解答は
geti
getia.each.with_index.map{|x,i|x==i+1?0:1}.inject(&:+)
smallをAC、largeもそのまま投げる。
直感的には、k箇所の間違えがあって、その部分をランダムに並べ替えたら、ある箇所に正しいのが来る確率は1/kくらい。よって、k*(1/k)=1個くらい揃うハズ。
これがどのkでも1個なので、大体k回くらいというのは正しげに見えます。
証明にはならない感じなので、正しい証明が見たい人はこれでも読んで下さい。
自分のチェック用途中生成物は、これ以上うまくまとまらなかった気がします(´・ω・｀)
GoroSortは流行りそうだなー。
次にBに、「出来た（ｷﾘｯ」 → アウトプット作り忘れてて 1 wrong try
まぁ慣れる意味も含めてのQRだろうし、この先やらかさなきゃいいんじゃないかなw