A – Buttons
問題
解法
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
問題
解法
海が見えるのは、「自分より西側の山の高さが全て自分以下の時」なので、その時点の最大の高さを保持しながら西の山から順に見ていき、
・これまでの最大の高さ以上の時:解を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
問題
解法
黒白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
問題
解法
ある一定の区間の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
コメント