AtCoder BC102 D: Equal Cut

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_b

解法

長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせはn-1C3通りあります。Nは最大2×105であるため、全ての組み合わせを試すのは現実的ではありません。

「P、Q、R、Sの最大値と最小値の差の絶対値が最小になる」は言い換えると、「P、Q、R、Sの大きさが出来るだけ近い場合」ということです。最適なのは、数列の総和の1/4になる場合ですが、実際にはなるべく1/4に近い値を目指すことになります。

ここで数列の三つの切れ目をi1、i2、i3とおきます。

そしてi2を固定した場合を考えます。

この時、PとQ、RとSの差が最小になる切れ目がi1とi3であったとします。

次に、i2を右に一つずらす場合を考えます。

この時、i1とi3は「そのまま」か「右にずれる」ことになります。(つまり単調増加)

そして、PとQ、RとSの差が最小になる新しいi1とi3に更新していきます。

このような処理をi1=0、i2=1、i2=3を初期状態として繰り返しながら、「P、Q、R、Sの最大値と最小値の差の絶対値が最小」になる値を求めることで解けます。

なお、配列の部分和については、累積和を事前に求めておくことで定数時間で計算できますので、全体としてはO(N)で解くことが出来ます。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

# aa = 累積和
aa = [a[0]]
1.upto(n-1) do |i|
    aa << aa[-1] + a[i]
end

i1 = 0
i2 = 1
i3 = 2

ans = 10 ** 9

while(i2 < n-2) do
    while i1 < i2 - 1 do
        if (aa[i1] - (aa[i2] - aa[i1])).abs > (aa[i1+1] - (aa[i2] - aa[i1+1])).abs
            i1 += 1
        else
            break
        end
    end

    while i3 < n - 2 do
        if (aa[n-1] - aa[i3] - (aa[i3] - aa[i2])).abs > (aa[n-1] - aa[i3+1] - (aa[i3+1] - aa[i2])).abs
            i3 += 1
        else
            break
        end
    end
    pqrs = [aa[i1], aa[i2] - aa[i1], aa[i3] - aa[i2], aa[n-1] - aa[i3]]

    ans = (pqrs.max - pqrs.min) if ans > (pqrs.max - pqrs.min)


    i2 += 1
end

puts ans

AtCoder BC102 C: Linear Approximation

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

解法

以下の数式の値を最小にするbをどのようにして求めるかという問題です。

$$
abs(A_1-(b+1)) + abs(A_2-(b+1)) + … + abs(A_N-(b+1))
$$

これは、Bi = Ai – 1 とすると

$$
abs(B_1-b) + abs(B_2-b) + … + abs(B_N-b)
$$

と書き換えることがが出来ます。

これが最小になるのは、数列Bの中央値をbとした場合です。

図にしてみるとよく分かります。
(見やすくするためにBはソート済みとしています)

Nが奇数の場合、bがB3より大きく(小さく)なるとその分合計値が増加します。

Nが偶数の場合、B2〜B3の間から外れると、その分合計値は大きくなります。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

0.upto(n-1) do |i|
    a[i] -= (i+1)
end
a.sort!

m = a[n/2]

ans = 0
0.upto(n-1) do |i|
    ans += (a[i] - m).abs
end

puts ans

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

AtCoder BC103 D: Islands War

問題

https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

解法

最初に(ai, bi)の組み合わせについて、a→bの順番でソートします。

そして、ソート後の組み合わせについて、昇順に橋を落とす範囲を求めていきます。

その場合、i番目とi+1番目について、以下の4つのケースが考えられます。

ケース1の場合、i番目の条件が達成できればi+1番目は必ず達成されるので、i+1番目は無視することが出来ます。

ケース2の場合、i+1番目の条件を達成することでi番目が達成できるので、落とす橋の範囲を(ai+1, bi+1)に更新して次に進みます。

ケース3の場合、落とす橋の範囲を(ai+1, bi)に更新して次に進みます。

ケース4の場合、重なる部分が無いため、落とす橋の数を1増やし、落とす橋の範囲を(ai+1, bi+1)に更新して次に進みます。

このようにして、橋を落とす範囲を移動させながら、落とす橋の数を数えていくことで求まります。

実装

n, m = gets.chomp.split.map(&:to_i)
ab = []
m.times do
    ab << gets.chomp.split.map(&:to_i)
end

ab.sort! {|a, b| (a[0] <=> b[0]).nonzero? || (a[1] <=> b[1])}

