トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）に参加して 暫定39位でした。

反省、または誰かの為になることを期待して参加記録を残します。

seed=0の結果。Score=82

問題概要

https://atcoder.jp/contests/ahc033/tasks/ahc033_a コンテナが流れてくるので指定の位置、指定の順番で搬出してください。

解法

大まかな解法は以下の通りです。

  1. タスク（搬出、ストックに置く）の優先度を決める

  2. 優先度が高い順にクレーンにタスクを割り当てる

  3. 割り当てられたタスクをもとにクレーンの操作を決定する

  4. クレーンを操作する

  5. 2～4を搬出終了まで繰り返す

  6. 1～5を時間まで繰り返す

ストックを利用することで、ターン数以外のペナルティ０を達成することができ、ローカルでは平均74手で完成しました。

これで暫定テストで85%程度（39位）の点を得られます。

タスクの優先度

タスクとは、搬入口から搬出口への輸送、搬入口からストックへの移動、ストックから搬出口への移動のいずれかを指します。タスク列とはタスクの列のことで、実行可能なタスクが2つ存在するとき、タスク列の左に存在するタスクが優先して実行されます。

タスク列の生成は、小クレーンが一つでクレーンの移動を無視していいとして考えました。

ストック

ストックとは、搬入口にあるコンテナを搬出口以外に移動させるときの一時的な置き場のことを指します。主にストックは6個としていましたが、6個での達成が困難であるときは多めにストックを確保しました。

ストックの位置（赤丸）

タスクのアサイン

タスク列をもとにクレーンにどのようにタスクを割り当てるかを考えます。

まず、各クレーンについてコンテナを持っている場合は現在のタスクをそのまま割り当て、コンテナを持っていないクレーンは一度タスクをリセットし毎ターン割り当て直します。その操作後、タスクが割り当てられていない個数を x個とすると、タスク列の内完了しておらず実行可能なタスクを左から x個取り出します。各タスクとクレーンの全組合せ x!通りを全探索し、クレーンとコンテナのマンハッタン距離の総和が最小のものをタスクの割り当てとして採用します。

クレーンの操作

割り当てられているタスクのコンテナ番号が小さい順にクレーン操作を決定していきます。

クレーンの位置と目的の位置が同じときはPまたはQのどちらかです。そうでない場合、前ターン操作後のコンテナの位置と先に決定したクレーンの次ターンの位置をもとに最短経路となる手をBFSをせずに計算して選びます。

日記

メモなので汚いです。

目標
  • 2330パフォ以上で橙になる。
  • 考察を頑張る。特定のケースから考えてみる。
  • 小さなところから根拠をもとに大きくしていく。
コンテスト１日目
  • 問題読んだ。マルチエージェント。実装が膨大になりそう。きれいにメソッドを作りたい。
  • 全てのペナルティ０を達成可能そう。上位は僅差になりそう。
    • 全ケースペナ０は達成容易だった。
  • 最初の実装は4列目までコンテナを出し終えたら大クレーン以外を爆破するか。手動seed0が286ターンだった
    • 平均290ターンのを提出。37で12位。
    • 爆破するんじゃなくて、右端で待っているのが賢いか。
  • ターンを縮めるには、小クレーンを残して道整理役を作る？
  • 理論値を見積もりたい。最終的に100ターンくらいで完成するんだろうか。
  • トヨタ決勝みたいに、id%Nが小さいのを左側に、大きいのを右側に配置するのがいいのかな。
  • 探索方法がわからない。
コンテスト2日目
  • 290手が14.2まで下がっている。1位は82手程度ってこと？
    • 13.1まで下がった。76手程度。
  • テスターを参考に作る
  • 80ターンくらいならビーム撃てるかも。
    • 目的地への距離の総和を評価値。まだ出ていないのはコンテナに邪魔されているとする。空きコスト１コンテナコスト５くらいにする。
    • 行０で搬出できていない場合、コンテナ0..=4の重みは、10,3,1,-1,-2くらいにする
  • 置き場は２３列目に６－８個のみにする？
    • ストック６でほぼすべてのケースで成功するっぽい。８なら100%
    • 30-40個くらいの運ぶタスクに分解される。N個に分解される。このタスク全てを完了させるスケジューリング問題？
    • １つのクレーンが8個のタスクをして平均10手なら80手くらいで完成する。
    • タスクの割り当ては最初はとりあえず順番でいい
    • タスクが決まったとき、デッドロックは発生するか？０，１列目で発生しそう。発生したら前のターンに戻って片方を停止をするようにすれば大丈夫そうか
コンテスト3日目
  • 1位68手
  • 手動で6ストックをすると8６手が達成できた。大クレーンの機能は使っていない。これを探索の段階まで持っていけたら70手切りもできそう。
  • ストックの位置は個数はもっといいものがあるかもしれないから汎用的な感じで実装したい。
  • タスクの割り当てが決まったときの各クレーンの動作を計算する必要がある。
  • これか？
    • 各タスクをaからbへの移動（移動後は爆破）とすればこれに落とし込める？
    • 順番にルートを決める。それまでの決定に衝突しないように適宜停止する。これはbfsでいける。タスクが割り振られていないなら、(i, 0)をランダムに選ぶ。目的地を一致しているものを最初に動かす。
    • これだと大クレーンの特性も生かせる。
  • 何とか実装した。
    • 2、3割で失敗する。
    • 0が完了するまで１を出口に向かわせていない
    • 平均150手くらい。２７.0で20位。たぶん上振れ。
コンテスト4日目
  • 改善案
    • ０が完了するまえに1を動かし始める
      • これはどうすれば実装できる？
      • タスクの割り当てという考えをやめる
        • 各コンテナに、持たれている、ターゲットになっている、なんもなしの３つの状態を付与する
      • 割り当ては置いといて、持っているクレーンの動作は、一つ前のコンテナが持たれていて自分より距離が短いならそこに向かう、そうじゃないならストックへ向かう
      • 割り当ては、まず搬出できるものを選ぶ、その後、1つ前を移動しているもので距離が遠いものを選ぶの繰り返し
      • 一個前のものが既に誰かに運ばれている場合のみに限定した方が楽か。一個前の出口までの距離<それに最も近いクレーンの距離+出口までの距離のときのみ許可
    • タスクのアサインを近いものorマッチングさせる
    • 操作長の最大値を最小化or総和を最小化するようなactionを採用
    • 通れる場所を制限
    • ストック個数を変えてみる
    • ストックを選択するとき、できるだけ出口に近い行を選択する
    • 逐次改善にしたい
    • タスクの割り当てがないときも、次に来る位置に向かって移動しておく
    • タスク作成関数の見直し
    • コンテナを持っていないクレーンは毎ターンタスクをアサインしなおす
    • ストック操作より搬出操作を優先
  • 平均10５まで下がった。けどあんまり伸びず32.9で21位。
    • 時間10倍にすれば96まで減る
    • 100.8まで伸びた。
    • ９６．９まで伸びた。
      • 35.5で19位
      • 時間10倍で90手
  • ビーム化は簡単そう
    • うまくいかない。深さをターン数をではなく進捗でしてみるか
    • 進捗でやっても多様性が確保できずに完成しない
  • 搬出が偏っているときのスコアが悪い
  • 明日は01を同時に動かすのを作りたい
コンテスト5日目
  • （タスクの概念は無しにしたいけど）タスクの長さとスコアに相関はあるか
  • 追い抜きが発生してしまうこともあるけどとりあえず動くものができた。
    • 0,1,2を同時に運んでいて、0,1を搬出、2をストックに置こうとしているときに、0を搬出すると1,2の距離が逆になってしまうことがある。
      • アサインかストックタスクの更新に問題がある？
    • 実装がめちゃくちゃになったけど直した。
  • 部分破壊で焼きなませる？
  • ８５まで下がった
    • 10倍で８２まで下がる
    • ３８．９で20位
  • 持ってないクレーンはストック上を動いた方がいいか？
  • 今の方法だと限界が近そうなのでビームか焼きなましにしたい
