yukicoder score 6

[tipstar0125]

問題：https://yukicoder.me/problems/no/5017 解説：https://yukicoder.me/problems/no/5017/editorial

• 敵を進めるのではなく、1000ターン分余分なマスを用意して、自分を進める
• 一番近い敵を25列分もって、コピーを高速化
• レベルは390ぐらいまでいけるらしい
• 評価関数はpowerとscoreをturnを考えながら良い感じに混ぜる

ぷらちなさんWriter記：https://platinum-prog.hatenablog.com/entry/2023/07/25/181223 rhooさん解法（ビムサ）：https://twitter.com/rho__o/status/1681665412843421699 pokaさん解法（貪欲）：https://twitter.com/poka_cp/status/1680559487369838596

[tipstar0125]

出現確率分布の活用に関して

• 今回のパラメータ設定だと、敵がかなり出てくるので、あまり確率分布を求めて、敵が多い方に移動するとかはしても効果が薄いかもしれない
• 画面幅が広い設定だったらもしかしたら効く？

[tipstar0125]

ビームサーチ

• 制限時間2sec、1000ターンなので、1ターン当たりの計算時間は2ms
• 状態の持ち方を工夫しなければ、15ターンぐらい計算できて、高速化すると30ターンぐらいまでいけるみたい
• ビーム幅は自機の列数25×各列10の250くらい

[tipstar0125]

コンテスト中の解法 ・S or L or Rの中で最適な動作を評価関数で判定 ・レベルアップを最優先として、次に残り体力が少なく倒せそうな敵ならスコアを高くした ・死んだときのスコアは-INF ・スコア同じ場合は留まることにした ・周りに敵がいない場合は左右どちらかに確率で移動

得点：2,859,502 サンプル得点：約36,000

[tipstar0125]

まずは貪欲法をやってみたい。

なるべく多くの敵機を破壊する貪欲法 一番早く破壊できる敵機だけを狙えば良い動きができそう 自機を動かす際、次のターンに敵機に衝突してしまったり、敵機に包囲されて回避不能になってしまわないように注意

[tipstar0125]

貪欲法

• 目の前に敵がいて倒せる場合はとどまる。
• 留まっていても倒せない場合は左右移動するが、左右移動したら衝突する場合はその場にとどまる
• 左右どちらかが衝突判定だった場合は、衝突しないほうに動く
• 左右両方とも衝突判定ではない場合は、最短で敵が倒せるほうに動く。
• 左右どちらにも倒せる敵がいない場合は・・・一旦ランダム！

注意点！！！：自機と敵の距離が1になって、敵を消滅できなければ、次のターンで確定Game over

[tipstar0125]

貪欲法の提出

コンテストでも貪欲書いたけど、Game overのタイミングを勘違いしてた。。。 「自機と敵の距離が1になって、敵を消滅できなければ、次のターンで確定Game over」

• 左右どちらにも倒せる敵がいない場合、強制で右に移動：3,799,828点 https://yukicoder.me/submissions/895362

check_left/right_enemyの判定dy < tをdy <= tに修正：3,810,330点 https://yukicoder.me/submissions/895616

judge_collision_left/rightを改善：3,891,630点 次のターンで目の前に敵がくる場合も衝突判定していたが、実際は倒せれば問題ないので、倒せる場合は衝突しないとした。 https://yukicoder.me/submissions/895624

• 左右どちらにも倒せる敵がいない場合、強制で左に移動：3,763,608点 https://yukicoder.me/submissions/895616

• 左右どちらにも倒せる敵がいない場合、左右ランダム：3,279,230点 https://yukicoder.me/submissions/895367

ランダムで左右に動くと、敵がいないところを反復横跳びして、終盤敵を倒せないので、強制的にどちらかに流れてしまった方が点数取りやすいのかもしれない。

[tipstar0125]

もう少し貪欲を頑張りたい。 改善点としては、正面・左右どこにも倒せる敵がいなかった場合、どう動くのか最適かを適切に求めたい。

ただし、2手先以上は衝突を回避しつつ、どこで留まるべきかを決めるのは貪欲では厳しそう。 衝突回避は難しいので、 一旦敵がいるところまで探索して、左右どちらが有利か決める方針を書いてみるのはよさそうな気がする。

左右どっちに行った方が良いのか、敵の密度を求めると良さそうな気もするので、それでやってみる。

• 近くの密度が高い方がよさそう（遠くにいても、その分移動がロスなので）
• ターン数やレベルで行動を変更するとか

