「 2018年07月 」一覧

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