【ABC370】ABC370をRubyで解いた振り返り【AtCoder】

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

この度 ABC370 に参加した結果パフォーマンスが 1100 を超えたので記念に振り返ります
今回の成績としては 77 分ノーペナの ABCD 4 完でした
4 完できている人がそもそも少ないのかパフォーマンスが 1157 もでてレートが 900 を超えました！

うれしかったので次の日には美味いすし屋に行きました

ちなみに D 問題解いて気持ちよくなったので E 問題以降は見ていません

提出結果

A - Raise Both Hands 100点

高橋君が右手と左手を上げるか下げるか行うのでそれに応じた出力をする問題

解き方

if 文で場合分けするだけで解けます
注意点としては左手を上げたからと言って Yes になるとは限らないので if 文の条件は右手と左手の両方を見るようにします

ソースコード

def main
    l, r = intary
    if l == 1 && r == 0
        puts "Yes"
    elsif l == 0 && r == 1
        puts "No"
    else
        puts "Invalid"
    end
end

#----------------------------------------------------------------------------------
require "set"
def intary
    gets.chomp.split(" ").map(&:to_i)
end
main

B - Binary Alchemy 200点

問題文がわかりづらく解くのに時間がかかりました
元素が1からNまで合成していき最終的にどの元素になるか求める問題
いわゆる配列を参照しまくる問題です

解き方

単純に N 回合成するだけでは解けません
以下の条件を忘れてしまうとエラーになるケースが発生してしまうので対応する必要があります

• 元素 i と元素 j を合成すると i ≥ j のとき元素 Ai,jに、i < j のとき元素 Aj,i に変化します

実際にこの条件を見逃してしまい解くのに少し時間がかかりました

ソースコード

def main
    n = int
    map = []
    n.times do |i|
        map << intary
    end
    element = 1
    n.times do |i|
        element_2 = i + 1
        element_2, element = element, element_2 if element > element_2 # 元素 i と元素 j を合成すると i ≥ j のとき元素 Ai,jに、i < j のとき元素 Aj,i に変化する対応
        element = map[element_2 - 1][element - 1]
    end
    puts element
end

#----------------------------------------------------------------------------------
require "set"
def int
    gets.chomp.to_i
end

def intary
    gets.chomp.split(" ").map(&:to_i)
end
main

C - Word Ladder 300点

問題の意図が分かりづらいので要約すると
S の文字列を T の文字列になるように 1 文字ずつ書き換えて T と同じになるようにする問題
書き換えるたびにSの文字列を記録しておき出力する必要があります

注意点として書き換えるたびに、前までに書き換えた時点の S の文字列より辞書順で大きくなる必要があります
例えば S = "aazz", T = "zzaa" だとします
1 回目に 1 文字目を更新し 2 回目に 4 文字目を更新する場合
1 回目の S は "zazz" になり 2 回目の S は "zaza" になります
これだと 1 回目の "zazz" より 2 回目時点の "zaza" の方が辞書順では小さいので WA になってしまいます
いかにして S の文字列を辞書順で小さい順に書き換えていけるかを考える問題です

解き方

まずは先頭から 1 文字ずつ見比べていき T の文字の方が辞書順で小さい場合のみ書き換えます
書き換えることで元の S の文字列より辞書順で小さくなります
そのため、より辞書順でできるだけ小さくなるように上の桁から書き換えていきます

次に最後から 1 文字ずつ見比べていき T の文字の方が辞書順で大きい場合のみ書き換えます
書き換えることで元の S の文字列より辞書順で大きくなります
そのため、辞書順でできるだけ大きくならないように下の桁から書き換えていきます

文字で説明されても理解は難しいと思いますので入力例 3 を見れば理解しやすくなると思います

ソースコード

def main
    s = strary
    t = strary
    x = []
    # 先頭から 1 文字ずつ見比べていき T の文字の方が辞書順で小さい場合のみ書き換える
    s.size.times do |i|
        if s[i] > t[i]
            s[i] = t[i]
            x << s.join("")
        end
    end

    s.reverse! # Sの文字列を反転する
    t.reverse! # Tの文字列を反転する
    # 最後から 1 文字ずつ見比べていき T の文字の方が辞書順で大きい場合のみ書き換える
    s.size.times do |i|
        if s[i] < t[i]
            s[i] = t[i]
            x << s.reverse.join("")
        end
    end

    # 出力する
    puts x.size
    x.each do |i|
        puts i
    end
