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

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

この度 ABC366 に参加した結果パフォーマンスが 1000 を超えたので記念に振り返ります
結果としては 53 分ノーペナの4完でした。
https://atcoder.jp/contests/abc366/submissions?f.User=yoto1980yen
E問題は見た感じ難しそうだったので早々にドロップアウトしちゃいました

A - Election 2 100点

内容としてはある時点で高橋氏に T 票、青木氏に A 票入っており、残りの票がどのような結果であったとしても結果が確定しているか判定する問題

解き方

残り票である N - (T + A) が T と A の差分を超えているかどうかを判定します
注意点としてはどちらのほうが票数が多いかは決まっていないので絶対値で判定することくらいですね
n - (t + a) < (t-a).abs

ソースコード

def main
    n, t, a = intary
    if n - (t + a) < (t-a).abs
        puts "Yes"
    else
        puts "No"
    end
end

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

B - Vertical Writing 200点

問題文がわかりづらく解くのに時間がかかりました
複数の文章を縦に並べ i 文字目ごとに抜き出し文章を作成するもの
文章ごとに長さが異なっており i 文字目までない場合は代わりに * を入れる必要がある

解き方

難しく考えてしまいました
各文字列 i 文字目を取得し答え用のリストに格納していきます
該当文字が nil の場合は * を代わりに入れる
またこれまでに文字を取得していない場合は該当文字が nil の場合でも * を入れないように工夫しました

もっと簡単な解き方としてはとりあえず文字を入れていって
もう一度ループを回し初めに * の場合だったら消す対応をしたほうがよさそうに思いました

ソースコード

def main
    n = int
    s = []
    max = 0
    n.times do |i|
        ss = strary
        s << ss
        max = [max, ss.size].max
    end
    ans = []
    max.times do |i|
        ans << []
        judge = false
        s.each do |j|
            if j[i] == nil && judge == false
            elsif j[i] == nil
                ans[i] << "*"
            else
                ans[i] << j[i]
                judge = true
            end
        end
    end
    ans.each do |i|
        puts i.reverse.join("")
    end
end

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

def strary
    gets.chomp.split("")
end
main

C - Balls and Bag Query 300点

よく見るクエリ問題ですね
袋の中に整数が書かれたボールを入れたり取り出したりしてその時の袋内のボールの種類数を答えるもの

解き方

種類数を答える際にループして数えると TLE になるので工夫する必要があります
Hash でボールの数を管理し Hash の Key が増えた場合(新たな整数のボールを入れたとき)や 0 個だったものが増えた場合などは種類数を +1 する
取り出すときに 0 個になった場合は種類数を -1 する事でわざわざ毎回種類数を数えなくて済みます

ソースコード

def main
    q = int
    map = {}
    syurui = 0
    q.times do |i|
        t, x = intary
        if t == 3
            puts syurui
        elsif t == 1
            if map[x] != nil
                map[x] += 1
                if map[x] == 1
                    syurui += 1
                end
            else map[x] = 1
                syurui += 1
            end
        elsif t == 2
            map[x] -= 1
            if map[x] == 0
                syurui -= 1
            end
        end
    end
end

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

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

D - Cuboid Sum Query 400点

ちょっと前から 2 次元累積和を履修していたのですがやっと本番で使う時が来ました
まず範囲が N * N * N の 3 次元の配列が与えられる
Q 個のクエリが与えられ、指定の範囲の配列の数字を加算したものを出力するもの

解き方

問題文通りに解く場合は 3 次元累積和を使う必要がありかなり難しいのでと思いました( X を見た感じそんな悲鳴を多数見た)
しかし,とらえ方次第で 2 次元累積和で解くことができます
というのも Lx から Rx まで範囲で y と z の2次元累積和を使えば O(NQ) で解けます
​計算量は 100 * 2 * (10 ** 5) = 2 * (10 ** 7) となり TLE になりそうですがこの問題の実行時間制限は 3 秒のため問題はないです(だから 400 点なのか？)

ソースコード

def main
    n = int
    a = []
    n.times do |i|
        a << []
        n.times do |j|
            a[i] << intary
        end
    end
    s = Array.new(n + 1) {Array.new(n + 1) { Array.new(n + 1, 0) }}
    n.times do |k|
        (0...n).each do |i|
            (0...n).each do |j|
                s[k][i + 1][j + 1] = s[k][i][j + 1] + s[k][i + 1][j] - s[k][i][j] + a[k][i][j]
            end
        end
    end
    q = int
    q.times do |i|
        ans = 0
        lx, rx, ly, ry, lz, rz = intary
        (lx..rx).each do |j|
            ans += s[j - 1][ry][rz] - s[j - 1][ly - 1][rz] - s[j - 1][ry][lz - 1] + s[j - 1][ly - 1][lz - 1]
        end
        puts ans
    end
end

#----------------------------------------------------------------------------------
def int
    gets.chomp.to_i
end

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

main