0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴6年半のかえでです。
これは、2026年6月22日日曜日午後7時から11時まで開催された、4時間の短期コンテスト「AtCoder Heuristic Contest 067」の参加メモです。
トップのスコアには全く届いていないのですが、自分の振り返りとして参加時に考えていたことを書きたいと思います。
1.問題概要
- スイッチと扉を設置して、勇者が玉座にゴールするのができるだけ遅くなるよう移動距離を最大にする
- スイッチはK種類（K=10で固定）あり、スイッチiを押すたびに、対となる扉2iと2i+1の開閉状態が反転する
- 盤面はN×N（N=20 で固定）
- 扉の設置上限はM（M=50で固定）
2.最初の提出
ランダムで扉とスイッチを設置するACする解を提出。158212339点を得ます。
全く遠回りをさせることができず、最短でゴールに進んでいました。順位表には同じスコアが並びます。
3.考察
- 0から9までのスイッチを順に踏むように、スイッチを踏むと扉が開いて次のスイッチを踏めるようにする
- スイッチを壁側に置いて、扉をスイッチの前に設置する
- 2秒使って乱択。ベストを出力する
偶数番号のスイッチと奇数番号のスイッチが盤面の両端に来てできるだけ距離をかせぐ感じ。意味のない扉がまだいっぱい設置されていました。
4.扉で邪魔をする
ランダムよりは関節点を試した方がいいのかな。
5.トップとの差を見る
自分の平均ターン数：約 1,360 ターン
トップの平均ターン数：約 49,180 ターン
うーん、差が大きすぎる。
複数ループする解が偶然できた。
どうして？
3枚扉が効いていそう。
トップの平均ターン数：約 63,500 ターン
トップとの差がどうしてこんなに開いているのかわかりません。
改善案を探すため、ビジュアライザを見る時間が続きます。
50個の扉を使い切っていなかったので、
- 余った扉を蛇行に使う
ことにします。少し上がりました。
6.コンテスト終了・結果
何もつかめないままコンテストが終了しました。
結果です。
得点は1,028,057,500点、順位は736人中263位、パフォーマンスは1578でした。
Ratingは時間減衰に負けて、前回より3下がり、2209になりました。
7.復習
さて、コンテスト翌日です。気を取り直して復習をします。
Xではコンテスト終了後に、聞き慣れない「9連環」、「グレイコード」というキーワードが飛び交っていました。キーワードを元にコードを改善します。
まずは「9連環」解法に取り組みます。
10連環は55枚必要とのことで、扉の数の上限50枚では足りません。9連環は45枚でできるということだったので、9連環を作ります。
100テストケースを試すと、できたりできなかったりします。seed70ではスコア10079285が出ていましたが、平均は3936377とイマイチです。
そこで、できなかったときには、コンテスト中に使っていた貪欲解を使用することにします。平均は8045151になりました。
提出をします。本番188位相当のスコア、1,256,058,730が出ました。パフォーマンスは1753相当です。
スイッチを一個使っていないのがもったいないので、扉を共有することで10連環にできないかを試します。
seed0ではスコア9787739が出ました。17678ターンです。
実行制限時間を20秒に伸ばしてみると、100テストケースのスコアは、835万平均から875万平均に上がりました。高速化を行います。
少し良くなりました。
「グレイコード」解法だと結果が変わるのでしょうか。maskを使って評価します。
100テストケースの平均は863万になりました。
実行時間を20秒に伸ばしてスコアを見ます。100テストケースの平均は893万になりました。とはいうものの、これを2秒におさめる方法がわかりません。
ここまでやってきて、ふと、上のビジュアライザに目をやります。
あ、と思いました。
勇者が通らないルートに扉を置いていました。一番上の左半分です。
意味がないですね、これ。
修正を試みますが、思ったようにうまくいきません。
それでも少し改善したのでプログラムを提出します。結果は少し良くなって本番169位相当の得点が出ました。
100テストケースで一番良いスコアはseed37の10536830、29712ターンでした。
出力を見ると、扉がまだ余っていました。
まだまだ改善できそうなものの、そろそろ寝たいと思います。
というわけで、一旦ストップして、復習の続きはAHCラジオを見た後に行いたいと思います。
8.復習2（後日更新予定）
一晩寝て起きたら、適当なことをやっている気がしてきました。AHCラジオを見た後にちゃんと復習します。
