AtCoder Beginner Contest 109 参戦記 - 銀の弾丸を探して

久しぶりにリアルタイムで参戦できたので結果のまとめです。

A - ABC333

問題

https://beta.atcoder.jp/contests/abc109/tasks/abc109_a

解法

A x B x C が奇数になりうるということは、少なくとも A x Bは奇数でなくてはいけません。また、Cは1 or 2 or 3なので、A x Bが奇数ならCが1 or 3なら成り立ちます。

よって、A x Bが偶数ならNo、奇数ならYesを出力すればOKです。

なお、Cが3通りしかないので愚直に組み合わせを試行しても良いですが、計算で解けるのはかなり明らかなのでその必要は無いかなと。

実装

a,b=gets.chomp.split.map(&:to_i)
puts a*b%2==0?"No":"Yes"

B - Shiritori

問題

https://beta.atcoder.jp/contests/abc109/tasks/abc109_b

解法

単語を読み取りながら、2つの条件にあっているかを逐次チェックしていけば良いです。

・その単語はまだ発言していない単語である　ハッシュを使って既出かどうかを確認します

・その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する　直前の単語の末尾と同じかどうかを判定します。

実装

n=gets.chomp.to_i
h = {}
prev = gets.chomp
h[prev] = 1
(n-1).times do
    w = gets.chomp
    if w[0] != prev[-1]
        puts "No"
        exit
    end
    if h.has_key?(w)
        puts "No"
        exit
    end
    prev = w
    h[prev] = 1
end
puts "Yes"

C - Skip

問題

https://beta.atcoder.jp/contests/abc109/tasks/abc109_c

解法

以下のようなケースを考えた場合、各地点をまわるためには X → x1 → x2 → x3とたどることになります。

f:id:taka_xyz:20181028194925p:plain

まず、X → x1 → x2について考えます。

x1とx2に訪れるためには、DがXとx1の距離とx1とx2の距離の公約数である必要があります。

さらに、最も効率的に＝最短回数で訪れるには、Dが最大公約数であれば良いことになります。

x3についても同様です。

つまり、Xと各xiの距離の最大公約数を求めることになります。

複数の値の最大公約数は、2つの値の最大公約数を求める処理を用意しておき、その結果と3つ目以降の値の最大公約数を順次求めていけば求まります。

実装

def gcd(a,b)
    while b > 0
        a,b = b,a%b
    end
    return a
end

n,x=gets.chomp.split.map(&:to_i)
xi=gets.chomp.split.map(&:to_i)
xi2 = xi.map{|v| (x-v).abs}
if n == 1
    puts xi2[0]
    exit
end

g = gcd(xi2[0],xi2[1])
2.upto(n-1) do |i|
    g=gcd(g,xi2[i])
end
puts g

D - Make Them Even

問題

https://beta.atcoder.jp/contests/abc109/tasks/abc109_d

解法

「偶数枚のコインが置かれたマスの数を最大化」するには、奇数のマスから奇数のマスにコインを移動することになります。

つまり、総コイン数が偶数であれば、全てのマスが偶数になりますし、奇数であれば1マス以外が偶数になります。

もう一つのポイントは、各マスにつき一度しかコインの操作が出来ない点です。

これを満たすためには、マス目を一筆書きでたどるようなルートでマス目をたどっていき、

・奇数のマスを見つけたら次の奇数のマス目までコインを移動する

という操作を繰り返していけば良いです。

なお、最短の操作数という制約はないので、どういう経路でマス目をたどるかは気にしなくて良いですね。

その制約があると、もっと難しかったと思います。（多分解けない。。。）

実装

添字の扱いがちょっとごちゃごちゃしてしまいました。

出力の最初に操作の数を出す必要があったため、最初に操作内容（どのマスからどのマスに移動するか）を配列に入れておき、最後に結果を出力するようにしました。

h,w=gets.chomp.split.map(&:to_i)
a = []
h.times do
    a << gets.chomp.split.map(&:to_i)
end

prev_i = -1
prev_j = -1

ans = []
0.upto(h-1) do |i|
    if i%2==0
        0.upto(w-1) do |j|
            if a[i][j] % 2 != 0
                if prev_i == - 1
                    prev_i = i
                    prev_j = j
                else
                    ans << [prev_i+1, prev_j+1, i+1, j+1]
                    prev_i = -1
                    prev_j = -1
                end
            end
        end
    else
        (w-1).downto(0) do |j|
            if a[i][j] % 2 != 0
                if prev_i == - 1
                    prev_i = i
                    prev_j = j
                else
                    ans << [prev_i+1, prev_j+1, i+1, j+1]
                    prev_i = -1
                    prev_j = -1
                end
            end
        end
    end
end

s = []
t = [] 

ans.each do |v|
    pi, pj, ti, tj = v

    while(pi != ti || pj != tj)
        s << [pi, pj]
        if pi == ti
            if pi % 2 != 0
                pj += 1
            else
                pj -= 1
            end
        else
            if pi %2 != 0
                if pj == w
                    pi += 1
                else
                    pj += 1
                end
            else
                if pj == 1
                    pi += 1
                else
                    pj -= 1
                end
            end
        end                        

        t << [pi, pj]
    end
end

puts s.size
0.upto(s.size-1) do |i|
    printf("%d %d %d %d\n", s[i][0],s[i][1],t[i][0],t[i][1])
end