コンテスト6日目
  • 追い抜かないようにするの結構簡単だから持ってないときのアサインも早めにする？
  • 明らかに悪いとわかったら早期breakして高速化
    • 2倍くらい早くなって82まで伸びた
      • 10倍で80
  • 完了分を[0,0,0,0,0]から[5,5,5,5,5]までのdp,ビーム？
コンテスト7日目
  • 他のクレーンに影響を与えるのを1手目だけにしたら微高速化で80
    • 10倍で78
  • スコアが悪い奴はcheck_stockが半分くらい使っている？
  • calc_actionはメモ化したら高速化しそう
  • ラスト5個以下になったら必ず割り当てるようにしたら79
    • 10倍７７
  • 初手の動きはどんなのがいいだろうか
  • 均等に残るようにしたい
  • 残り時間が僅かになったら今までのbesttaskを繰り返す
    • ７８
コンテスト8日目
  • besttaskは半分で分割する？
  • 1000ケース中3ケースが貪欲しか成功していない。これにより平均が0.6手上昇している。
  • クレーンpos=targetのものがあれば、操作させてからアサイン、アクション計算した方がいい？左端のを持った時点で搬出させたらバグるかもしれないけど、1手先に近づくことができる
コンテスト9日目
  • ↑めっちゃバグらせている。
    • やりたいこと
      • アサイン前に、置く、取ることが確定している（cranepos=target）ものは先に操作する
      • ストックタスクの更新
      • 搬入搬出できるならする
      • まだ操作していないもののアサイン
      • 動き計算
  • 上のはバグったままだけど、apply時にそこにクレーンがあっても搬入するようにしたら伸びて76.5
    • 10倍75
  • 持ったときにtargetpos = !0にしてはいけない
  • バグらせまくりなのでとりあえずdpを先に試す
    • ｄｐ（ビーム）したけど100手を下回れず
コンテスト10日目
  • 2000ケースで9件失敗している。これ改善で0.9改善
  • 実行結果を観察してると、やはり置く取る操作を先に対応させた方がいい。実装したい
  • 76.1
コンテスト11日目
  • 何とか実装して75.4。思ったより伸びなかった
  • 貪欲も5個でやればいいのでは
  • 10000ケースで53ケース失敗
    • 暫定テストで1ケース失敗
  • 悪いケースも90手以内くらいに収まってくれるようになった。
  • 暫定39位、42.8でフィニッシュ。

終わりに

良かった点
  • 複雑な実装だったけど完成させることができた。
悪かった点
  • 数字を使って方針の根拠や方向性を決定することができなかった。
  • ビームは思いついたけど評価関数と多様性の確保ができなかった。
Todo
  • ビームの評価関数と多様性の練習
感想

問題を最初に読んだときは盤面が小さすぎてギリギリの勝負になるかと思っていたけど、技術で差がついて面白い問題でした。

最近コンテストで学びを得たりすることがなく、自分の現在の実力の範囲内でしか問題を解けていないのでよくない。橙になれそうだけど赤になるには今持ってない強みを獲得する必要がある。

THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）に参加して 35位でした。

反省、または誰かの為になることを期待して参加記録を残します。

seed=1の様子

問題概要

https://atcoder.jp/contests/ahc030/tasks/ahc030_a

グリッド上にポリオミノが重なりを許して配置されている。その位置を推定してほしい。

解法

大まかな解法は以下の通りです。

M=2のときは、全ての配置が高々 N^{2M}なので全ての配置を保持して占いの結果をもとにベイズ的に確率を更新しました。

M=3のときは、全ての配置について事前の占い結果をもとに尤度を計算して、その上位10000個だけでM=2と同じように解きました。8割くらいは上位10000個に正解が含まれていました。

M>3のときは、

  1. 最初に盤面を格子状に区切って占う
  2. 各ターン占いと採掘結果をもとに油田の配置を焼きなましによって推定する
  3. 焼きなまし結果をもとに占いまたは採掘をおこなう
  4. 適宜回答クエリを投げる

これで暫定テストで22%程度（34位）の点を得られます。

初期占いパート

N, Mによって辺の長さが3から7までの長方形を詰めるように盤面全体を占いました。

焼きなましパート

過去の占いと採掘の結果をもとに、ありそうな油田の配置を焼きなましで探索しました。

近傍は1個以上の油田をランダムな位置に変更させるものでした。評価値は過去の占いと採掘の結果から、その油田の配置の対数尤度を求めてそれを最小化しました。

近傍の設計が悪かったらしく、かなりの高温でもvalidな配置が一つも見つからないことも良くありました。このvalidな配置というものは、尤度が小さすぎずこれまでの回答クエリと一致しないものを指します。

占い・採掘パート

焼きなましでvalidな解が見つかったときは、尤度の大きい２つの差集合をとり、その大きい方を占いました。

焼きなましでvalidな解が見つからなかったときは、以下の優先度が高く中央に近いものを1点堀りしました。

  1. 周囲が全て1以上だと予測されていて、かつ自分が0
  2. 周囲3マスが0だと予測されていて、かつ自分が1
  3. 周囲3マスが1以上だと予測されていて、かつ自分が0
  4. 周囲2マスが0だと予測されていて、かつ自分が1

日記

メモなので汚いです。

目標
  • 2500パフォ
  • 乱択要素を入れる前に貪欲を考える
  • 実装やツールを最初の方は整備する
コンテスト１日目
  • 問題を読んだ。推定系で諦めムード
  • 平均と分散のところがぱっと見ではよくわからない。式をちゃんと理解するべき
  • ジャッジ部分をきちんと実装しよう
  • 盤面サイズとブロック数がかなり小さいのは、しっかり推定しなさいってことかな
  • ミスするとほぼ0点になるので、コストを減らしつつ100%確定という状態までするのだろうか。それともコストを減らして賭けに出る方がいいのか？
  • 方針案
    • ベイズ
    • 尤度を最大化するように焼く
    • 各クエリで確からしさの改善量が最大になるように選ぶのではなく、クエリ全体で確からしさを最大化させたいことに注意
    • ガウス過程？
コンテスト２日目
  • 平均と分散の式がわからない。
  • すでに高い確度で分かっているマスはsurveyに含むべきなのかどうか
  • とりあえずsurvey無しでブロックの位置が確定するまで掘り続けてみる
  • サンプルコードとの相対スコアがわかるので提出する必要は薄そう
  • 0以上のマスを見つけたらbfsで周囲探索
  • 現在の1位はコスト \frac{N^2}{4} ほど。最終は \frac{N^2}{12}くらいかな
  • あるブロック配置のときの尤度を求めるものを作る
  • 推定がミスったときはわざとWAにしたほうがわかりやすい
  • 掘ったやつに一致させる配置は乱択dfsでいけそう？
コンテスト3日目
  • 当然だけど、隣接マスの v_{i,j}は近い
  • 観測結果から尤度を最大化させる配置を焼きなましで求めているけど、貪欲ではできないか？
  • 0以上のマスを見つけたらbfsで周囲探索
    • サンプルの倍くらいで129位
  • 大まかに推定してから、鍵となる点を掘りたい
    • 3×３を1個飛ばしで推定してもコストは \frac{1}{10}くらいでそれなりの精度で予測できている
    • 外側に張り出している角は重要そう
    • または０予測したマスでへこんでいるところ
  • ↑のを実装して提出。ローカルではサンプルの0.3倍で16.7で30位
    • 3×３を1個飛ばしで大まかに推定
    • 何回かに1回焼いて、1マス探索を優先度に従って行う
        1. 周囲が全て1以上だと予測されていて、かつ自分が0
        1. 周囲3マスが0だと予測されていて、かつ自分が1
        1. 周囲3マスが1以上だと予測されていて、かつ自分が0
        1. 周囲2マスが0だと予測されていて、かつ自分が1
        1. 自分が1以上の内ランダム
      • 同じものがあれば、中央に近いものを優先
  • 焼きなましの近傍を1個移動から2個移動にしたら4%ほど改善した
