読者です 読者をやめる 読者になる 読者になる

小池イーサンだお(^O^)/

読んでーーーー

AtCoder Beginner Contest 046を解いたよーーーー(^O^)/

AtCoder Beginner Contest 046

AtCoder Beginner Contest 046 - AtCoder Beginner Contest 046 | AtCoder
昨日はやまぁに遊びに誘われたから参加できず( ;∀;)
リアルタイムで参加することにこだわってないから別にええやんな(*‘ω‘ *)

イーサンはrubyで解いたよーーーー(^O^)/
いつもC,D問題は時間内に解けないor自力で解けないみたいなレベルです( ;∀;)

A問題

A: AtCoDeerくんとペンキ / AtCoDeer and Paint Cans - AtCoder Beginner Contest 046 | AtCoder
a,b,cを重複の許さない集合に放り込んで大きさを返すだけ。
javaとかpythonだとsetに.addして.sizeで済むけど、
rubyではsetがないから配列に入れた上で.uniqして.lengthしないといけない。

puts gets.split.uniq.length
結果

AC

B問題

B: AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer - AtCoder Beginner Contest 046 | AtCoder
ひとつ左隣のボールの色以外で塗っていけば、
結果的に右隣のボールの色とも違う色になる。
なので、左隣との関係だけ気にすればよい。
左端のボールの塗り方はK通り
それ以降のボールの塗り方は左隣の色を除いた(K-1)通り
なので、求めたい組み合わせは
K^1*(K-1)^(N-1)

N, K = gets.split.map(&:to_i)
puts K*((K-1)**(N-1))
結果

AC

C問題

C: AtCoDeerくんと選挙速報 / AtCoDeer and Election Report - AtCoder Beginner Contest 046 | AtCoder
「現時点での票数の比(a:b)」=「表示された票数の比(c:d)」となればうれしいので、
内項の積と外項の積を比較して、等しくなるように票数(a,b)を1ずつ足し込んでいけば
答えは出るなぁ。

a=b=1
gets.to_i.times do
  c,d=gets.split.map(&:to_i)
  until (a*d==b*c)
  	if(a*d<b*c)
  		a+=1
  	elsif (a*d>b*c)
  		b+=1
  	end
  end
end
p a+b

結果

TLE

てことで紙とペンでウンウン唸りながら考える(*・ω・)(*-ω-)(*・ω・)(*-ω-)ウンウン♪

票数は比の数値の整数倍になればよい。何倍にするかを考えないといけない。
現在の票数(t,a)と比の数値(Ti,Ai)の大小を比較して考えると、
t<Tiならt=Ti
t>Tiならt=(整数倍)*Ti
にすればいい感じがする。
(整数倍)=(t/Tiを切り上げた値)にすればいいかな。([t/Ti])
となると、t<Tiのとき[t/Ti]は1になるから大小を比較する必要がなかった。
なのでt=[t/Ti]*Tiとすればいい。
a,Aiについても同様に考えて、
a=[a/Ai]*Aiとすればいい。
で、比を保つためには[t/Ti]と[a/Ai]は同じ値じゃないといけない。
しかも、大きいほうを選ぶ必要がある(小さいほうを選ぶと票数を減らさないといけなくなる)
なので、
t=max([t/Ti],[a/Ai])*Ti
a=max([t/Ti],[a/Ai])*Ai
切り上げは.ceilだったな。
よし、書こう。
票数(a,b)、比(c,d)として読み込む。
商は小数でほしいから.map(&:to_f)で読み込まないとアカンかな?

a=b=1
gets.to_i.times do
  c,d=gets.split.map(&:to_f)
  a=[a/c,b/d].max.ceil*c
  b=[a/c,b/d].max.ceil*d
end
p (a+b).to_i
結果

WA

ファッ!?テストケースの半分くらいWAやんけ。

.map(&:to_f)が怪しいので有理数で読み込んでみよう(.map(&:to_r))

a=b=1
gets.to_i.times do
  c,d=gets.split.map(&:to_r)
  a=[a/c,b/d].max.ceil*c
  b=[a/c,b/d].max.ceil*d
end
p (a+b).to_i
結果

AC

D問題

D: AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper - AtCoder Beginner Contest 046 | AtCoder
わけわかんななぁ。わかったことを書き出してみよう。
1回目は各プレイヤーはgしか出せない。(絶対にあいこ)
2回目以降gかpが出せる。(出せる手はgかpの2通り)
相手と同じ手を出し続ければあいこなので0点未満になることはない。
(gの数)≦N
(pの数)=N-(gの数)≦N/2.floor(切り捨て)

わからん。よし、愚直に書いてしまおう。
ひと文字ずつ読み込む。
相手が何を出してきても、なるべくpを出したい。
でも(pの数)≦(gの数)にしないといけない。
pが出せなかったら仕方ないからgを出す。
gとpの数、勝ち数(win)負け数(lose)を足しこんで、
win-loseを出力すればいい。

g,p,win,lose=0,0,0,0
gets.chomp.chars.each do |c|
    case c
    when 'g'
        if(g > p)
            p += 1
            win += 1
        else
            g += 1
        end
    when 'p'
        if(g > p)
            p += 1
        else
            g += 1
            lose += 1
        end
    end
end
p (win - lose)
結果

AC

初心者が解いてみた感想

A問題は簡単
B問題も簡単
C問題は答えを出すだけならすぐできるけど、
ACにするのはかなり考えないとだめ。
D問題はなにも考えずに愚直にやったら通ってしまった(これでいいなら簡単)

リアルタイムでやったらABDが解けて、Cは諦めていただろうなって感じです。

おわり(*‘ω‘ *)