【AHC055】結構簡単な方法で青パフォが取れたので振り返る(2週間遅れ)【AtCoder】
AHC055 に参加しましたのでその振り返りを
実は個人ごとですが AHC055 にて初めて青パフォーマンスが取れてうれしかったので振り返ります
ちなみに青パフォは1600からです
結果としては正解者 804 人中 273 位でパフォーマンスは 1614 でした
問題としても結構シンプルな問題で解きやすかったと思います
初心者におすすめ！
AHCではどういった動きをするのかWeb 版のビジュアライザで見れて面白いので AHC 始めたての人には良いと思います
自分の点数は 8,141,012 点でした
ではどのように解いたか振り返っていきます
A - Weakpoint
複数の宝箱があり各宝箱には武器が入っています
これらすべての宝箱を素手、または宝箱から入手できる武器を使って開けてねという問題
素手の攻撃力は最小の 1 しかないため、できる限り武器で攻撃して開けれるように工夫するのが大事です
しかし武器にも特徴があり宝箱の耐久値を減らせる攻撃力が異なり攻撃回数も1~6回までと異なります
解き方
1回目の解法 7,957,079 (最終順位だと449位)
始めに考えた方法としては"貪欲に行く"です
以下の考えで実装しました
- 素手で宝箱を攻撃する場合はできるだけ耐久値の低いものを攻撃する
- 武器を手に入れたらその武器が最も耐久力を減らせる宝箱を攻撃する
ちょっと工夫した点だと武器を使い宝箱を壊しても攻撃回数が残った場合にはそのまま使わず今後使えるように取っておくようにしました
後半になりこの武器が使いたいパターンもあると思ったので余ったら残すようにしました
実装イメージは以下です
while すべての宝箱の耐久値が0以下になるまでループ do
武器があれば最も耐久値を減らせる宝箱を攻撃 # 武器は取得順
宝箱を壊しても攻撃回数が余ったならweaponsの末尾に移動
武器がなければ素手で最も耐久値も低い宝箱を攻撃
end
これでも意外と点数が出て驚きました
2回目の解法 8,120,061 (最終順位だと291位)
1回目の解法では初めに最も耐久力が低い宝箱を壊す方法をとりましたが、初めの宝箱から取れる武器から今後壊す宝箱の順番が変わると思いました
そのためすべての宝箱で初めに壊すパターンをすべて試すことにしました
答えとしては最も攻撃回数が少ないパターンを出力するようにしています
実装イメージは以下です
best_score = Array.new(100000, 0) # 答えを定義しておく
各宝箱.each do |宝箱| # 始めに壊す宝箱ごとにループする
current_score = []
h[宝箱] = 0 # 初めに壊す宝箱の耐久値を0に更新
weapons = [[宝箱から出た武器, その武器の攻撃回数]] #初めに得られる武器を持っておく
# 1回目の処理と同じ
while すべての宝箱の耐久値が0以下になるまでループ do
武器があれば最も耐久値を減らせる宝箱を攻撃# 武器は取得順
宝箱を壊しても攻撃回数が余ったならweaponsの末尾に移動
武器がなければ素手で最も耐久値も低い宝箱を攻撃
end
# 今回の行動回数がこれまでのパターンより少なければ答えを更新
best_score = current_score if current_score.size <= best_score.size
end
全ての宝箱で初めに壊すパターンを試しただけで点数としては7,957,079から8,120,061まで大幅に上がりました
始めに壊す宝箱次第でどのように壊していくかは大きく変わるので絶対にやったほうが良い手法でした
3回目の解法 8,141,012 (最終順位だと273位)
より改善していくために考えた方法として武器で宝箱を攻撃する際にランダム性を持たせるようにしました
これまで武器を使って攻撃する場合は、最も耐久値を減らせる宝箱を選んでいた
これだと箱を壊す流れが 1 パターンになってしまいます
別の宝箱を壊したほうが後々良くなるパターンも考えられるため乱数で壊す壊さないの場合分けを行いました
会社の先輩とこの方法について話したとき焼きなまし法だと教えていただきました
今回の問題では壊す箱の順番次第で後半のパターンがどうなるか分かり難いため、焼きなまし法にも一定の効果がありそうでした
実装イメージは以下です
skip_thresholds = [0, 1, 10, 20, 30, 40] # 確率を定義
best_score = Array.new(100000, 0) # 答えを定義しておく
skip_thresholds.each do |skip_threshold| # 宝箱を壊す確率ごとにループする
各宝箱.each do |宝箱| # 始めに壊す宝箱ごとにループする
current_score = []
h[宝箱] = 0 # 初めに壊す宝箱の耐久値を0に更新
weapon = [[宝箱から出た武器, その武器の攻撃回数]] #初めに得られる武器を持っておく
while すべての宝箱の耐久値が0以下になるまでループ do
# 武器がある場合
# 耐久値を減らせる宝箱順にループする
treasure_box.each do |treasure|
next if skip_thresholdの確率より低い場合はスルーする
宝箱を攻撃
宝箱を壊しても攻撃回数が余ったならweaponsの末尾に移動
end
武器がなければ素手で最も耐久値も低い宝箱を攻撃
end
# 今回の行動回数がこれまでのパターンより少なければ答えを更新
best_score = current_score if current_score.size <= best_score.size
end
end
点数としては8,120,061から8,141,012に上がりました
2回目の時よりは上がり幅は低いですが効果はありました
改善案
正直まだまだ改善できるところはあります
もしかしたら200位以内も狙えたかも
- 素手で宝箱を開ける際、耐久値が最も低いものではなく得られる武器を見て宝箱を選ぶ
- 武器で宝箱を攻撃する際、確実に壊せる宝箱を選ぶ
- 今回は使う武器は入手順にしたが耐久値を最も減らせる順にする
- 武器で宝箱を攻撃する際、宝箱の耐久値がx未満なら素手で攻撃するようにする ( x == 10 など)
感想
やっている処理を見てもらったらわかると思うのですが難しい処理はしておらず、ABCだとB,C問題くらいの実装でした
AHCはよりアイデア、ひらめきが大事でそれが順位にも出やすいので始めたての人でも楽しめると思います
また今回のAHCはグリッドを操作するような実装が重い問題ではないかったので解きやすくて助かりました(いつも実装自体がきつい)
今後もこういう問題をお願いします！(切実)
青コーダーになってみせる！
Discussion