コンテスト4日目
  • 貪欲。各ブロックについてこれまでに掘ったやつに矛盾しない位置を列挙。まだ掘っていないマスの内、一番重なりが多いマスを掘る。
    • これで0.3
  • mm147は役に立つかな？
  • eps=0.01の場合を考える
  • 3×３のマスを測定したとき、その中心の値を推定できないか
  • 各マスについて０である確率を持っておいて、サンプリングするごとに更新する？
  • 複数まとめて測定するとき、はなれたものだと情報がすくなくなる？3×3とかだといいのか?
  • 理想では各 (pos_0, pos_1, ..., pos_{m-1})について確率をもっていて、ansクエリではそれが最大の組を出力したい
  • 3×３より十字のがいいか？
  • 掘るやつ同士ははなれているほうがいい？
  • 1点掘りパートになったら、モンテカルロで一番いいところをほればいいか？
    • まず評価値によるいい感じの貪欲をしたい。
    • モンテカルロだと毎回焼けないので焼きなしで可能な評価がいい
コンテスト5日目
  • 時間無視でモンテカルロを試す
    • 重すぎるし改善しない
  • 各ブロックの存在確率を持ちたいけど、独立じゃないから無理そうって考えてたけど、AHC022では縦方向の正規化ってやつが有効だったそうだけど、これには使える？
  • おおまかにブロックの位置がわかっているとき、1点堀りでは０が判明する方がうれしい？
  • まんべんなく掘ったほうがいい
  • 答えがかぶっているときは、別のを出力
  • スコアが低いのが必ずしも解とは限らないので、温度は高めに
コンテスト6日目
  • 次掘るのに最も良い手は、あり得る解候補を列挙してその候補数を減らせる手
  • 1番と2番の違うところ？
    • １１．６９で37位
    • 差集合のどっちかをsurveyすればいい？
  • 現状スクリーンショット (66).png)
    • epsはほぼ関係ない
    • mが大きい奴をどうするかが大事
    • mが小さいやつはほぼ意味なさそう
  • 推定盤面を複数生成。解が一意になるような1点堀りするマスの集合をマスの個数を最小化するように焼く。一致しているところが多いものを掘る？
    • 点の個数と配置の総積の和を評価値にする
  • ０と１が隣り合っているところを発見すると嬉しそうなので、０と１をみつけたらその間を二分探索？→微妙
コンテスト7日目
  • 時間を10倍にしたら1割くらい伸びる
  • 4倍の点を取るにはどうすればいいか考える
    • 1点堀リの数を4分の1にできるのか
    • surveyを活用するのか
    • ｍごとに提出してそれぞれ何割取れているか確認する
      • 2\le m\le5 、19ケース2.23(11.7%)
        • 3.57(18.7%)
      • 6\le m\le10 、21ケース3.60(17.1%)
      • 11\le m\le15 、7ケース1.34(19.1%)
      • 16\le m\le20 、3ケース0.87(29.0%)
  • １つのブロックでできている島は、4方向から固定してやれば位置がきまる？
  • mcmcっぽくサンプリング？
  • 1点掘るなら、０か1以上かが最もあいまいな場所を掘りたい
  • ある点を掘った後にかかるスコアの期待値を求められたら
  • 推定盤面に対して、スコアが10倍になるだけの数の点を焼きなましにより配置し、その中で一番評価が高いものを掘る
    • この焼きなましは、各ブロックは０と接してるなら4方向に０があると高評価。各ブロック最低1個は1以上の点が欲しい。
    • 点の個数も最小化
コンテスト8日目
  • 線形補完？
  • 推定盤面が焼きなましでx番目にscoreが小さいとき、(x-1)番目までの各盤面と推定盤面と違うところに少なくとも1つ点を置くときの最小個数を評価値とすることができる？
  • (x+y)%2=0しか置かない
  • サンプル
    • 2\le m\le5 、19ケース0.15(0.8%)
      • \frac{N^2}{100}を目指す
    • 6\le m\le10 、21ケース1.02(4.8%)
      • \frac{N^2}{15}を目指す
    • 11\le m\le15 、7ケース0.53(7.6%)
      • \frac{N^2}{10}を目指す
    • 16\le m\le20 、3ケース0.５２(17.4%)
      • \frac{N^2}{5}を目指す
  • 予測配置で面積の小さいものから
  • 差集合の内、最も大きな連結成分をsurvey?
  • 推定盤面で各ブロックの中、上、下、左、右に点がなかったらおく
コンテスト9日目
  • 焼きなましでvalidな解に移動できていない
    • いくつかブロックを取り除いて、矛盾しない位置に移動
  • 9.81で25位
    • 最終的に1.5倍くらいまではのばしたい
  • eps=0.01は半分くらいにできるはず
    コンテスト10日目
  • M=2は全探索できるはずなのでする
    • 考えること
      • 各配置の確率を決定したときに、ansクエリをするべきかどうかの判断
      • surveyするとき、どこをするべきか
    • 4倍くらいに伸びた
      • m=2をこれにしただけで、1.8くらい伸びた
      • M=3,4も最初の焼きなましで間引けばいけるのではないか？
コンテスト11日目
  • 微改善しただけ

終わりに

良かった点
  • copilotを使いはじめて実装速度が上がった
悪かった点
  • コードが汚くなりすぎた
  • 勝てないのに潔く諦めなかった
Todo
  • ファイルの分割
  • 統計、機械学習の知識をつける
感想

見た瞬間に苦手そうだと思ったけど、実際に苦手で最後まで問題の理解が進まなかった。統計の知識が足りなさを痛感した。

M=2のような単純なものから考えていくと考察が良く進んだ。最初から特定のパラメータに限定して考えるというのも悪くないかもしれないと学んだ。

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）に参加して 10位でした。

反省、または誰かの為になることを期待して参加記録を残します。

 

 

問題概要

グリッドの原点から始めてすべてのマスを１回以上通って原点に戻ってくるようなルートを作成し、そのコストを最小化してください。ただし、各マスには訪問と訪問の間隔により異なるコストがかかります。

seed=0の様子

解法

大まかな解法は以下の通りです。

  1. validなルートをdfsにより生成し、これを初期解とする。
  2. ルートを部分的に破壊して再構築する焼きなましをする。

これで暫定テストで96.9%程度の点を得られます。

初期解の作成パート

訪問順をランダムにしたサンプルプログラムを100回実行して、最も素のスコアが高いものを初期解として採用しました。

おそらく初期解が最終スコアに与える影響は大きいのですが、良い方法が思いつきませんでした。

焼きなましパート

ルートの一部の区間を別のものにすることを近傍とする焼きなましをしました。近傍の詳細は、

  1. ある区間を１つ選び、dfsで作成した新しいルートに変更する（95%）。
    区間幅1-50程度の区間を選択し、区間幅1-7程度のdfsで作成した新しいルートと交換しました。dfsでは関節点以外の点の訪問は１回までに制限し、関節点は何回の訪問可能にしました。
  2. 最初と最後のマスが一致する区間を２つ選び、これらをスワップする（1%）。
    マスp0..=p1という区間が２つあった時、これらを交換してもvalidな状態は保たれています。
  3. 最初と最後のマスが等しい区間を１つ選び、これを反転する（4%）。
    マスp0..=p0という区間があった時、これを反転してもvalidな状態は保たれています。

です。

スコア計算が重いので差分計算を頑張ります。計算は合わなかったけど、焼きなましのイテレーション1000回ごとに正しいスコアに直したら問題は起きませんでした。数十万から数百万回イテレーションできました。

差分計算

ある区間が変化したときの、その区間の中で閉じている部分のスコア差分計算については省略します。

差分計算で重要だったのは、変化した区間と変化していない区間にまたがる部分のスコアでした。特に区間の変化によって長さが変わるときに複雑になりました。

図１のような、4個のマスがありルートの長さが10であって、ターン６とターン７の間にルートが挿入されることを考えます。その時各マスのスコアは(訪問間隔×d)だけ増加します。全マスにおけるsum(訪問間隔×d)=xとすると長さがL増加するときは、x*L + (L-1)*L/2 * sum(d)となります。逆に縮むときはx*L - (L+1)*L/2 * sum(d)に近いです（あるセルの区間がL未満だった場合はおそらく誤りです）。

各ターンにおけるxを事前に計算しておくことで、計算を高速化できました。事前計算には経路の長さ分だけ時間がかかるのですが、焼きなましの受理率が数%であったため、受理されるたびに計算しても問題ありませんでした。

