Tenka1 Programmer Contest C - Stones Difficulty: 946
This theme, cumulative sum
From the problem, the final arrangement of stones is all white ........, all black ########, or left white right black..... # Change to one of ##.
A little annoying is a pattern like . # .... #. #., The left . #. Is ... and the right #. #. Is #### The minimum value is to change it to .
Therefore, take the cumulative sum of . and#from left to right, check the number of changes at that position, and find the minimum value.
Ruby
ruby.rb
n = gets.to_i
s = gets.chomp.bytes
dot = '.'.ord
a = Array.new(n){Array.new(2, 0)}
if s[0] == dot
a[0][0] = 1
else
a[0][1] = 1
end
1.upto(n - 1) do |i|
if s[i] == dot
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
end
end
min = [a[-1][0], a[-1][1]].min
n.times do |i|
min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]
end
puts min
rui.rb
1.upto(n - 1) do |i|
if s[i] == dot
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
end
end
It's anomalous, but it's a cumulative sum.
bw.rb
min = [a[-1][0], a[-1][1]].min
First, find out the number of cases when all are white and when all are black.
tugi.rb
min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]
Next, check the number when changing to left white right black at each position.
ord.rb
dot = '.'.ord
if s[i] == dot
It seems that it is a little faster to compare by char value. Python
python.py
from sys import stdin
def main():
input = stdin.readline
n = int(input())
s = input()
a = [[0, 0] for _ in range(n)]
if s[0] == '.':
a[0][0] = 1
else:
a[0][1] = 1
for i in range(1, n):
if s[i] == '.':
a[i][0] = a[i - 1][0] + 1
a[i][1] = a[i - 1][1]
else:
a[i][0] = a[i - 1][0]
a[i][1] = a[i - 1][1] + 1
min = a[-1][0] if a[-1][0] < a[-1][1] else a[-1][1]
for i in range(n):
if min > a[-1][0] - a[i][0] + a[i][1]:
min = a[-1][0] - a[i][0] + a[i][1]
print(min)
main()
| Ruby | Python | |
|---|---|---|
| Code length(Byte) | 457 | 631 |
| Execution time(ms) | 175 | 186 |
| memory(KB) | 16208 | 30024 |
Recommended Posts