Ruby と Python で解く AtCoder Tenka1 Programmer Contest C 累積和

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

Tenka1 Programmer Contest C - Stones
Difficulty: 946

今回のテーマ、累積和

問題より最終的な石の並びは、すべてが白........、全てが黒########、もしくは左白右黒.....###のいずれかに変更します。
少々厄介なのは.#....#.#.の様なパターンで、左の.#.は...に、右の#.#.は####に変更するのが最小値となります。
そこで、左から右に.及び#の累積和を取り、その位置での変更個数を調べて最小値を求めます。

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

変則的ですが、累積和を取っています。

bw.rb

min = [a[-1][0], a[-1][1]].min

まずは、全部白にした場合と全部黒にした場合の個数を調べます。

tugi.rb

  min = a[-1][0] - a[i][0] + a[i][1] if min > a[-1][0] - a[i][0] + a[i][1]

次に、それぞれの位置で左白右黒に変更した場合の個数を調べます。

ord.rb

dot = '.'.ord

  if s[i] == dot

char値で比較した方が、若干速くなる様です。

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
コード長 (Byte)	457	631
実行時間 (ms)	175	186
メモリ (KB)	16208	30024

まとめ

• Tenka1 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった