「 2018年09月 」一覧

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とたどることになります。

まず、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

結果

Dで凡ミスで一度WAを食らってしまいましたがとりあえず全部解けました。

今回はABC単独開催だったので、Dもそれほど難しくなかったからだと思います。

とりあえず順調にいけば次回あたりで水色は達成できそうな見込みです。

そろそろARCにもチャレンジしようかな。


AtCoder BC108 C: Triangular Relationship

問題

https://beta.atcoder.jp/contests/abc108/tasks/arc102_a

解法

a+b、b+c、c+aが全てkで割り切れると言うことは、

$$(a+b)\%k=(b+c)\%k=(c+a)\%k=0$$

ということです。

ここで、aに着目した場合、以下の2通りが考えられます・

・aがkで割り切れる場合
 (a+b)%k=0よりbもkで割り切れることになり、さらにcもkで割り切れることになります。
 つまり、a、b、cが全てkで割り切れる場合に条件を満たすことになります。

・aがkで割り切れない場合
 例えばa%k=1の場合、b%k=k-1となり、c%k=1となります。
 その場合、(c+a)%k=0となるにはkが2である必要があります。

 次にa%k=2の場合、b%k=k-2となり、c%k=2となります。
 その場合、(c+a)%k=0となるにはkが4である必要があります。

 つまり、kが偶数の場合は、a%k=b%k=c%k=k/2 の場合に条件を満たすことが分かります。

よって、aが偶数の場合と奇数の場合でそれぞれ個数が変わります。

実装

n,k=gets.chomp.split.map(&:to_i)
puts k%2==0 ? (n/k)**3 + ((n-k/2)/k+1)**3 : (n/k)**3