図１. ルートの例（赤丸: 訪問, 青線: 訪問間隔）
その他の工夫
  • ルートの倍化。
    実行時間が半分過ぎたタイミングとラスト付近で、ルートを同じものを2個つなげました。こうすることで、dが小さく訪問頻度を下げて良いマスを消去しやすくなることを期待しました。実際に当時のスコアで6%ほど改善しました。

日記

メモなので汚いです。

クリックで詳細表示
目標

最低限の取り組む時間で黄上位程度をめざす。考察してある程度の根拠をもって実装する。きれいなコードを書く。

コンテスト１日目

問題を読んだ。得意そうなやつで嬉しい。

ルートにループする動きを追加した場合、汚れの大小関係は変化している場合があるので、少し文脈がある。

コンテスト２日目

ahc024みたいに期間が重要かも。

シンプルな部分破壊焼きなましを書いて11位。この問題は評価関数と高速化ゲーになるのでは。

探索効率が悪いので、再構築時は同じところの訪問を禁じるか。それでも折り返しなどを保てる？

ルートで座標p0..p1という区間が２つあった時にそれらをスワップする近傍を追加して１割くらい点が伸びて45.6億で７位。

p0..p0という区間を反転する近傍を追加で46,6億で５位。

実行時間を10倍にできたら数%伸びるので1位くらいのスコアは出る。スコア計算が重い。とりあえず未訪問のマスがあるときは計算しなくする。

初期解をサンプルのままにしているけど変えたい。いい貪欲とはなんだろう。

盤面の平均より大きいものを消せばいい？

動きの長さは短いほうがいいのか？

コンテスト３日目

bitset高速化？

dが小さいマスを何回も通る必要はない。繋ぎなおしはdfsではなく、dが多いところを通るダイクストラ？

未訪問期間の寄与が最も大きいマスをなんとかする。

受理率が数％なので、意味のある候補を生成したい。

確実に前進するような、繋ぎなおすときの貪欲はあるかな。あれば山登りキックでいい。

コンテスト４日目

平均aよりaが小さいマスを１手追加して踏むことで改善することは絶対にない？一度のみ訪問するマスの平均コストはd*(L-1)/２。dが小さいマスを訪問する回数を減らし、dが大きいマスの訪問時期を分散させることが重要。

一筆書きよりは小さくしたい->さすがに一筆書きよりは数割良かった。初期解はできるだけ一筆書き->dfsの方が強い。

ビジュアライザにマニュアルモードを追加する。ビジュアライザをマニュアルモードで１手ずつ更新すると重すぎるので差分計算できるように自作する。

Lが無限であるとき、理想はdの比率で訪問を均等な間隔ですることが理想だと思う。現実ではdが大きいところの間の移動距離がボトルネックになる？

倍化しても、スコアが悪くなることはない。時間が半分すぎたら倍化するようにしたら、なんと6％ぐらいコスト減少した。倍化したから区間削除も追加する->伸びない。

10倍速にできると、49.1（2位相当）はでるらしい。

コンテスト５日目

被覆問題？

差分計算しようとすると、stateの更新ごとに必要なデータの更新が重くなってボトルネックになってしまう。いいデータの持ち方を考える。

スコア計算は頑張ればO(変更された長さ)で可能だけど、そのデータの更新に結局O(L)かかってしまう。データ更新もO(変更された長さ)でできるかもう少し考える。

閾値で枝刈り。

でかい幅でswapとかが成功していないなら、幅を縮める。

反転は差分計算が簡単。

今46.0で15位。5倍速にできたら47.9で4位くらいでるのに。

コンテスト６日目

changerouteでももとの長さと新しい長さが同じになることが1/10くらいである。これは差分計算が簡単にできる。

差分計算をバグらせまくり。明日完成させる。

コンテスト７日目

伸ばすときのコストはあっているっポイ。

dna。

今のままだと、行き止まりを往復するようなものはあらたに生成されないので、コピーして挿入する近傍を作る。

ばぐとれない。スコア合わないまま使ってみたけどそんなに早くならない。

コンテスト８日目

47.5で13位相当。

焼きなましの受理率が1%くらいなので、いい近傍を列挙できていない。

スコアはnかn^2で割ってそろえる？sum(d)をそろえた方がいいと思ったのでsum(d)=100000となるようにdを調整した。まあまあ伸びた。

dfs中で未訪問があったらng。

48.42で7位相当まで来た！もし５倍速にできたら2%伸びるので、49.39で2位相当になるらしい。

penalty設定してないけど何かいいのあるかな。最初の方は長さが（長いor短い）ほうがいいみたいなのか？

コンテスト９日目

nと壁の個数ごとにパラメタ調整あとでする。多点スタート。キック。スコア計算を閾値で枝刈り。

ラストに詰めの貪欲で短くできるか。

10個近傍をつくって最もいいものを必ず受理する？

前回変更された近傍の近くは改善の余地がある

dfs中で大まかにスコア計算して、あまりにもあり得ないやつはngにする。->適当なやつだと判定できなかった。

nと壁でスコアを整える

なにも伸びない。明日やること。整理。スコアの調整。パラ調整。

コンテスト10日目

受理されたときだけ正確なスコアにする？

提出。48.68で10位。あと0.5%伸ばしたい。

初期解は本当にdfsでいいのか？

提出48.791で8位。

usizeを32にするとはやくなるか？dfsを非再帰に？

最終提出上振れて48.46で9位。

終わりに

良かった点

  • 実装する時間を少なくできた
  • 焼きなましに落とし込むことができた。

悪かった点

  • 考察する時間は増えたけど、数学的に理解することはできなかった。
  • コードが汚い。
  • 初期解やスコアの標準化など詰めが甘いところがあった。

Todo

  • 焼きなましの構造体を改良してもう少し使いやすくする
  • Optuna用にコードを書き換えたりするのが面倒で結局手動でパラメータ調整をしたため、Optunaに慣れておく or マクロなどで対処可能なようにする？
  • テストを書く

感想

焼くだけにしかみえなかったので、HTTFらしくない問題だなーと思っていました。実際はもっと奥深い問題だったらしく、捨象して典型問題に落とし込めているのはいいけれど、細部まで考慮しないと最上位には届かないかもしれないと痛感しました。

過去最高順位でやったーという気持ちはあるけれど、満足のいくまで取り組めたとは言えないので今後の課題としたいです。

来年も10位以内に入って本選に行きたいです。

 

AtCoder Heuristic Contest 025参加記録

こんにちは。競技プログラミングをしているssaattooと申します。AtCoder Heuristic Contest 025に参加して 25位でした。

反省、または誰かの為になることを期待して参加記録を残します。

 

 

問題概要

n個のアイテムを天秤をq回使用して、できるだけ均等にd個のグループに分割してください。

図1. seed=2の様子

解法

大まかな解法は以下の通りです。

  1. 初期解を作成する（qによって2パターン）。
  2. 暫定解の最も重いグループから最も軽いグループに1アイテムを移動させる、またはアイテムをスワップすることを繰り返す山登り。
  3. その他の工夫（過去の比較から明らかな比較には天秤を使用しない。など）

これで暫定テストで94.5%程度の点を得られます。

初期解作成パート

まず、qが小さいときについて解説します。d個のグループにランダムにアイテムを割り当てた後、グループをその総和でソートします（d logd回天秤を使用）。

qが大きい場合は、アイテムをソートします（n logn回使用）。その後、最も小さいグループに最も大きいアイテムを追加し、グループをソートします。これをすべてのアイテムを追加し終えるまで繰り返します。これだけでかなり均等に分割することができます。

貪欲パート

1アイテム移動。グループa<グループbのとき、bからaにアイテムcを移動させようとするときにスコアが改善する条件は、a<b-cです（図2左）。この条件を満たすときは必ず移動させます（1回使用）。a>b-cだった場合は、スワップできるかを試みます。

２アイテムスワップ。グループa<グループbのとき、aのアイテムdとbのアイテムcをスワップするときにスコアが改善する条件は、a-d<b-cかつd<cです（図2右）。そのようなdを探してやるとよいです。qが大きくアイテムをソートしているときはc未満の最大のaの要素をdとしました（１回使用）。

解が改善された時はグループをソートしなおしました（d logd回使用）。

