HTTF2022予選 メモ書き

 

 

（注意）コンテスト中に書いたものなのでかなり読みづらいです。

 

 

https://atcoder.jp/contests/future-contest-2022-qual/submissions/27198960

 

感想
    ローカルに提出できるような環境を作った方がいい（めんどくさい）
    線形代数は勉強した方がいい
    比較的当たりの解法を引けた回だったと思う

AHC003 参加記

AHC ヒューリスティクス 競技プログラミング

結果

117位

atcoder.jp

最終的にやったこと

ジャッジから与えられるパスの長さの情報をもとに辺の長さをどうにか推測して最短経路問題の復元をおこないました。

辺の長さの推測

パスの長さから推測

まず、通った回数が一番多い辺を一つ選びます。

次に、選んだ辺が含まれているパスの b_k e_kを使って辺の長さを推測します。

このとき、 \displaystyle\frac{b_k e_k}{パスが含む辺の個数} の平均を推測した値として使いました。

最後に、パスの b_k e_kと、パスが含んでいる辺の個数を、選んだ辺の分だけ引きます。

上の操作を全ての辺に行うまで繰り返します。

行と列をお気持ち

縦と横の辺に対してガウシアンフィルタをかけるようなことをしました。

M=1の場合に対しては、行（または列）の辺の長さを平均したものを、行（または列）の辺全てに上書きしました。

M=2の場合に対しては、よく分からなかったのでお気持ちをしました。

具体的には、行（または列）の辺を、ある辺を中心とした座標を変数にとる正規分布に従う重みで平均して、正規分布の中心の辺の長さを重みつき平均の値で上書きしました。

全ての辺が中心になる場合を計算して、全ての辺の長さを上書きしました。

M=1とM=2

本当はM=1とM=2を区別して処理を切り替えたかったんですけど、うまく区別することができませんでした。

なので、スコアが最大になるような比率を調べてM=1用の処理とM=2用の処理をどっちも使いました。

ダイクストラ

推測した辺の長さを使ってダイクストラ法で最短経路問題＋復元を解きました。

感想

初めて見るタイプの問題で本当に楽しかったです。

他の人の解法を見て、いろいろ勉強したくなりました。

CODINGAME SPRING CHALLENGE 2021 参加記

競技プログラミング codingame ヒューリスティクス

codingame spring challenge 2021に参加しました。

全体252位、ゴールド25位でした。

レジェンドに一歩及ばず😭

考えたこと

ビームサーチ

最初は相手の動きを考慮しないビームサーチを実装しました。

評価関数は「100000×スコア+1000×サイズ1の木+1000×サイズ2の木+1500×サイズ3の木+SUN」です。

スコア>木>SUN の順に評価してくれるように雑に決めました。

枝刈り（行動制限）を試行錯誤しているうちにGoldになれました。

この枝刈りは改良しながら最後まで流用しました。

DUCT

Gold昇格後は、だんだんとビームサーチの評価関数を考えるのがしんどくなってきたため、ビームサーチを捨ててTwitterで見かけたDUCTを実装してみました。

参考にしたDUCT資料

ぼくは英語が読めないので図を解読しました

なんとか実装したDUCTですが、プレイアウト回数がうまく増やせず弱かったです。（もしかしたらバグってたかも）

プレイアウト

DUCTを強くする方法が思いつけなかったため、他の実装を試すことにしました。

DUCTの実装を無駄にしたくなかったので、「有向手をプレイアウトして勝率を計算し、一番勝率が高かったものを採用する」というものを実装してみました。

有向手の選択には、UCB1を使いました。

これで252位までいけました。

追記 枝刈り（行動制限）について

最終的な枝刈り（行動制限）は以下のようになりました。

SEED

  • 0日目はSEEDしない
  • 20日目からはSEEDしない
  • サイズ0の木が存在するときはSEEDしない
  • 木が7個以上だったらSEEDしない
  • できるだけ他の木の近くにSEEDしない

GROW

  • サイズ2の木は23日目（最終日）にGROWしない
  • サイズ1の木は22日目からはGROWしない
  • サイズ0の木は21日目からはGROWしない

COMPLETE

  • 0日目から11日までは、サイズ3の木が6個未満だったらCOMPLETEしない
  • 12日目から14日目までは、サイズ3の木が5個未満だったらCOMPLETEしない
  • 15日目から18日目までは、サイズ3の木が4個未満だったらCOMPLETEしない
  • 19日目から23日目（最終日）までは制限なし

WAIT

  • WAIT以外に可能なアクションがあるときはWAITしない

感想

楽しかったです

AHC001 参加記

競技プログラミング ヒューリスティクス AHC

結果



atcoder.jp

やったこと

焼きなまし

初期解

1×1の正方形

遷移

遷移は一種類だけでした

  1. 広告をランダムに何個か選んで1×1の正方形（初期解の状態）に戻す。
  2. 広告をランダムに一つ選んでランダムな方向にランダムな長さだけ面積が r_i を超えないように伸ばす。
  3. 2を何回か繰り返す。
  4. 全ての広告について、面積が r_i を超えないように伸ばす。

最終的な解

スコアが最大になった解を保存して出力。

感想

一週間もあったのでいろいろなアイデアを試せて楽しかったです。