Ruby と Python で解く AtCoder ABC243 D

はじめに

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

今回のお題

今回のテーマ、ビット演算

この問題は、扱う数値が大きいので計算が大変そうに見えます。
しかし、数値（10進数）を2進数で表しよく見ると．．．

• S の i 番目の文字が U のとき、今いる頂点の親に移動する
  -> 2進数の右側の文字を除去
• S の i 番目の文字が L のとき、今いる頂点の左の子に移動する
  -> 2進数の右側に0を追加
• S の i 番目の文字が R のとき、今いる頂点の右の子に移動する
  -> 2進数の右側に1を追加

即ち、右側に文字を出し入れしているだけの操作になります。

Ruby

n, x = gets.split.map(&:to_i)
s = gets.chomp.chars
y = x.to_s(2).chars

n.times do |i|
  case s[i]
  when 'U'
    y.pop if y.size > 1
  when 'R'
    y << '1'
  when 'L'
    y << '0'
  end
end

puts y.join('').to_i(2)

10進数->2進数	2進数->10進数
xxxx.to_s(2)	'xxxx'.to_i(2)

Python

n, x = map(int, input().split())
s = input()
y = list(format(x, 'b'))

for i in range(n):
    if s[i] == 'U':
        if len(y) > 1:
            y.pop()
    elif s[i] == 'R':
        y.append('1')
    elif s[i] == 'L':
        y.append('0')

print(int(''.join(y), 2))

10進数->2進数	2進数->10進数
format(xxxx, 'b')	int('xxxx', 2)

まとめ

タネを知ってしまえばなんてことない問題ですが、コンテスト中は大変ですよね。