🔥

【AHC035】AHC035をRubyで解いたことを今更振り返る【AtCoder】

2024/08/12に公開

Ruby

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

やっと記事を書くモチベが上がったので AHC035 を振り返ります
結果としては 1023 人中 522 位でパフォーマンスは 1261 でした

問題の感想としてはこんな問題もあるんだなーっと
これまで参加した AHC はどのような動きをするかを考える問題でしたが今回の問題はどの様に種を選ぶか、自分で独自にパラメーターを設定して適切に配置するか考える問題でした

自分の点数は 224,906,022 点でトップは 274,272,291 点でした。そこまで大きな差はなくどのように種を選び置くかだけで結構変わるので面白かったですね

今回はビジュアライザ等でテストできなかった（ローカルに環境を用意していなかったので）のでもしローカルで試せていたらもっと点がよくなるように改善できたかもしれませんね

ではどのように解いたか振り返っていきます

A - Breed Improvement

6 * 6 の畑に 15 種のパラメーターを持つ種を植えて上下左右の種同士を交配し新たな種を作ります
これを 10 回繰り返し最高の価値を持つ(パラメータが最も高い)種を作る問題
交配して得られる種のパラメータは親である 2 種の種のパラメータからどちらかをランダムに引き継ぐため期待値が高くなるように種を植える必要があります

解き方

10 ターンの間種を置く配置は以下のような順番で評価の高い順に配置しました

考え方としては評価の高い種を出来るだけ評価の高い種同士で交配できるように中央に寄せて置くようにしました

さて、いかにして評価の高い順に種を選ぶかですが
以下の3つのパラメータで評価しました

平均値の高い順
最小値の低い順
最大値の高い順

ただ、それぞれのパラメータをそのまま評価にしたところで順位は上がりませんでした
そのため各パラメータに重みを付けました
平均値の高い順 8 : 最小値の低い順 1 : 最大値の高い順 9
試行錯誤で重みを変えてみましたがこれが本番中で見つけれたもっとも点が高くなる評価でした

ソースコード

def main
    n, m, t = intary
    t.times do
        seeds = []
        (2 * n * (n - 1)).times do
            seeds << intary
        end
        # 評価値の高い順に並べ替えたいぞい
        sum_sort = {}
        min_sort = {}
        max_sort = {}
        hyouka = {}
        # 平均値の高い順に設定
        seeds.each.with_index do |v, i|
            sum_sort[i] = v.sum
        end
        sum_sort.sort_by {|key, val| val}.each.with_index do |v, i|
            hyouka[v[0]] = i + i + i + i + i + i + i + i
        end
        # 最小値の低い順に設定
        seeds.each.with_index do |v, i|
            min_sort[i] = v.min
        end
        min_sort.sort_by {|key, val| val}.each.with_index do |v, i|
            hyouka[v[0]] += i
        end
        # 最台値の高い順に設定
        seeds.each.with_index do |v, i|
            max_sort[i] = v.max
        end
        max_sort.sort_by {|key, val| val}.each.with_index do |v, i|
            hyouka[v[0]] += i + i + i + i + i + i + i + i + i
        end
        hyouka = hyouka.sort_by{|key, val| val}.reverse
        
        put_list = Array.new(n) {Array.new(n, false)}
        
        #　真ん中から敷き詰める
        [[2,2], [3,2], [2,3], [3,3], [1,2], [1,3], [2,1], [3,1],[2,4], [3,4],[4,2],[4,3],[1,1],[1,4],[4,1],[4,4]].each do |i|
            put_list[i[0]][i[1]] = hyouka.shift.first
        end
        6.times do |i|
          6.times do |j|
            if put_list[i][j] == false
                put_list[i][j] = hyouka.shift.first
            end
          end
        end
        
        # 出力するぞい
        put_list.each do |i|
            puts i.join(" ") + "\n"
        end

        # リフレッシュしますよん
        STDOUT.flush
    end
end

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

GitHubで編集を提案

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

A - Breed Improvement

解き方

ソースコード

Discussion