AtCoder Beginner Contest 143

はじめに

Atcorder ABC143へ初参加。
結果は問A～問Cまでの3問のみ正答。
言語：ruby
Ver:Ruby 2.3.3
URL:https://atcoder.jp/contests/abc143/tasks

143-A（Curtain）

・この問題は窓の幅とカーテンの1辺のサイズ×2と比較する問題
※ただし、値がマイナスにならないよう注意

143-A.rb

A,B = gets.split(' ').map(&:to_i)
Num = A - B*2

if Num < 0
  Num = 0
end

p Num

143-B（TAKOYAKI FESTIVAL 2019）

・たこ焼きの組み合わせの選び方の問題
　1つ目のたこ焼きを限定して、2つ目のたこ焼きを選択

143-B.rb

N = gets.to_i
takoyaki = gets.split(' ').map(&:to_i)

taste_total = 0
a = 0

while a < N do
    taste = 0
    b = a + 1

    while b < N do
        taste = taste + takoyaki[a]*takoyaki[b] 
        b = b + 1
    end
    taste_total = taste_total + taste
    a = a + 1

end

puts taste_total

143-C（Slimes）

・隣接する文字列を判定する問題
・先頭から次の文字が同じかどうか比較し、異なるとスライムの総数を増加

143-C.rb

N = gets.to_i
slime = gets.chomp
slime_total = 0

slime.length.times do |num|
    if slime[num] != slime[num + 1]
        slime_total = slime_total + 1
    end
end

p slime_total

143-D（Triangles）

・解法を最適化する問題

1.すべての辺を1つずつ計算（ 計算時間がO(N^3) ）

※ 計算時間がかかりすぎるので改善

143-D.rb

N = gets.to_i
hen = gets.split(' ').map(&:to_i)
hen.sort!

triangle_total = 0
a = 0

while a < N - 2 do
    b = a + 1
    while b < N - 1 do 
        c = b + 1
        while c < N do
            if hen[a] + hen[b] > hen[c]
                triangle_total += 1
                c+= 1
            else 
                break
            end
        end
        b = b + 1
    end
    a = a + 1
end

p triangle_total

2.解放を改善（計算時間がO(N^2 log2)）

改善のポイント

1. 143-Bの考え方を応用する
2. 入力された数値がばらばらだと辺の大小関係が分かりにくい
3. 入力された内容を昇順にソートする
4. 三角形の成立条件は「最小の二辺が最大の辺より大きい」という条件に言い換えができる
   ・a < b + c
   ・b < c + a
   ・c < a + b
5. 最小の2辺を固定したうえで、最大の辺が条件を満たす組み合わせを考える
6. 最小の2辺（a + b）で残りの1辺がどの値まで条件を満たすか（> c）を考える
7. 1つずつ左から探索（線形探索）する場合は時間がかかる
8. 2分木のソート方法を用いて、a + b に近似する値を探索する
   https://qiita.com/ryosuketter/items/2798b09330e7102b6cfe

143-D-2.rb

N = gets.to_i
hen = gets.split(' ').map(&:to_i)
hen.sort!
 
triangle_total = 0
a = 0

# aの候補の最大要素は配列数の2個前
while a < N - 2 do
    b = a + 1

    # bの候補の最大要素は配列数の1個前
    while b < N - 1 do 
        check_num = hen[a] + hen[b]
        
        # a + b がソート対象の最小値以下の場合は三角形の成立条件を満たすものはなし
        if check_num <= hen[b + 1]

        # a + b がソート対象の最大値より大きい場合は全ての数値が三角形の成立条件を満たす
        elsif check_num > hen[N - 1]
            triangle_total = triangle_total + N - 1 - b
        
        # a + b がソート対象範囲内の数字 
        else
            # ソートの先頭と末尾を定義
            head = b + 1
            tail = N - 1

            # ソート対象の中央値より上か下かで範囲を絞る
            while head <= tail
                
                center = (head + tail) / 2   
                
                if hen[center] >= check_num
                    tail = center - 1
                
                elsif hen[center] < check_num
                    if check_num <= hen[center + 1] 
                        triangle_total = triangle_total + center - b
                        break
                    else 
                        head = center + 1
                    end
                end
            end
        end
        b = b + 1
    end
    a = a + 1
end

p triangle_total

3.Rubyのライブラリを使用して改善

・bsearch_indexを使用して、探索用の処理に書き換える
https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch_index.html

143-D-3.rb

N = gets.to_i
hen = gets.split(' ').map(&:to_i)
hen.sort!
 
triangle_total = 0
a = 0
 
while a < N - 2 do
    b = a + 1

    while b < N - 1 do 
        check_num = hen[a] + hen[b]
        
        if check_num <= hen[b + 1]
        elsif check_num > hen[N - 1]
            triangle_total = triangle_total + N - 1 - b
        else            
           c = hen.bsearch_index { |x|  x >= check_num }
           triangle_total = triangle_total + c - 1 - b
        end
        b = b + 1
    end
    a = a + 1
end
 
p triangle_total