AtCoder: ABC124

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

シェアする

  • このエントリーをはてなブックマークに追加

フォローする