【ABC392】ABC392をRubyで解いた結果水パフォが出たので振り返ります【AtCoder】

ABC392 の参加しましたのでその感想を

この度 ABC392 に参加した結果パフォーマンスが水パフォ (1277) だったので記念に振り返ります
結果としては 70 分ノーペナの5完でした
E問題をコンテスト中に解いたのはこれが初めてだったので本当にうれしいです
https://atcoder.jp/contests/abc392/submissions?f.User=yoto1980yen

Unratedだったので嬉しさ半減
ライバル視している人たちはみんなE問題を解けてなかったので嬉しさ倍増

A - Shuffled Equation 100点

3 つの数字が与えられるので並び変えて A * B = C という形に作れるかという問題

解き方

制約を見ると 1 から 100 までなので掛けた答えが 3 つの数字のうち最も大きい数になることが約束されます
そのため与えられた数字をソートして昇順に A * B = C の形になるかを確認すれば解けます

ソースコード

a, b, c = gets.chomp.split(" ").map(&:to_i).sort # 入力を昇順にソート
if a * b == c
    puts "Yes"
else
    puts "No"
end

B - Who is Missing? 200点

1 から N までの数字のうち M の整数列に含まれないものを昇順で出力するもの

解き方

1 から N までループで回し M の整数列に含まれていたら解答に追加せず、含まれていなければ解答に追加していくだけ
ただ、今回自分は難しく考えており M をソートして先頭のものと一致していれば解答に含めず M の整数列から外す様に対応しました
一応これであれば M が 2 * 10 ** 5 個あっても解けるようになりますが今回の制約は 1000 個なので M の整数列に含まれるかで判断すればよかったです

ソースコード

n, m = gets.chomp.split(" ").map(&:to_i)
ans = []
a = gets.chomp.split(" ").map(&:to_i).sort # Mの整数列を昇順にソート
n.times do |i|
    if a.first == i + 1 # Mの整数列の先頭に一致する場合は答えに追加しない
        a.shift # Mの先頭の要素を除外する
    else # Mの整数列の先頭に一致しない場合は答えに追加する
        ans << i + 1
    end
end
# 答えを出力
puts ans.size
puts ans.join(" ")

C - Bib 300点

まず感想を言うと何を言っているのかわからない問題でした
i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を、i=1,2,…,N のそれぞれについて求めてください。
この文章を理解するのに5分かかりました

理解した後だとわかりますが連想配列を使って解く初歩的な問題でした
ゼッケンi を着ている人が見ている人をループで探すと TLE(Time Limit Exceeded) になってしまうので連想配列を使い実行時間を減らす必要があります

解き方

ゼッケン i を key に、ゼッケン i を着ている人が見ている人を valueとして連想配列を作成します
その後 1 から N までをkeyとして連想配列から value を取得し、得られたゼッケン (value) を着ている人を出力します
ここまで書いてて自分でも何を言っているのかわからなくなってますのでぜひ解いてみてください

ソースコード

n = gets.chomp.to_i
p = gets.chomp.split(" ").map(&:to_i)
q = gets.chomp.split(" ").map(&:to_i)
map = {}
n.times do |i| # 連想配列を作成
    map[q[i]] = p[i]
end
ans = []
n.times do |i| # ゼッケンを1からNまで着ている人が見ている人のゼッケンを答えに格納
    ans << q[map[i + 1] - 1]
end
puts ans.join(" ") # 答えを空白区切りで出力

D - Doubles 400点

100個のサイコロがあり、この内2つのサイコロを振り出目がそろう最も高い場合の確率を出力する問題
これを求めるには全パターン (100 C 2) を試す必要があり実行時間との勝負になりそうです

解き方

まずは実行時間の削減のためにサイコロの出目の値の持ち方を工夫する必要があります
面の数と各出目については分けて管理します
大事なのが出目の管理方法で key を出目、value をその出目の個数として連想配列を作成します
これにより特定の出目の個数を O(1) で取得出来ます

比べる対象のサイコロのうち 1 つのサイコロに含まれる出目の種類を Set に保存しておきます
もう 1 つのサイコロの出目が Set に含まれるか確認し含まれていたら list に格納しておきます
これで list には両方のサイコロに含まれる出目が格納されます
あとはこの出目ごとに揃う確率を計算し全て足すことでさいころの出目が揃う確率が求まります

list.each do |出目|
    ans += サイコロAの出目の個数 / サイコロAの面の数 * サイコロBの出目の個数 / サイコロBの面の数
end

これを全パターン試しもっとも確率が高いものを出力する事で解けます
これでも Ruby だと 1200 ms だったので結構ギリギリです