end

#----------------------------------------------------------------------------------
require "set"
def strary
    gets.chomp.split("")
end

main

D - Cross Explosion 400点

H * W のグリッド上全てに壁があります
Q 回 (R, C) の位置に爆弾を置き、壁をどんどん壊していく
爆弾を置いた場所に壁がある場合はその壁を破壊され、なかった場合は最も近くにある上下左右の壁が破壊されます
Q 回の爆弾で壁を破壊して最終的に残った壁の数をこたえる問題です

解き方

まず単純な2次元配列だと上下の壁を壊すことが困難なため縦と横それぞれで壁の状態を記録する配列を作ります
制約的に H * W ≤ 4 * (10 ** 5) なので問題ありません
次に爆弾の最寄りにある上下左右の壁を探していきます
探索の方法として配列の先頭から探すような単純な探索をすると TLE になってしまうので二分探索で探していきます
二分探索で見つけたら該当の壁を縦横それぞれの配列から消していきます

ここでもう一点工夫する必要があるポイントです
先ほど縦と横それぞれで壁の状態を記録する配列を作ると書きました
しかし、壁の情報を配列で持たせてしまうと壁情報の削除時にかなり時間がかかってしまうので SortedSet で作成します
これにより配列から壁を消す際に実行時間がかからなくなります

ちなみに解説を見ましたがこれが想定解でした
しかし Ruby だと 3500ms かかってしまいあやうく TLE になるところでした
Rubyのような遅い言語でも通せるようにするためか実行制限時間が 4s で助りました！！！！

ソースコード

def main
    h, w, q = intary
    yoko = []
    tate = []

    # 横の行をすべてSortedSetで用意します
    h.times do |i|
        yoko << RBTree.new
        w.times do |j|
            yoko[i][j] = true
        end
    end

    # 縦の列をすべてSortedSetで用意します
    w.times do |i|
        tate << RBTree.new
        h.times do |j|
            tate[i][j] = true
        end
    end

    # 爆弾を設置していきます
    q.times do |i|
        r,c = intary
        #　設置された場所に壁がある場合
        if yoko[r - 1].lower_bound(c - 1) != nil && yoko[r - 1].lower_bound(c - 1).first == c - 1
            yoko[r - 1].delete(c - 1)
            tate[c - 1].delete(r - 1)
        # 設置された場所に壁がない場合
        else
            # 二分探索で設置された場所より最も近い左右の壁を探す
            yokor = yoko[r - 1].lower_bound(c - 1)
            yokol = yoko[r - 1].upper_bound(c - 1)
            # 右に壁が見つかった場合はSortedSetから削除する
            unless yokor == nil
                tate[yokor.first].delete(r - 1)
                yoko[r - 1].delete(yokor.first)
            end
            # 左に壁が見つかった場合はSortedSetから削除する
            unless yokol == nil
                tate[yokol.first].delete(r - 1)
                yoko[r - 1].delete(yokol.first)
            end
            
            # 二分探索で設置された場所より最も近い上下の壁を探す
            tater = tate[c - 1].lower_bound(r - 1)
            tatel = tate[c - 1].upper_bound(r - 1)
            # 上に壁が見つかった場合はSortedSetから削除する
            unless tatel == nil
                tate[c - 1].delete(tatel.first)
                yoko[tatel.first].delete(c - 1)
            end
            # 下に壁が見つかった場合はSortedSetから削除する
            unless tater == nil
                tate[c - 1].delete(tater.first)
                yoko[tater.first].delete(c - 1)
            end
        end
    end

    # すべての爆弾の処理が終わったら残っている壁の数を数える
    ans = 0
    yoko.each do |i|
        ans += i.size
    end
    puts ans
end

#----------------------------------------------------------------------------------
require "set"
require "rbtree"
def intary
    gets.chomp.split(" ").map(&:to_i)
end

main