TOYOTA Programming Contest 2023 Summer final: Transit Warehouse

[tipstar0125]

https://atcoder.jp/contests/toyota2023summer-final-open/tasks/toyota2023summer_final_a

[tipstar0125]

コンテスト中解法

• BFSで各コンテナの理想の距離を求める
• 置ける場所をBFSで求めて、理想の距離に近い場所に置く。ただし、次回以降で置けなくなる箇所がある場合は置かない
• BFSで取り出せるコンテナを求めて、番号が小さい順に取り出す
• 理想の距離の配列は使用されたら削除することで、点数が伸びた

[tipstar0125]

解法近い人の解説、ツイート

• nok0さん：https://twitter.com/nok0_kyopro/status/1695659276185063540
• hirayuu_Atさん：https://atcoder.jp/contests/toyota2023summer-final-open/editorial/7056

[tipstar0125]

terryさん(1位)の解法

https://twitter.com/terry_u16/status/1695696323662709081 https://atcoder.jp/contests/toyota2023summer-final/submissions?f.Task=&f.LanguageName=&f.Status=&f.User=terry_u16

• コンテナを置いてしまったら、置けなくなる場所が発生しないようにする⇒LowLinkによる関節点検出
• 理想的な距離に近い候補を選ぶ
  • 壁に近い候補を最優先で選ぶ
  • 距離が理想より短くなるような候補は優先度を下げる
• 焼きなまし
  • 取り出す順番の優先順位を焼きなまし
  • ランダムでコンテナidを選んで抜き出し、ランダムで再挿入
  • スコア計算（転倒数計算）はBITで高速化
• モンテカルロって何？

[tipstar0125]

コード改善

• インタラクティブの入力をmain関数だけでなく、構造体や関数内で、できるようにする
• 座標構造体
• 列挙型を使用して、各グリッドの状態を指定
• Map2Dという構造体で、Indexトレイトをオーバーライドして、座標構造体でindex指定できるようにする