図2. 逐次改善の条件（左: 1点移動、右: 2点スワップ）
その他の工夫

qが大きい場合、アイテムがソート済みなのでその情報をうまく使いたいです。ソート済みの情報をそのまま用いた場合、小<大+小などの比較は明らかですが、小＋小<大という比較は自明ではありません。そこで、入力と同じ方法で重さの組を1200個作成して、1200個すべてで成り立つような比較は天秤を使用せず判断できるようにしました。

うまくいかなかったこと

いくつかの比較結果から焼きなましで重さを推定して、多数決で比較結果を予想するということを試しました。左右の差が10%以上あるようなときは99%程度の精度で予測できましたが、遅く、また重要である僅差を予測できなかったので諦めました。

日記

メモなので汚いです。

目標

考察を頑張る。上位が無理そうなら早めに撤退する。

コンテスト１日目

問題を読んだ。苦手そう。

クエリ数2Nがどのくらいきついのかが見当がつかない。天秤に載せた集合の重さの和がある程度特定できるのか、個々の重さが特定できるのか全く分からない。重さの推定は指数分布からあり得そうなように予想すべきか。

重みが正確にわかっているとき、厳密解は求められるのだろうか。dpとか？とりあえず山登りで高速にそれなりのグループ分けはできそう。

一つ一つの大小関係はn logn回の比較回数で求められる。あまったら適当に２個１個の比較をして、それを満たすように重さを生成。山登りでグループ分けを計算。時間が無くなるまで生成と山登りを繰り返して、平均スコアが最も低くなるようなグループ分けを出力。

ソートができないなら、２個を１個にまとめる。

上の方法を実装して初提出。65AC35WAで49%143位。WAはqがn lognより小さいときに無視してソートしているから。余った回数は無駄にしている。方針が違いそう。

明日すること。最初にいくつかの商品を塊にできるようにする。余った回数を有効活用し、その結果にあう重みを生成できるようになる。

コンテスト２日目

最初にd個に分割してソート。最大グループから最小グループに１個移すのを繰り返せばよくなる？ある商品cを移す場合、最小グループ<（最大グループ-c）なら改善する。

上のものを提出。4WAで88%40位。

バグを直して0WAで91%29位。

最大グループを最小化すればいい？

局所解っぽいのにはまると脱出できていない。適当なswapは意味があるのか。

グループa, bがa<bでそれらの要素caとcbがca<cbで(a-ca)<(b-cb)ならswapで改善する。１点移動では受理されない場合でも受理される場合がある。これは１点swapである必要はなく、何個かずつでも可能。

１点swapを実装して96%12位。

最大と最小で交換をできなくなってしばらくしたら最大グループを別のでも許可するようにして96.89%5位！

乱数で作っているので、既に比較したやつを比較しているかもしれない。hashで重複除去してとりあえず無駄をなくそうと思う。

qが小さいとき最初のグループのソートいる？２つの大小を判定すればそれでよくないか。

場合によっては、クエリをやりきってもその情報から改善できるかも。

既に探索済みのやつを比較しなくしたやつを提出。97.1%で7位。qに余裕があるやつはほぼどうしようもないくらい良い解が出てそう。

比較結果から合法な重みを生成して山登りは無理があるのかな。時間を有効活用したい。

明日すること。多対多のswapを実装。余った時間の有効な使い方を考える。qが小さいときの良い方法を考える。

コンテスト３日目

既存の比較結果から他の比較結果を計算してみる。実装したけど悪化。ミスってないことを確かめたけど、スコアにはほぼ影響なし。多対多のスワップも改善せず。

統計取る。スコアは重みを知っているときの焼きなましをbestとする相対評価の方が良さそう。けど焼きなましが貪欲に負けているっぽい。

全ケース11人に負けている場合、現在の534人の提出者数だと97.9%だから、苦手なケースがあるということ？

統計取った。横軸がlog((q-最初のソートにかかった回数)/n)、縦軸が対数スコア。やっぱりqが小さいケースを何とかした方がいい。log((q-dlogd)/n)が閾値以下のときはソートしない方がいいのかも。

ｑ小さいやつはソートしないようにしたら悪化した。

n個をソートするのではなく、上位n/2個下位n/2個を把握できたら便利かも（nth_element?）。まだ変更していないブロックから２個選び、小の小と大の大のswapが比較０回でできるから。大体２ｎくらい比較しているから無駄っぽい。

ordのソートはまとめてでもいいかも。比較無しでswapできるやつがあるなら優先した方がいいかも。

qが大きいときは、ｎ個をソートして、空のグループに小さいグループから詰め込んでいったものを初期解にしたら微増して97.0%で11位。

クエリ回数を使い切った後も、各グループ１回は小さいグループの比較済みの小さいものとswapすることができる。いやこれは嘘。悪化する場合もある。

ｑごとに提出して苦手を把握してもいい。

コンテスト４日目

１個と１個同士の推移律を実装した。そんなに効果なし。

高速だから、ハイパラを入れまくってoptunaを最後にするべき。

qn<1.7のみ提出で19ケースで18.176%。１ケースあたり95.6%で苦手ぎみではあるけれど思ったより高い。qn>4.0のみで19ケース18.37%。1ケースあたり96.6%。

qを10000回に増やしてみたらスコアは4倍くらいになった。効率のいい探索が必要。

一つ一つをソートしたものをw0,w1,..、としたときの差分di=wi+1-wiを求めるのはどうか。差分があれば焼きなまし的にできるかもと思ったけど。

かなり小さい＋かなり小さい＜かなり大きい、みたいな嘘情報も事前にあたえたら効率よくなるかも。

現在のスコアをmax block - min blockと近似すると、そのスコアはmax blockとmin blockに含まれない物で二分探索でlognで見積もれる。破壊する前にスコアを見積もって、破壊して貪欲後にスコアを見積もる。これで局所解から脱出できる？w0未満は計測できないことに注意。

コンテスト５日目

kickがうまく動作しない。

小さい2d個くらいは（それだけはソートして）探索中はブロックに含めなくて、最後に降順に追加するのは。

ソートして降順に小さいブロックに追加していく初期解が強すぎるから、qが小さいやつにもこれを適用したい。

焼きなましで重さを適当に作った。評価値は正解した数で９割くらい。これは未知の比較に関しては７割だった。これって焼きなまし解を100個作って多数決したらかなりの確率で正解するってこと？99%で成功するようになったけど、1%の嘘のせいでそれでも悪化する。

コンテスト６日目

意見が100%一致するのはクエリ中９割くらいで、そのほとんどのケースで100%の精度を達成していた。つまり、わからないクエリだけqを使用してほかは予測ですれば実質qを10倍にできるということか？

もしかしたらほぼイコールみたいなやつは把握できていないのかも。→その通りで、10％以内の差を区別することが難しかった。よってこの解法は忘れるべき。

提出。95.77%で16位。qが小さいときを何とかしたい。qを半分近く消費したときに焼きなませばどのくらいの精度が出せるんだろう。

コンテスト７日目

qn<1.7のみ提出で19ケースで17.822%。１ケースあたり93.8%。苦手らしい。

パラメータ調整してもあまり伸びそうにないからやる気が出ない。いい改善が思いつくのにかける。

コンテスト８日目

2点swapは大グループの要素未満の最大の要素でするのが貪欲としては最適だと気が付いた。いや最適ではないか。１％くらい改善。

提出。95.40%で21位。

q小さいときでも使える効率のいい方法が欲しい。

sympyというものを見つけたけど、これは役に立ったのだろうか。

コードを整理したらスコアが悪化した。なぜ。

コンテスト９日目

パラ調整して94.90%で20位。

終わりに

良かった点

  • プロトタイピングがうまくできた。
  • あたり方針を引くのが早かった。

悪かった点

  • 2日目からほとんど改善できなかった。
  • 小手先改善にばかり時間を費やしていた。
  • パラメータ調整が雑。

順位表から粗点の差がわからなかったのでずっと手応えがないまま問題を解いていました。おそらく過去最高順位と初橙パフォーマンスですが、実力がついたとかではなくよくわからないまま終わりました。最初の方が順位が良かったからなんとか食らいつきたかったです。