pokaさんも貪欲だったから、後でみておきたい！

[tipstar0125]

一旦敵がいるところまで探索して、左右どちらが有利か決める方針を書いてみるのはよさそうな気がする。

3,777,131点 https://yukicoder.me/submissions/895625

隣より先を探索しても、すぐ倒せなければ、あまり意味ないかも（新しい敵が出現したりするので） あと、ビジュ見ると比較的弾幕なので、敵が過疎っている状況（序盤）をがんばっても意味がなさそう。

[tipstar0125]

今気づいたんだが、levelはpowerで上がっていくけど、scoreはhpであがっていく。。。 scoreとlevel同じだと思ってた。 最初はレベルアップ重視で、後半はスコア重視にすると良さそう。

書いてみた：3,755,820点 https://yukicoder.me/submissions/895760

seed0002でうまくいっていないっぽい。 目の前、左に敵がいなくて、右に倒せる敵がいない場合は留まっている。 敵がいないとき、倒せないときの優先順位とタプルのソートの影響。少し工夫がいる。

評価値計算で、hp or pが小さく、tが大きい場合は0になってしまい、正しく評価できないので1e6をかけて評価したら、ちょっとだけスコア上がった。 3,869,015点 https://yukicoder.me/submissions/896736

[tipstar0125]

貪欲色々改善したけど、超絶激固弾幕？？があるっぽくて、ローカルテストケース100ケで問題なくても、提出したら点数が伸びない。どこかでGame overになっている。 貪欲は3.8-3.9Mで限界説。

試した改善

• その場にとどまっているとき、左右に動ければどちらか一方に動く（空打ちよりも敵を探す）
• その場にとどまっているとき、 左右近傍の敵数を数えて、数が多い方に動く
• SLRのソート工夫（評価値で基本ソートするが、評価値が同じ場合、今までRSLの順に選ばれやすいソートだったが、SLRにしてみた）

[tipstar0125]

pokaさんコメント： LRSの3択ではなく、どの列の敵を狙うかの貪欲を使ってですが一応4.29Mまででましたよ。 評価値は(敵機のinit_hpとpowerの重み付き和) / (敵機を破壊するまでにかかるターン) に加えて各列周辺の敵の密度的なものを使っています

コード(Rust) https://yukicoder.me/submissions/896568

[tipstar0125]

pokaさんのコメントを受けてどの列を狙うかの貪欲を書いてみた。 ただ、全ての列に最短で到達できるターン数を求めるとTLEするので、最大8ターンで到達できる範囲で計算した。 ※途中移動中に敵を倒すこともあるが、評価値には考慮していない

4,137,041点 https://yukicoder.me/submissions/896738

• 各列に対して最短で到達できるターン数をBFSでもとめたけど、行まで拡大してBFSすると、重複キューがなくなり、高速になる？？ ⇒関数名bfs2。若干？早くなったけど、あまり高速化できなくて、点数も変化なし：4,116,568点 https://yukicoder.me/submissions/896912

• 各列の先頭の敵のみで評価値を計算していたのを、全ての敵に変更した。あまりのびず。：4,056,776点 https://yukicoder.me/submissions/896990

• 各列の先頭の敵のみで評価値を計算していたのを、全ての敵に変更したv2。bf2(8turn)使用：4,277,879点 https://yukicoder.me/submissions/896992 ※スコアが伸びなかった方は、敵を倒すたびにscore/turnを積算していたが、scoreとturnを積算して、最後にscore/turnを評価値とする

• 移動の途中でダメージ与えるのは無視しても、倒せる敵は考慮しやすそうだから、評価値に加えた方がよさげ？？ ⇒ビームサーチした方が実装しやすそう。。。

• ターンが進むごとに、評価値はスコアの取得を重視、powerの取得の影響をさげていくこともやってみたが、効果が出なかった。。。なぜだろう。。。 ⇒現時点のhpではなく、init_hpで評価しないと、powerの評価と同じにならない ので、評価に使用するパラメータをhpからinit_hpに変更：4,296,090点 https://yukicoder.me/submissions/897111

[tipstar0125]

pokaさんコード（4.29M点）解読 https://yukicoder.me/submissions/896568

Main

1. 敵情報を入力
2. preprocess(敵の位置情報更新、両端キューを使って処理圧縮)
3. greedy(最もスコアが高い列xを取得)
4. move(x列に移動、衝突するならS、衝突回避できないならnot success、敵機が衝突しなくても目の前に来たらNG)
5. postprocess(自機を移動、敵機のダメージ及び撃墜判定)

