RubyでAtCoder ABC291(A, B, C, D)を解いてみた

はじめに

Webエンジニアを目指して、RubyやRailsをいじってます。
今回は、RubyでAtCoder ABC291のA, B, C, Dを解きました。備忘録として解き方をまとめていきたいと思います。

A - camel Case

a-291.rb

s = gets.chomp.chars
arr = *"a".."z"
s.each_with_index do|i, j|
    unless arr.include?(i)
        puts j + 1
        exit
    end
end

<追記>
コメントでいただいた別解になります。正規表現を使った書き方で[A-Z]がAからZまでを列挙したもので、これを使って大文字があるかどうかを判定できるようです。

別解

s = gets.chomp
puts s.index(/[A-Z]/) + 1

解説

与えられた文字列に対して、先頭から調べていき大文字ならその時のindexを出力して終了します。

B - Trimmed Mean

b-291.rb

n = gets.to_i
x = gets.split.map(&:to_i).sort
n.times do
    x.shift
    x.pop
end
puts x.sum.to_f / (3 * n)

<追記>
コメントでいただいた別解になります。fdivメソッドは便利そう！

別解

n = gets.to_i
xs = gets.split.map(&:to_i).sort

puts xs[n...4 * n].sum.fdiv(3 * n)

解説

まず、与えられた集合xをsortしておきます。そして、xの先頭と末尾の要素を取り除くことをN回繰り返します。最後に、残ったxの集合の要素の平均値を出力すればOKです。なお、答えは浮動小数点型で計算する必要があります。

C - LRUD Instructions 2

c-291.rb

n = gets
s = gets.chomp.chars
x, y = 0, 0
hash = {[0, 0]=>true}

s.each do|i|
    if i == "R"
        x += 1
    elsif i == "L"
        x -= 1
    elsif i == "U"
        y += 1
    else
        y -= 1
    end

    if hash[[x, y]]
        puts "Yes"
        exit
    else
        hash[[x, y]] = true
    end
end
puts "No"

解説

まず、x, yをそれぞれ0で初期化し、高橋君が通った座標を記録する連想配列hashを用意します。そして、与えられた文字列に対してx, yを変更していき、すでに通っていればYesを出力して終了、そうでなければその座標をのvalueをtrueにします。逆に、最後までYesとなるような場合がなければNoを出力します。

D - Flip Cards

d-291.rb

n = gets.to_i
arr = Array.new(n){gets.split.map(&:to_i)}

dp = Array.new(n){[0, 0]}
dp[0] = [1, 1]
mod = 998244353
for i in 1..n - 1
    2.times do|pre|
        2.times do|nxt|
            dp[i][nxt] += dp[i - 1][pre] if arr[i - 1][pre] != arr[i][nxt]
        end
    end
    dp[i][0] %= mod
    dp[i][1] %= mod
end
puts (dp[n - 1][0] + dp[n - 1][1]) % mod

解説

（公式の解説を参考にしました）

<方針>
DP（動的計画法）を使い、dp[i][j]：i枚目の面がj（j=0なら表、j=1なら裏）でそれまでに条件を満たす枚数とします。

<実装方法>
まず、1枚目は表裏ともに1通りなのでdp[0]=[1,1]で初期化します。そこから順に条件を満たすなら１つ前の要素までの枚数を足していきます。そして、最後のカードの面のそれぞれの状態における条件を満たす枚数を足すことで答えを求めることができます。

終わりに

どういった時にDPを使うのかの見分けがまだつかないので、数をこなして慣れていきたいと思います！

参考