わかったこととしては、私がプロトタイピングが上手になっていることで色々な方針を試せるようになってたことです。それは嬉しいです。

今回のような貪欲や推定問題ではなく、純粋に実力バトルになりやすい焼きなましで橙以上パフォをとれるように頑張ります。

windowsでDockerを利用してflamegraphでRustのプロファイリングをする

競技プログラミングのマラソンという分野でRustプログラムのボトルネックを探したかったのですが、windowsにはRustの良さげなプロファイラツールがなさそうでした。なのでDockerを利用してlinuxで動作するflamegraphを使います。

 

手順

Docker desktopのインストール

インストールします。

Docker imageのビルド
  •   Dockerfile 
    FROM rust:latest
    RUN apt-get update && apt-get install -y \
        linux-perf \
        linux-headers-amd64
    RUN cargo install flamegraph
    WORKDIR /profile

上のDockerfileを作成して。それが置いてあるディレクトリで

docker build -t rust-profile .

を実行します。

プロファイラの実行

Cargo.tomlに以下を追加します。

  •   Cargo.toml 
    [profile.release]
    debug = true

以下でプロファイル結果が得られます（パスなどは変更してください）。

docker run -it \
  --name profile-container \
  -v $(pwd):/profile \
  rust-profile \
/bin/bash -c "cargo flamegraph --bin=a -- ./target/release/a < tools/in/0000.txt > out0000.txt"

こんな感じに可視化されます。

終わったらコンテナは消してください。

 

終わりに

記事の内容は間違っていたりもっと良い方法があるかもしれません。

第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）に参加して 44位でした。

反省、または誰かの為になることを期待して参加記録を残します。

 

 

問題概要

水路が通った正方形の圃場が与えられるので、土地の利用率が最大となるような栽培計画を立ててください。作物の植え付け時期は早めても良いが、収穫時期は固定です。植え付けと収穫には農機が必要です。農機は水路と作物を跨げません。

解法

大まかな解法は以下の通りです。

  1. 圃場全体に張り巡らされた道を作る。
  2. 道以外の部分をグループに分割する。各グループは必ず道に接するようにする。
  3. 入口から遠いグループから作物を植えていく。同じグループで栽培するのはdが同じ作物に限定する。
  4. その他の工夫（初ターンは全て植えきる。終盤はグループを無視する。道も植えられそうなら植える）
  5. 1-4を乱数でブラして時間いっぱい繰り返す。

これで82%程度の点を得られます。

1-3についてもう少し詳しく書きます。

seed=1の結果。Score=847175
道作成パート

まず、道は作物を栽培できる期間が短いため、道を大きくすることはスコアの減少を招きます。一方で道を大きくすると、2で作成するグループのサイズが小さくなるため道以外の利用効率が良くなります。

このトレードオフ関係のもとで、道から最も遠い点との距離がx(5-10)以下となるように道を作成しました。作成アルゴリズムは以下の通りです。

  1. 入口を道とする。
  2. 道から最も遠い道でない点をダイクストラで求める（bfsでなくダイクストラを用いているのは、乱数を加えたり曲がることにコストを与えたりしているから）。
  3. 距離がx以下なら終了。
  4. 最短経路の内、遠いほうからx個以外の点を道に追加する。
  5. 2-4を繰り返す。

道（青）から最も遠い点（赤）への経路（緑）（図左）。経路を取り込む様子（図右）
グループ分けパート

道に接している道以外の点をそれぞれグループの代表とします。グループサイズが小さい順に、周囲のどのグループにも属していない点を取り込んでいきます。

このグループ割り当てのスコアをsum(グループサイズの２乗)としました。グループのサイズが均等な方が土地の利用効率が良くなると考えたからです。

作物決定パート

各ターン、入口から遠いグループから栽培する作物を決定していきます。

あるグループに栽培する作物は全て同じdであると制限しているので、dを決定したときの利用率は計算可能です。そこでターンtにあるdを置いたときの評価値を evalscore = (利用率)\times 60+\sqrt{d-t+1}として、最もよいdを植えました。

日記

メモなので絶対に見ないでください。

目標

rustを使う。橙パフォ。よい立ち回りをする。問題の性質をよく考える。安易に焼きなましに走らない。散歩、睡眠、お風呂などのぼーっとする時間を確保する。最初の２日で案をすべて実装する。スタートダッシュする。

コンテスト１日目

問題を読んだ。アスプローバだから固い複雑なものだと思っていたら面白そうな問題だ。得意そうでやる気がでる。

自分より小さいDか空マスを通って入口に到達可能なら合法。それを使うのが素直な貪欲かな。空マスが到達不可能になる置き方は必ずしも無駄ではないと思う。

ビームサーチについて。単純に考えると時間の軸があるので有効そう。

焼きなましについて。各作物をマスに割り当てたときの最もよいオンオフ（栽培するかしないか）や、合法な状態を保ったままの遷移が決定できれば焼きなましを実装できると思う。解空間をなめらかにする必要がある。

時間軸を気にするならばビームサーチが有効そうだけど、T=100なのでahc013のようにトップは焼きなましの方を採用しそう。

とりあえず乱択をする。1割ちょっと。とりあえず次はビームに直してみる。

幅1000のビムサを試してみたら、めっちゃ時間かかって乱択ほぼ変わらないくらい。

takumiさんが早い段階で上位にいる。rhooさんも。

lowlink試してみるか。lowlinkで2割くらい。

置くものをsが10ターン以内のもののみにしたら点数が倍くらいになり4割。隣接した置かれたもののdは近いほうがいいのだろうか。これはあまり関係なかった。

各ターンにおいて、dの降順においていったらかなり伸びて６割。

入口から遠い順に探していくとぎちぎちに詰められることを発見したけど、なんかバグっているのか空白が目立つ箇所がある。

コンテスト２日目

遠くから詰めていくのがバグったままなので、あとでやる。一気に増えたり、全く置かなかったりしてる。

乱択で詰めていくと、農道のようなほぼ栽培しないマスができてそれが80~100マスぐらい占める。他のところを完全に利用できても８割くらいしか取れない？スコアは土地の利用率と同じだよね？他のところは8割くらい。

ダイクストラで合法判定していたのをdials alogrithmに変更で微高速化。時間100倍にしても伸びないから高速化は意味ないけど、ビームか焼くならもっと高速な判定が必要っぽい。

そもそもダイクストラみたいに全体を見る必要がなく、置くものの周囲とその点が関節点であるかどうかだけで判定できることに気が付いた。10倍以上高速化した。たぶんlowlinkがボトルネック。

幅1000、置いたものの生スコアで評価するrhoo式ビームを実装。めっちゃ遅いけど66％まで伸びた。強いかもしれないけど、もう少し乱択でいい貪欲を探す必要がありそう。

致命的なバグがあったことを発見し修正。遠くから詰めていく貪欲で65%、幅100のビムサで７割乗った。普通のも7割。

lowlinkの差分計算がわからないので、ダイコネかundo機能つきunionfindを実装してみるか。

置くものをs==turnのもののみにしたら伸びて73%。遠い順に置くやつが決定的なので爆速で74%。距離に乱数を足すみたいのでブラして75.8%。

置くところは遠いところではなく、差が小さいところの方がいいのではないかとふと思う。その通りで 76.7%に伸びた。

提出。385で15位。手元では76.9%。サンプルが大きく偏っていることはないし、80%超えるまでは提出を控えよう。

明日は評価値が高いものを高確率で選ぶようなものにしてみる

コンテスト３日目

関節点を特定の条件で差分計算できるようにした。２倍くらい高速化された気がする。rustのパフォーマンスプロファイラの使い方がわからないからどこがボトルネックか調べられない。

あるターンに置くものを、貪欲を初期解とする置く個数を最大化させる焼きなましで変化させることはできないか。遷移はそのターンに置けるものを削除、置く、移動、swapなど。焼きなましやってみたけど微妙だった。

各ターンで何回か試して最も置ける置き方をするのも微妙。

cropをdの降順から調べていたのを、1000秒焼いてみる。ほんのわずかに伸びる。

d-sが小さいやつは近くに置いた方がいいよな。