Enemy

1. init_hp, hp, power, x, y
2. evaluation: 序盤（レベルが低い時）は敵のpowerを重視、levelがあがるとinit_hpを重視。level=250になると、init_hpだけで評価

greedy

1. enemies_score_sum: 各列における敵機のinit_hpの総和＋周辺敵機のinit_hpの総和（距離の2乗で割る）
2. 候補になる（先頭の）敵機取得
3. 各列についてスコア計算
   • 敵機の評価
   • 敵機を撃墜するまでのターン数計算（移動＋攻撃）
4. 最もスコアの良い列を返す

compute_attack_turn

1. 移動ターン数計算(compute_approach_turn)
   • player, enemiesをclone
   • 移動したい列に到着する最短ターンを求める（衝突判定の場合はS、回避できない場合はINF）
   • 例えば、右に移動したくて、左に避けるみたいなことはしていない
2. 撃墜ターン数計算

スコア

• main: enemyのevaluationで得られた値を撃墜に必要なターンで割った値
• sub: enemies_score_sumに0.15かけた値。ただし、序盤（レベルが低い時）は割合を下げて、TARGET_LEVEL=250で効果最大。序盤は敵がたくさんいてもそんなに倒せないからだと思う。

理解できていない点

• 敵の評価でnow_hpではなく、init_hpで評価するのはなぜか？⇒倒して初めて得点が得られるからだと思う。powerと同じ評価になるからそりゃそう、という気持ちになった。

[tipstar0125]

貪欲をさらにがんばろうとすると結局ビームサーチっぽいことになる（すでにビームサーチっぽいけど）。 ビームサーチをやった方がよさそうなので、ここら辺で貪欲を切り上げる。

貪欲まとめ：

• 8-9ターンで到達できる列の貪欲
• 到達できる列とそのターン数及び最初のアクションに関してはBFSで求める
• 評価は序盤はレベルアップを重視するため、powerを重視。後半はinit_hpを重視。一撃で撃墜できるようなレベルからは、init_hpだけで評価

重要：評価関数は最終的には問題のスコアに近づくようにした方がよい。やり方には2通りあって、ある閾値（今回の場合レベル）を境に評価関数を変えるとか、レベルごとに重みを変化させる。2つのやり方を混ぜるのもあり。

最大4,296,090点獲得 https://yukicoder.me/submissions/897111

[tipstar0125]

ビーム打ってみた。 ビームの深さが5までしかいかないので、5ターンでスコアを獲得できない場合は、全てのスコアが同じになって、その場にとどまってしまい、最後まで残ったとしてもスコアが全く伸びない。 https://yukicoder.me/submissions/897194

改善案

• 計算量減らす：計算量重い処理がない。。。
• コピー量を減らす：序盤で敵が少なく、コピー量が少なくてもそんなに回ってない。いつか改善した方が良いが、もっと別のところに問題ありそう？？
• ビームで、重複した状態があるような気がする。特にスコアに変化がない場合とかは、同じ列に戻ってきたら同じ状態になり、意味のない計算をしているかもしれない。⇒BTreeSetで重複削除しようと思ったら、スコア以外無視で重複削除され、良くない。オーバーライドの実装をタプルとかで工夫すると良いかもだけど、実装大変そう。
• 敵機を倒せない場合は、敵機に与えたダメージも込みで評価する⇒ダメージも同じになることがあるので、残りhpとかも評価しないといけなさそう？？⇒ダメージに加えて、自機がいる列の先頭の敵を倒しきることができる場合は加点 ※ビームの追加順をS -> L -> Rの順にして、スコアが同じ場合はSが選択されやすいようにした（留まって敵を倒しやすいかも） ※ビーム深さ（ターン数）は5-6程度 ※評価関数をレベルアップメイン、スコアメインどちらにしてもあまり変化なし 4,122,093点 https://yukicoder.me/submissions/899464

bowwowさんツイート：

敵を1体倒すまでを深さ1としたビームサーチ。深さ4の幅8までしかできなかった。 https://twitter.com/bowwowforeach/status/1680521601559691265

[tipstar0125]

コピー量を減らす案：

• 行動を1次元でもつ（同じ敵に複数回攻撃している場合は圧縮）
• 敵の状態は各列両端キューでもって、実際にターンが進むごとに更新
• 敵の状態から次の行動を求めるが、状態コピーするとコストが高いので、状態は参照して、行動をシミュレーションしつつ、次の行動を求める