a = ab[0][0]
b = ab[0][1]
ans = 1
for i in 1..(m-1) do
    if a <= ab[i][0] && ab[i][1] <= b
        a = ab[i][0]
        b = ab[i][1]
    elsif ab[i][0] < b && b <= ab[i][1]
        a = ab[i][0]
    elsif b <= ab[i][0] 
        ans += 1
        a = ab[i][0]
        b = ab[i][1]        
    end
end
puts ans

AtCoder BC103 C: Modulo Summation

問題

https://beta.atcoder.jp/contests/abc103/tasks/abc103_c

解法

m mod ai が最大になるのは、mがaiの倍数-1の時で、余りはai-1になる。

よって、mがa1,a2,,,anの最小公倍数-1の時にf(m)は最大になる。

最大値を求めるだけなら最小公倍数自体は求める必要は無く、ai-1の総和を求めれば良い。

(最初、mを求める問題かと思い、最小公倍数を求めるコードを書いてしまって時間ロス。。。)

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

ans = 0
a.each do |v|
    ans += v - 1
end
puts ans


AtCoder GC020 A: Digit Sum 2

問題

https://beta.atcoder.jp/contests/agc020/tasks/agc020_a

解法

各自がとるべき戦略を考えるにあたり、まずはどのような状態で勝敗が確定するかを考えます。

勝敗が確定するのは、以下のように片方が端っこに追いやられた状態で、次のターンがまわってくる場合です。

この状態でAliceが次のターンだとAliceの負けになります。

さらにこの1ターン前の状態、2ターン前の状態を考えると以下のようになります。

このように1ターン前の状態をたどっていくと、「隣接した状態になると次のターンの人の負けが確定する」ことがわかります。

次に初期状態でのAliceとBorysの間のマスの数について考えます。

AliceとBorysの間のマスの数が1であれば、最初にBorys側に移動すれば隣接状態となるためAliceの確定します。

AliceとBorysの間のマスの数が2の場合、AliceがBorys側に移動すれば次のターンでBorysが隣接してくるとAliceの負けが確定します。よって、Borysと反対側に移動することになり間のマスの数は3になります。そうすると、BorysはAlice側に移動してくるので、再び間のマスの数は2に戻ります。これを繰り返すことになるため、最終的にAliceは端っこに追い詰められて負けてしまいます。よって、Aliceは必ず負けます。

AliceとBorysの間のマスの数が3の場合、最初にAliceがBorys側に移動すると、AliceとBorysの間のマスの数は2になります。これは上記の「AliceとBorysの間のマスの数が2の場合」の逆になるため、今度はBorysが必ず負けます。

上記のように初期状態の両者の間のマスの数を考えていくと、

間のマスの数が奇数の場合、Aliceの勝ち
間のマスの数が偶数の場合、Borysの勝ち

であることがわかります。

実装

n,a,b = gets.chomp.split.map(&:to_i)
puts (b-a)%2==0 ? "Alice" : "Borys"

AtCoder BC098 C: Attention

問題

https://abc098.contest.atcoder.jp/tasks/arc098_a

解法

ある人をリーダーに選んだ場合、

西から東に向きを変える人の数 = 選んだ人より西の人の内、西を向いている人の数
東から西に向きを変える人の数 = 選んだ人より東の人の内、東を向いている人の数

となります。

よって、上記を数え上げる配列を最初に作成し、それぞれの和が最小となるものを求めれば解にになります。

例2の場合、上記の配列は以下のようになり、上下の配列の和の最小値は4となります。

実装

n = gets.chomp.to_i
s = gets.chomp.split("")

w, e = [], []
ww, ee = 0, 0
s.each do |c|
    w << ww
    if c == 'W'
        ww += 1
    end
end

s.reverse.each do |c|
    e << ee
    if c == 'E'
        ee += 1
    end
end

e.reverse!

ans = 10 ** 6
for i in 0..(n-1) do
    ans = (w[i] + e[i]) if ans > (w[i] + e[i])
end
puts ans

AtCoder BC098 B: Cut and Count

問題

https://abc098.contest.atcoder.jp/tasks/abc098_b

解法

文字列のサイズが最大でも100なので、全ての切断箇所のパターンで「どちらにも含まれる文字」の種類を数え上げれば解けます。

Rubyの場合、配列の「&」をとると共通部分が求められるので、実装は以下のようになります。

実装

n = gets.chomp.to_i
s = gets.chomp.split("")
ans = 0
1.upto(n-1) do |i|
    tmp = (s.slice(0,i) & s.slice(i,n-i)).size
    ans = tmp if tmp > ans
end
puts ans