今はs=turnのもののみを見てそのターンにおけるだけ置いているけど、数ターン後まで見て最大化したい。特に最初数ターンはすべて置ける空間があるので、dの大きさ順に並ぶようにしたい。

三圃式農業みたいにぐるぐるさせるやつ微妙だった。

コンテスト４日目

距離を空白マスでのbfsにしたら少し伸びた。これ初期値のみ乱数であとはそのままだけど、初ターンの置き方によってかなりムラがある。

最初数ターンはトヨタ決勝のように置くとよいのでは。小さいやつを手前に大きい奴を奥に置く。dがこれくらいのときに距離がこのくらいがいいという配列を用意しておいて、それをもとに各マスの評価をする。近すぎるとあとに置くのが大変なので、それより近いとペナルティは多めにする。

最初５ターンはすべて埋めきるような別の埋め方にする。これが効いて78.2%。５ターンのではなく一つでも失敗するまでにターンを変更する方がいいと思う。した。

最初のターン以外は１つのターンしか見ない貪欲だけど、数ターン先まで見て良いように置きたい。１ターン先まで読むやつ遅いけど78.5くらいまで行く。

コンテスト５日目

今までturn==sの時にしか置いていなかった。とりあえず最初のターンだけターン無視しておいたら78.8%。次ターンのものを考慮するようにしたら20倍くらい遅くなったけど微増。

トップは87%とっているけどどうやっているんだ。

自分のd以下のものを通って空白に到達可能なら合法としていたのを、同じdのみにしたらめっちゃ上がって79.7%。

最初の距離に乱数を加えたのを沢山試すことで時間を使っているけど、もっといい時間の使いかたはないものか。距離への乱数を山登りにするとか。

コンテスト６日目

木を作って葉に置くのを試してみたけど、たいして早くならなかった。

後ろのターンから考えることはできないか？後ろから考えると、置いた時点で点数が評価できるのでビーム向きか？

道以外のところが９割以上になっていて改善がむずいので、道の部分を５割くらいまで上げたい。

入力生成パラのdごとに調整？幅が大きいときは９割くらいでるのか

コンテスト７日目

とりあえず提出。39.95で46位。optunaでパラメータ調整してみたけどたいして意味なさそう。

上位との違いはいいドンよくを見逃しているか、時間の使い方が下手なのか。逐次改善はできないのか。

あるターンだけ評価を逆にする山登り。あるターンのあるマスに置かないようにする山登り。

道を作り、その他sとｄが同じブロックで詰め込めばいいのでは。

木を作るパート無駄が多いけどとりあえず動くものができた。幅が大きいやつでは70を切るくらいの大きさ。改善できる点としては、壁側を通ると有効活用できる範囲が狭くなるので、距離が同じなら中心側が良い。なんとかしてシュタイナー木に落とし込めないか。

グルーピングパートも作った。グループサイズ15みたいな大きすぎるやつがあるから、焼いたり乱択で何回か試した方が良さそう。

道作るやつ、適当な調整なのに79.5%くらい出ている。

rustでv.shuffle().iter()みたいなのほしい。

80%超えた。提出50位。

明日やるべきこと。

  • 木の作り方をもう少し厳密にする。
  • ブロックに詰め込むdの値の評価値を考える
コンテスト８日目

82%乗った。のこり時間でなにができるかな。

終わりに

良かった点

  • 複数の案を素早く実装して試せた
  • 貪欲で上位と同じくらいの順位をとれた

悪かった点

  • 上位の点数から解法を読めなかった

最近貪欲にこだわっていたのもあって貪欲解法を高めることができました。焼きなましまでもっていきたかったけど、今回の問題は貪欲から焼きなましへの発展がつながっていなかったようなので仕方ないと割り切って、これからも貪欲を重視したいです。

焼きなましはあるものを決めると栽培計画が自動で決まるような同時に最適化できるタイプのものだったようで、かっこいいのでこれはぜひ習得したいです。

今回ahcで初めてrustを使用しました。コンパイルエラーと実行時エラーで苦しむ時間がほとんどなくなってすごい使いやすかったです。これはむしろ短期コンで役立つ性質ではないかと思いました。

いいかげん橙以上のパフォーマンスを出したいです。

MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）に参加して 41位でした．

反省、または誰かの為になることを期待して参加記録を残します。

 

問題概要

正面、右側から見たシルエットを満たすような立体を複数のブロックを用いて作るパズルがある。立体パズルが２個与えられるので、同じブロックを使って２個の立体パズルを完成させたい。なお、ブロックは大きいほうが良い。

図１. seed=1 の様子

https://atcoder.jp/contests/ahc019/tasks/ahc019_a

解法

基本方針
  • パズル（シルエット組）１とパズル２からランダムで座標と向きを決めて同時にブロックを操作することで同一なブロックを配置する。
  • ブロックの短縮・削除・延長を組み合わせたものを近傍とする部分破壊焼きなましを行う。
  • スコア計算はサイズ２以上のブロックをサイズで降順ソートし、順番にシルエットの完成に寄与するなら採用する。それでもシルエットが完成しなかった場合にサイズ１のブロックを追加する。最終的に採用しなかったブロックはすべて削除する。
ブロックの操作について

まず、無からサイズ２以上のブロックを生成するときは、パズル１とパズル２からランダムに座標を選択し始点とします（始点と言っても操作で始点が無くなることもあります）。次にブロックを伸長する際の向きを決定しますが、パズル１は向き０としてよく、パズル２の向きはあり得る24通りからランダムに選択しました。ブロックを伸長・短縮するときはこの向きに従い操作します（図２）。

図２. ブロック生成の方法

ブロックの伸長は座標をランダムに選びbfsをして可能な限り大きくしました。ブロックを伸長する時にはブロックと新たに加えられるブロックに辺を張ることで、ブロックのサイズを計算できるようにしました。

ブロックの削除は、ブロックが木構造なので枝を切ります。正確には、座標をランダムに選択し、その座標に存在するある１辺を辿っていけるすべてのブロックを削除しました。他の方は始点を固定しているような気がするのですが、これで始点に縛られずにブロックの操作ができます（効果はなさそうです）。

焼きなましについて

近傍は３つ用意しました。

  1. （１サイズ分短縮）×複数＋（生成 or 伸長）×複数
  2. （枝を短縮）×複数＋（生成 or 伸長）×複数
  3. （１ブロック削除）×１＋（生成 or 伸長）×複数

温度は低めに設定しました。イテレーションは数十万回でした。

日記

自分の考察メモとして書いていたので、読み辛い可能性があります。

コンテスト１日目

忙しい．

コンテスト２日目

忙しい．

コンテスト３日目

問題を読んだ．難しすぎないか？

４つのシルエットのうち1つをZ軸に沿ってD個に分割．それらのZ±1のブロック間でブロックを受け渡しする．選んでいない方のシルエット組でこれらを配置できるか判定する？

コンテスト４日目

自由度が大きすぎて何も思いつかないよ．

サンプルプログラムはブロックを置くことができる最大の空間．一方のペアでつくった合法なブロックは，もう一方のペアでは合法となる場所が少なくて全探索できたりしないかな．

方針案

  1. サンプルプログラムのブロックをペア１とペア２でそれぞれ繋げる/破壊してペア間で類似度の仮のスコア計算する焼きなましorビームサーチ．
  2. ブロックを最初に何種類か作っておいてそれからいい組み合わせを探す．
  3. ペアとペアの空間を繋ぎ合わせてdfs/bfsでブロックを作る．

方針１をとりあえず実装してみようと思うけど，初手焼きなましは悪いパターンだね．この問題での貪欲って何だろう？

方針１を実装するにあたって必要なのは，ブロックが同一の形か判定する方法．Graphoreanでは次数列をソートしたもので判定していた．炭化水素の命名方法みたいに一意に決められないか？完全に一致していなくても似ているかどうかを判定できないと焼けない気がする．それとも同じ形のブロックを伸ばしたり縮めることで一致しない類似度は無視できるようにするか．

コンテスト５日目

忙しい．バグっている．

コンテスト６日目

バグが取れてようやく初提出で106位．ブロックを結合・分離する焼きなまし．

