Ruby と比較しながら Bash で AtCoder に登録したら解くべき精選過去問 10 問を解いてみた

はじめに

シェルスクリプトに関わる可能性が出てきたのでやってみました。
ちなみに、AtcoderのBashの現行のバージョンは5.0.11で、次のコマンドで実行されます。

	bash ./Main.sh

他にも、dash(0.5.8)やzsh(5.4.2)で解くことができます。
Atcoder凄いぞ。

以下の、諸先輩の記事を参照させていただきました。

精選過去問 10 問

ruby

a = gets.to_i
b, c = gets.split.map(&:to_i)
s = gets.chomp
puts "#{a+b+c} #{s}"

bash

read a
read b c
read s
echo $(( a + b + c )) $s

readって便利ですね。

ruby

a, b = gets.split.map(&:to_i)
if a * b % 2 == 0
  puts "Even"
else
  puts "Odd"
end

bash

read a b
if (( (a * b) % 2 == 0 )); then
	echo "Even"
else
	echo "Odd"
fi

ruby

s = gets.chomp
puts s.gsub(/0/, '').size

bash

read s
t=${s//0/}
echo ${#t}

${対象文字列//置換前文字/置換後文字}で0を削除しています。
変数の代入で、=の前後にスペースがあるとエラーが発生します。
${#文字列}で文字列の長さを求めます。

ruby

n = gets.to_i
a = gets.split.map(&:to_i)
ans = 10000
n.times do |i|
  c = 0
  while a[i] % 2 == 0
    c += 1
    a[i] /= 2
  end
  ans = c if ans > c
end
puts ans

bash

read n
read -a a
ans=10000
for (( i = 0; i < n; i++ )); do
    c=0
    while (( a[i] % 2 == 0 )); do
    	c=$(( c + 1 ))
        a[i]=$(( a[i] / 2 ))    
    done
    if (( ans > c )); then
    	ans=$c
    fi
done
echo $ans

read -aって便利。

ruby

a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
ans = 0
(0..a).each do |i|
  (0..b).each do |j|
    if x < i * 500 + j * 100
      break
    elsif ((x - i * 500 - j * 100) % 50 == 0) && ((x - i * 500 - j * 100) / 50 <= c)
      ans += 1
    end
  end
end
puts ans

bash

read a
read b
read c
read x
ans=0
for (( i = 0; i <= a; i++ )); do
    for (( j = 0; j <= b; j++ )); do
        if (( x < (i * 500 + j * 100) )); then
            break
        elif (( ((x - i * 500 - j * 100) % 50 == 0) && ((x - i * 500 - j * 100) / 50 <= c) )); then
            ans=$(( ans + 1 ))
        fi
    done
done
echo $ans

ruby

n, a, b = gets.split.map(&:to_i)
ans = 0
(1..n).each do |x|
  y = x
  t = 0
  while y > 0
    t += y % 10
    y /= 10
  end
  if a <= t && t <= b
    ans += x
  end
end
puts ans

bash

read n a b
ans=0
for (( x = 0; x <= n; x++ )); do
    y=$x
    t=0
    while (( y > 0 )); do
        t=$(( t + y % 10 ))
    	y=$(( y / 10 ))
    done
    if (( a <= t && t <= b )); then
    	ans=$(( ans + x ))
 	fi
done
echo $ans

ruby

n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse
ans = 0
n.times do |i|
  if i % 2 == 0
    ans += a[i]
  else
    ans -= a[i]
  end
end
puts ans

bash

read n
read -a arr

loop=1;
k=0
while [ $loop -ne 0 ]; do
    ((loop=0))
    for ((i=0; i<${#arr[@]} - 1 - k; i++)); do
        if [ ${arr[i]} -lt ${arr[i + 1]} ]; then # -lt:降順 -gt:昇順
            ((tmp = arr[i]));
            ((arr[i] = arr[i + 1]));
            ((arr[i + 1] = tmp));
            ((loop = 1));
        fi
    done
    ((k++))
done

ans=0
for (( i = 0; i < n; i++ )); do
    if (( i % 2 == 0 )); then
        ans=$(( ans + arr[i] ))
    else
        ans=$(( ans - arr[i] ))
    fi
done
echo $ans

ソート部分はこちらを参照しました。

ruby

n = gets.to_i
d = Array.new(n){ gets.to_i }.sort
ans = 1
(n - 1).times do |i|
  if d[i + 1] > d[i]
    ans += 1
  end
end
puts ans

bash

func_sort () {
	loop=1;
	k=0
	while [ $loop -ne 0 ]; do
	    ((loop=0))
    	for ((i=0; i<${#arr[@]} - 1 - k; i++)); do
	        if [ ${arr[i]} -gt ${arr[i + 1]} ]; then
        	    ((tmp = arr[i]));
    	        ((arr[i] = arr[i + 1]));
	            ((arr[i + 1] = tmp));
            	((loop = 1));
        	fi
    	done
    	((k++))
	done
}

read n
for (( i = 0; i < n; i++ )); do
	read d
    arr[i]=$d
done
func_sort
ans=1
for (( i = 0; i < n - 1; i++ )); do
    if (( arr[i + 1] > arr[i] )); then
        ans=$(( ans + 1 ))
    fi
done
echo $ans

ソート部分を関数化しましたが、今は再利用できないです。

ruby

n, y = gets.split.map(&:to_i)
0.upto(y / 10000) do |a|
  0.upto(y / 5000) do |b|
    if a * 10000 + b * 5000 + (n - a - b) * 1000 == y && a + b <= n
      puts "#{a} #{b} #{n - a - b}"
      exit
    end
  end
end
puts "-1 -1 -1"

bash (TLE)

read n y
for (( a = 0; a <= y / 10000; a++ )); do
	for (( b = 0; b <= y / 5000; b++ )); do
		if (( a * 10000 + b * 5000 + (n - a - b) * 1000 == y && a + b <= n )); then
            echo $a $b $(( n - a - b ))
            exit 0
        fi
    done
done
echo "-1 -1 -1"

この解法ですと、BashはTLEします。
ここは文法の学習ですので．．．

ruby

s = gets.chomp
r = Regexp.new("^(dream|dreamer|erase|eraser)*$")
if r.match(s)
  puts "YES"
else
  puts "NO"
end

bash

read s
if [[ "$s" =~ ^(dream|dreamer|erase|eraser)+$ ]]; then
	echo "YES"
else
	echo "NO"
fi

みんな大好き正規表現。

ruby

n = gets.to_i
txys = Array.new(n){ gets.split.map(&:to_i) }
t0 = x0 = y0 = 0
txys.each do |txy|
  kd = (txy[1] - x0).abs + (txy[2] - y0).abs
  td = (txy[0] - t0).abs
  if kd > td || kd % 2 != td % 2
      puts "No"
      exit
  end
  t0 = txy[0]
  x0 = txy[1]
  y0 = txy[2]
end
puts "Yes"

bash (TLE)

read n
for (( i = 0; i < n; i++ )); do
	read t x y
    txys[$(( i * 3 ))]=$t
    txys[$(( i * 3 + 1 ))]=$x
    txys[$(( i * 3 + 2 ))]=$y
done
t0=0
x0=0
y0=0
for (( i = 0; i < n; i++ )); do
	t=${txys[$(( i * 3 ))]}
    x=${txys[$(( i * 3 + 1 ))]}
    y=${txys[$(( i * 3 + 2 ))]}
    if (( x > x0 )); then
    	kd=$(( x - x0 ))
    else
    	kd=$(( x0 - x ))
    fi
    if (( y > y0 )); then
    	kd=$(( kd + y - y0 ))
    else
    	kd=$(( kd + y0 - y ))
    fi
    if (( t > t0 )); then
    	td=$(( t - t0 ))
    else
    	td=$(( t0 - t ))
    fi
    if (( kd > td || kd % 2 != td % 2 )); then
    	echo "No"
        exit 0
    fi
    t0=$t
    x0=$x
    y0=$y
done
echo "Yes"

2次元配列を1次元配列にしてみましたが、TLE
ここは文法の学習ですので．．．

RubyってBashに似ているところが多いと感じました。

まとめ

• Bash に詳しくなった