ソースコード

def main
    n = gets.chomp.to_i
    dice = []
    size = []
    n.times do |i|
        k = gets.chomp.split(" ").map(&:to_i)
        size << k.shift # 面の数は別途管理する
        dice << grouping(k.sort) # keyを出目、valueをその出目の個数として連想配列で作成
    end
    ans = 0
    (0...n).each do |i|
        set = Set.new
        dice[i].each do |deme| # サイコロiの出目を Set に保存する
            set << deme.first
        end
        ((i+1)...n).each do |j|
            nowans = 0.to_f
            list = []
            dice[j].each do |deme|  # サイコロjの出目がサイコロiの出目に含まれていたら list に保存する
                list << deme.first if set.include?(deme.first)
            end
            list.each do |deme| # 出目ごとに出る確率を計算
                nowans += dice[i][deme].to_f / size[i].to_f * dice[j][deme].to_f / size[j].to_f
            end
            ans = [ans, nowans].max # 出目が揃う確率が高ければ答えを更新するする
        end
    end
    puts ans
end

def grouping(ary)
    a = ary.slice_when { |a, b| a != b }.to_a
    map = {}
    a.each do |i|
        map[i.first] = i.size
    end
    return map
end
main

E - Cables and Servers 450点

問題文を見た瞬間絶対UnionFindじゃんってなりました
自分でも行けるかもと思い解きました

閉話休題

N 個のサーバーがありM本のケーブルが繋がってます
ケーブルを繋ぎ変えてすべてのサーバー同士がケーブルを介して繋がるようにする問題
ただケーブルを繋ぎ変えるのではなく出来るだけ少ない回数で繋ぎ変える必要があります

解き方

UnionFind一択です
まずケーブルを連結して行きます
この際同じ親同士だった場合はスペアのケーブルとして保持しておき連結しません

次に親の種類を Set に用意しておき、スペアのケーブルをループで回し繋ぎ変えていきます

Set をループで回しケーブルの親ではない親を探します
異なる親を見つけたらケーブルを繋ぎ変え Set からつなげた親を削除します
これを Set の要素数が 1 (全ての親が同じ)になるまで繰り返すことで解けます

ソースコード

def main
    n, m = gets.chomp.split(" ").map(&:to_i)
    uf = UnionFind.new(n)
    spare = []
    m.times do |i| # M本のケーブルを連結する
        a,b = gets.chomp.split(" ").map(&:to_i)
        if uf.same_parent?(a - 1, b - 1) # 親が同じ場合はケーブルを連結する必要がないのでスペアにする
            spare << [i + 1, a,b]
        else # 親が異なる場合は連結する
            uf.unite(a - 1, b - 1)
        end
    end
    if uf.size == 1 # 全ての親が同じ場合はケーブルをつなぎ変える必要がないので終了
        puts 0
        return
    end
    set = Set.new(uf.parents) # 親の種類をSetに保存
    operate = []
    spare.each do |i|
        parent = uf.get_parent(i[1] - 1)
        set.each do |j| # 異なる親を探す
            unless uf.get_parent(j) == parent # 異なる親の場合は連結しSetから該当の親を削除し次のケーブルへ
                operate << [i[0], i[1], j + 1]
                uf.unite(i[1] - 1, j)
                set.delete(j)
                break
            end
        end
        break if set.size == 1 # 全ての親が同じ場合はケーブルをつなぎ変える必要がないので終了
    end
    # 行った繋ぎ変えの操作を出力
    puts operate.size
    operate.each do |i|
        puts i.join(" ")
    end
end
#----------------------------------------------------------------------------------
class UnionFind
    def initialize(size)
        @rank = Array.new(size, 0)
        @parent = Array.new(size, &:itself)
    end

    def unite(id_x, id_y)
        x_parent = get_parent(id_x)
        y_parent = get_parent(id_y)
        return if x_parent == y_parent
        if @rank[x_parent] > @rank[y_parent]
            @parent[y_parent] = x_parent
        else
            @parent[x_parent] = y_parent
            @rank[y_parent] += 1 if @rank[x_parent] == @rank[y_parent]
        end
    end

    def get_parent(id_x)
        @parent[id_x] == id_x ? id_x : (@parent[id_x] = get_parent(@parent[id_x]))
    end

    def same_parent?(id_x, id_y)
        get_parent(id_x) == get_parent(id_y)
    end

    def size
        @parent.map { |id_x| get_parent(id_x) }.uniq.size
    end

    def parents
        @parent.map { |id_x| get_parent(id_x) }.uniq
    end
end
main