ブロック組を作った後にシルエットをつくるのに不要なものを除去していないからそれを除去したら倍の点くらいかな．焼きなましのスコア計算が除去前だからそこも直す必要がある．ブロックの個数が多すぎる（seed 0 で12個）からブロック数を制限する必要があるかも．焼きなまし時にシルエットが完成しているかどうかも判定しておいた方がいいかな？ブロックの破壊からのどこかを始点にして伸ばせるだけ伸ばす部分破壊焼きなましもよさそう．

２回目提出で8Bで36位．ブロック数の制限とスコア計算を改善した．最終20位は今の40Bくらいは必要だと思う．Dが小さいときは10^8台のスコアが出ているからせいぜい改善して２～３倍くらい．Dが大きいときの改善が重要だろう．

次はseed 0が50を下回ったら提出しよう．改善点としては，Dによってブロック数上限と温度を変更する．始点と向きを決めたらbfsで最大まで伸ばすのがこの問題の貪欲かな？部分破壊とこの貪欲をセットにした遷移も追加したい．結合と分離をセットにした遷移も．初期の動きが強く影響しそうだから多点スタートが必要かも．最終出力でブロックの選択を体積が大きい順にしているけど，0.1秒くらい焼けば少し改善しそう．

コンテスト７日目

1 add 1 remove, 1 add 2 remove, ブロックを消して貪欲に作り直す近傍を追加したけど全然伸びない．

best_scoreが一定時間更新しなかったら部分破壊するようにしたのを提出．11Bで35位．

初期温度を３から１にしたら絶対スコアは良くなったけど相対スコアは下がった．最後に調整する．

もし両方にサイズ１のブロックがあったら対応させる．→対応させた．

部分破壊の所がバグっていたので修正して提出．15Bで24位．seed 0 もたまに50を割った．

何度も使う関数内の配列はstaticにする．初期化不要の配列にするのも検討．100倍高速化したらもともとスコアが大きいものは２～３分の一くらいになるから高速化も重要かも．

良さそうな改善が尽きてきたので実行時間を延ばした解から学んでみる．図３の右が実行時間を100倍にしたものであり，点も６割ほどになっている．大きすぎるブロックが無くなり，ブロックサイズは大体均等になっていることが観察できた．大きさ制限は難しい気がする．なんとか上手い具合に均等にする方法はないものか．

図３　seed 1 の実行結果．左が通常の実行時間，右が100倍の実行時間

D毎にブロック個数の制限を調べる．

ブロックを一つ破壊した後に，既存の使用済みブロックから伸ばせるだけ伸ばす近傍はどうか？ある空間に含まれるブロック関連のものをすべて消して再生産する近傍は．

実行ごとに２倍ほど点数にムラがあるのは何でだ．

コンテスト８日目

estieのやつに似ているからその時の解説を読みなおそう．合法手の計算がボトルネックになっていたらしい．点数が安定しないときは状態を複数持っておく．このときは１長方形の追加，削除は良い近傍ではなく，部分破壊貪欲が強かった．

ある(x, y, z)の方向dirの辺を使って到達可能なブロックを全削除する近傍．これはブロックが分断されないよね？ 使用済みのブロックから伸ばせるだけ伸ばす．

部分破壊した後の再構築は一つの始点から伸ばせるだけ伸ばしていたけど，そうすると一つのブロックばかり大きくなってしまうので，何回か一つ伸ばすのを繰り返す方が平均的に大きくなりそう．

提出153->1489で悪化．

コンテスト９日目

やはりブロックサイズに差があるもののスコアが悪い気がする．大きすぎるブロックのaddを禁止するか．最小サイズの５倍以上になるのを禁止とか？毎回bfsで大きさ計算するのは重そう．

どこを変えたか覚えていないほど些細な改善をして提出．17Bで29位．

キックをイテレーション回数から時間に変えた．18.4Bで28位．

コンテスト10日目

夢でブロックのedgeの向きを変更する方法を思いついたけど意味なさそう．

キック時に一つのブロックを全破壊していたのを，１～４ブロックの一部分を破壊するのに変更して提出．18.14B 30位→21.2Bで27位．

ブロックのサイズを保持できないかな．できればadd, removeはコピー・計算前にrejectできるんだけど．

サイズ２のブロックは向きとmappingを変更できる．

実行時間を10倍にしたら点数が半減するらしい．案が無くなってきたしそろそろ高速化の時間か．

コンテスト11日目

(x, y, z) は事前に合法なものを準備．ブロックは木構造なのでhoumon配列を用意せずにmae座標を持っておけばオーケー．addたくさんする近傍．

サイズを事前に計算していても，存在するブロック全てがスコア計算に使われているわけではないから事前にrejectできないことに気づいた．removeしてもスコアに影響しないものもあるのだ．

addでスコアが悪化している試行がある．厳密解ではなくサイズで降順sortして順番に足しているからそうなるのだろう．スコア計算を高速で正確にできるかな．addを問答不要で受理したらiterは伸びたけどスコアが下がった．スコア計算を見直す．まずソート配列を適当にスワップした点数を調べる．

コンテスト12日目

add, removeはいちいちコピーせずにシミュレーションすればよい。空間破壊。

近傍の割合をoptunaで何とかしたい。

一つ一つadd, removeする意味ってあるのか？スコア計算するときはもうaddできない状態でないといけないのでは。remove系をしてから追加できなくなるまでadd系をする近傍のみにした。19.14B31位から16.89B36位に下がった。ローカルでは上がったのに。時間経過とともに変化する部分を小さくするようなパラメータ調整が必要。あとラスト少しはいままでの近傍のほうがいいかも。

コンテスト13日目

takumiさんのを参考にしてoptuna。optunaで近傍の割合を調整しようとしてみたけど、100ケース100トライアルじゃお手製の割合に全く勝てなかった。14近傍の割合の和が100％になるようにしたいけど、下のコードみたいにしたらいい感じにサンプリングしてくれなさそう。

p0 = trial.suggest_int('p0', 0, 100)
p1 = trial.suggest_int('p1', 0, 100-p0)
p2 = trial.suggest_int('p2', 0, 100-p0-p1)

コンテスト14日目

Dが大きいときは7.cppが優れているので組み合わせたのを提出で18,3Bで36位。たぶん暫定テストはDが小さいのが多い。

optunaに温度を調整させてみたけどお手製のものと全く同じ値がでてきた。

近傍の割合を72ケース120トライアルで調整したら過学習？で悪化した。これを参考にした。

https://optuna.readthedocs.io/en/stable/faq.html#how-do-i-suggest-variables-which-represent-the-proportion-that-is-are-in-accordance-with-dirichlet-distribution

最後に使わないものをすべてremoveしてaddする。

計算に使わないブロックをすべて(確率でもいい)消す近傍。ブロック個数がDになるまで破壊する近傍。

計算に使わないブロックをすべて消す近傍（4%）を追加したらそこそこ伸びた。20.3Bで33位。

すべてのスコア計算時に不要なブロックを除去するようにした。そうすると１個ずつaddするのを繰り返す近傍の遷移確率が低くなったのでそれらを消した。21.3B 32位。

なんかDが大きいほうがスコアいいらしい。

コンテスト15日目

ブロックが既に置かれているときの厳密解が最小費用流で求まると考えたけど，コストが１流量あたりらしいので無理．そもそもブロック数が高々20個なのでbit全探索で行けるか．bit全探索だと一回のcalc_scoreで9msかかっている．

僅かに高速化して22.3Bで37位。最終日は配列を１次元にしたい。あとブロック個数の最大値調整。

コンテスト16日目

多次元配列を1次元にしたらイテレーションが1.5倍くらいになった。最終提出22.2B, 45位。

終わりに

良かった点

  • 結果はともかく、立ち回りが理想に近かった。
  • 役には立たなかったけど初めてoptunaを使えたり、並列実行の仕組みについてほんの少しわかったり技術的な成長があった。

悪かった点

  • 焼きなましという初歩的な方針まではスムーズにいけたが、それからの考察や改善ができなかった。
  • optunaを有効活用できなかった。

非常に自由度が高い問題で途方に暮れました。たまたま焼きなましという型にはめられたからましな順位になったけど実力不足を感じました。今回でレーティングが黄色になりましたが橙色になるためにもっと考察を頑張りたいです。