A – Buttons
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
2個のボタンのサイズが等しい時は、A+Bが解。
等しくないときは、大きい方 x 2 – 1 が解。
実装
入力を読み取る際にソートして、B >= A にしておく。
A,B=gets.chomp.split.map(&:to_i).sort puts A==B ? 2*B : 2*B-1
B – Great Ocean View
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
海が見えるのは、「自分より西側の山の高さが全て自分以下の時」なので、その時点の最大の高さを保持しながら西の山から順に見ていき、
・これまでの最大の高さ以上の時：解を1増やす＆最大の高さを更新する
・これまでの最大の高さ未満の時：何もしない
というループをまわせば良い。
実装
N=gets.to_i
H=gets.chomp.split.map(&:to_i)
min=0
ans=0
H.each do |h|
if h >= min
ans += 1
min = h
end
end
puts ans
C – Coloring Colorfully
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
黒白2色しなかいので、隣り合うタイルが異なる色となるタイルの並べ方は以下の2通りしかない。
黒白黒白黒白黒白・・・・
白黒白黒白黒白黒・・・・
よって、両方のケースについて何枚塗り替える必要があるかをそれぞれカウントし、小さい方が解となる。
実装
S=gets.chomp.split("")
ans1,ans2=0,0
S.each_with_index do |s,i|
if i.even? && s=='0' || i.odd? && s=='1'
ans1+=1
end
if i.odd? && s=='0' || i.even? && s=='1'
ans2+=1
end
end
puts [ans1,ans2].min
D – Handstand
問題
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
ある一定の区間の0、1を反転させることを繰り返し、連続する1をどれだけ長く出来るか、という問題です。
基本的に1を反転させる意味は無いので、出来るだけ長い1の連続を作るには、1回の操作で連続する0の区間を反転させていけば良いことが分かります。
ここで、連続する0の区間がK個以下であれば、全てを1に出来るので解はNになります。
問題となるのは、連続する0の区間の数がKより多い場合です。
仮に連続する0の区間がL個だとすると、K個からL個選ぶことになるので、全探索だと間に合いそうに無いです。
そこで、次のように考えます。
なるべく1の連続を長くするには、反転させる連続する0の区間は連続していた方が良いです。
例えば、以下のような並びについてK=3で考えた場合、連続する0の区間は5カ所ですが、選び方は3通りしかありません。
よって、しゃくとり法などを使って前から順に見ていけば、O(N)で解くことが出来ます。
実装
N,K=gets.chomp.split.map(&:to_i)
S=gets.chomp.split("")
prev=S[0]
ss = []
ss << 0 if prev=='0'
cnt = 1
1.upto(N-1) do |i|
if prev == S[i]
cnt += 1
else
ss << cnt
prev = S[i]
cnt = 1
end
end
ss << cnt
ss << 0 if S[-1] == '0'
if ss.size/2 <= K
puts N
exit
end
tmp = 0
0.step(2*K) do |i|
tmp += ss[i]
end
ans = tmp
(2*K+1).step(ss.size-2,2) do |i|
tmp = tmp + ss[i] + ss[i+1] - ss[i-2*K-1] - ss[i-2*K]
ans = tmp if tmp > ans
end
puts ans