MON.T+α ProgrammingRoom

MON.T+α Programming Room

MON.T+αの活動を綴っています。

【PostMortem】HTTF2024 (AHC027)

AtCoder Postmortem

※画像は公式Visualizerよりお借りしています

 

 

はじめに

　この記事は2023/12/01 - 2023/12/10にAtCoderで行われましたAHC027の解法を紹介するものになります。いつもは冗長に書いているのですが、今回はいつもとちょっと違う切り口で、他の人の言及が少なそうなところを中心に書いてみます。（決して時間が取れなくて雑に書いているとかでは）

　気を付けてはいるのですがところどころうっかり打ち間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。

問題の概要

こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「部屋の汚れの平均が小さくなるように掃除ロボットを動かす」という問題です。

問題文はこちら

atcoder.jp

この問題では与えられた各マスの汚れやすさに比例して汚れの値がたまっていくので、汚れやすい所へは多めに掃除に回るのがよさそうという印象を受けます。

最終提出の解法

以下、最終提出の概要です。

言語:go言語

　これはただの好みです。

解法:評価値をもとに1マスずつ動く貪欲

　以下はTwitterで行った解法ツイートです。

 

今回用いた評価値はほとんど同じ方針のものがAHC公式放送で述べられていた(公式放送にて√dにしたら44Mになったといわれているもの)ので、AHC公式放送の該当の解法をご存じない方はぜひご覧ください。（該当の解法以外にもいろいろ述べられていて参考になりました）一応、この先のセクションではそのあたり詳しいことは知らなくても、「最も評価の高いマスに1マス近づく」という貪欲を繰り返していることだけ知っていれば楽しめる内容になっています。

AHC公式放送（該当の解法の前準備は22:30くらいから）

www.youtube.com

　公式解説では各マスの汚れを√dで計算する(本来の汚れを√dで割る)という方法が用いられていますが、実はこれは(現在のそのマスの訪問回数)で割ることで似たような結果が得られるので、こちらを採用しています。このほうが実際のマスの位置関係による行きやすさが若干反映されてよいような気がします。

 

貪欲の限界に挑戦

　もう他の方の解法を確認している方はご存じの通り、このコンテストにおいて貪欲解法には大きな壁があります。というのも、貪欲解法はこの問題の持つ以下の特徴に対して弱いからです。

・道中うろうろしながらコンスタントに成果をあげることが大事

(評価値として、最短経路でないパスを用いた場合にあげられる成果を考慮しようとすると途端に難しくなる)

・かたまって汚れているエリアはとりきれないとすぐに戻ってくる羽目になる

(貪欲では汚れているエリアを分断するように突っ切ってしまうor途中で別の汚れているエリアの目標に方向転換してしまうことがあり、少ししてまた無駄に戻ることになる)

　最終的に順位表の最上位あたりにいる方々のスコアは私の感覚では貪欲では達成できなさそうだな・・・という印象なのですが、貪欲でもここまではこれたよ、ということで一部をここに残しておこうと思います。誰か貪欲でさらに良い結果が出せている方がいれば教えてください。

貪欲における47.7Mの道のり

46~47Mあたりまでは改善の繰り返しで比較的順調だったのですが、そのあたりを超えてからはいろいろ苦しい中もがいていた記憶があります。もがいていた時に一番効果があった「反転テクニック」をここでは紹介します。

最近通った道についた場合に直近の経路を反転する

貪欲で移動経路を決めているときにいちばんよく起こるのが「ここさっき通ったばっかじゃん」パターンです。ということで、これを解消するために経路の反転を行います。

サンプルはseed=1での一場面です。

↑貪欲に評価の高いマスへと足を進めていたところ。botはこの後L(+そのあとにLD)とすすんで取りそびれた大きめの汚れを取りに行きます。

 

↑ところが、このターンの移動はついさっき汚れをとったばかりのところに行きついてしまい、無駄に一ターン消費してしまっています。

 

↑そこで、直近3回の移動を逆再生して、その動きを正式な動きとして改変してしまいます。移動の回数の合計を確認してみると、先ほど無駄に消費してしまった1ターンはなかったことになり、別の場所に移動することに成功しています。

 

↑結果、ここでは1マスの移動の追加だけで汚れの大きな場所の掃除をすることができました。

この後左上へULLと計画します。

 

↑ここで逆再生。（逆再生の長さは5）

 

↑今回は結局距離は縮まりませんでしたが、Lと進んでやり直すことができます。あるいは現在地が変わったので上のマスを取りに行くほうが評価が高くなっているかもしれません。

 

このテクニックは貪欲ベースで47M付近からスコアを改善するには必須のテクニックでした。

現在位置を分身させてしまう

上で述べた反転テクニックを使って大胆に現在位置を分身させてしまうのが有効です。

サンプルはまたしてもseed=1のこの場面です。

↑この場面は先ほどの反転テクニックを使って、移動回数を増やすことなく

 

↑この場面にできることを確認しました。また、最初の場面でU,Rを選択することで

 

↑このような場面にも到達できます。

さらに、最初の盤面→Lからの逆再生→Dからの逆再生を用いることで

 

↑こんな場面にも到達できたりします。(さらにこの場面からRからの逆再生で新しい場面に)

そんなわけで、これらの場面での現在位置の点を覚えておき、これらを距離0の点とします。これにたいして最短経路に対するDPを公式解説同様に行い、移動に都合の良い場面を持ってくることで改善が期待できます。

 

この分身戦法が使える場面は特定のケースでのみということはなく、取りこぼしを回収する際・別の汚れた区域へ移動する際に効果を発揮します。

例として、seed=1の別の場面を考えてみます。

↑この場面では、

 

↑この中から都合の良い視点を選ぶことができるということで、左・中央・右下の取りこぼしや左上の新しい区域への移動などいずれの方針に対しても大きなアドバンテージを得ることができます。

 

お掃除高橋君2号は現在位置を錯覚しているのでデバッグ出力をしてVisualizerを確認すると1マス進む貪欲での道の変わり方が面白いです。(以下はseed=1でのまた別の例)

　意外にもDFSでのこれらの列挙はそれほど時間がかからず（ほぼ全列挙していますが、そもそも厳密に全列挙する必要はない）、手元の実験では最短経路についてのDP のほうが時間がかかるようでした。

 

これら(+諸々)を実装するとかなり貪欲らしからぬ振る舞いをしてくれるようになります。貪欲を頑張ってみたら最終的に行き着くのは貪欲らしからぬ動きという、現実を突きつけられる結果になりました・・・。

seed=5 (注:実際の行動は長さが70000くらいあるので一部分のみを抜粋しています)

改善の余地

　容易に想像できることですが、この貪欲のポテンシャルはそれほど高くないです。特に区域を訪れる頻度の認識が最短路に限定したDPでは甘く、この頻度については反転では対応できません。

　また、反転によって本来訪れる予定だったターンから多少前後していることで若干コストが増えてしまいます。かといって、スコア計算の処理を導入すると出力できる行動の長さが短くなってしまいループのつなぎ目での無駄が無視できなくなってしまいます。（私の解法では各マスの評価の値に(現在の汚れ)/(訪問回数)を入れていることもあって長さが長いほうが強いです。）

　評価値を謎の(軽い定数時間程度で計算できる)見積もり項で修正するorDP部分自体を工夫するなどして上の問題が解消できるなら、まだまだ改善が可能だと思います(いろいろ突き詰めて多分~2%くらいで、それ以上を目指すならさすがにビームを打つか、さっさと経路を完成させて後からいろいろ変形させないと厳しそう)

　そんなわけで、この貪欲はある程度頭打ちになっており、wataさんの順位表を確認してみると安定して最上位陣に敗北しています。（これらの統計データを公開してくださっている方々、いつもありがとうございます）

 

おわりに

　ここまで読んでくださった方、ありがとうございました。今回は高速に焼くのが難しそうで貪欲ベースで頑張ってみましたが、なかなか戦えたのではないかと思っています。一方で最終的に高速な焼きなましにもっていく人たちには歯が立たず、実力不足を感じています。ビームサーチもそろそろまともに向き合っていかないと・・・。

　今回のコンテストのテーマは一度過去に作ってみたいと思っていたいたので、コンテストという形できれいなビジュアライザとともに楽しめたのが嬉しかったです。コンテストの開催に関わってくださっていた方々、他参加されていた方々、楽しい時間をありがとうございました！

 

 

おまけ

以下はコンテスト中・後に思ったことを雑多に書いたものです。

・wataさんの順位表を見ていると15位のtokoharuさんも全ケースのスコア安定してらっしゃるなーと思ってみていたら、チーム戦を疑われるくらい相関が高くて笑ってしまった。

tokoharuさん(15位)との比較

(参考:kawateaさん(13位)との比較。ふつうはこれくらい相関が薄いので、tokoharuさんとは方針が近いのかも？)

 

 

・今回の問題設定では汚れやすさという値としてdが与えられていたが、汚れやすさにオフィス内の重要度を掛け算してやると（隅っこやあまり利用されてない部屋は低めの値を設定し社長室や応接室を高めに設定するなど）、より満足度の高いロボットになりそう。

【Postmortem】AHC025

AtCoder Postmortem

※画像は公式Visualizerよりお借りしています

 

 

はじめに

　この記事は2023/10/14 - 2023/10/22にAtCoderで行われましたAHC025の解法を紹介するものになります。

　初めまして(orお久しぶりです)。参加記を書こうとはてなブログを開くと最後に参加記を公開してからもう半年以上であることに気づきました・・・。この間いくつかAtCoder・CodinGameのコンテストには出ていたのですが、コンテスト期間に大きな用事が入っていたり、短期コンは思ったものを実装してなかったり、はたまたコンテスト終了後参加記を書こうとしているところに用事立て込んでしまったりで書けていなかったんですね。今回のAHCは久しぶりにこれといった大きな用事に被ることもなくがっつり参加することができたため、一度考えたことなどをまとめておこうかと思います。

　このPostmortemは自分自身のコンテスト中の思考を改めて整理するために書いているものでもあるため、解法とともにそこに至った考えなど少々冗長に書いております。見てくださっている方はもし長いと感じたら是非見出しだけを流し読みするだけでも概略がわかるのでぜひ見てみてください。

　一週間いろいろ試行錯誤し、最終的に3位（&初赤perf）という結果になりました！

　気を付けてはいるのですがところどころうっかり打ち間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。

問題の概要

こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「天秤を使って重さのわからないアイテムを袋に均等に分ける」という問題です。

問題文はこちら

atcoder.jp

この問題では

・アイテムの数

・袋の数

・天秤を使ってよい回数

がケースにより異なり、特に三つ目の要素は大小によって問題の雰囲気が大きく変わるので、このケースによる違いを何とかするのが難しいところでした。

最終提出の解法

以下、最終提出の概要です。

言語:go言語

　これはただの好みです。

解法:一番重い袋と一番軽い袋を均すことを繰り返す山登り

　以下はTwitterで行った解法ツイートです。 

 

もう少し詳細を確認していきます。

まず、遷移云々の前に根本的な部分を確認します。

今回の問題は最終的にアイテムをまんべんなく分けられた解を出力するわけですが、Validな解に対して、実際にどのくらいばらつきなく分けられているかを天秤で判定するのはかなり難しいです（天秤はどのくらい差があるかを返さないため）。よって、

・何らかの初期解を与えて明らかに改善するほうへ遷移できないか試す

という方針を基本方針としました。これにより「実際にはどのくらいまんべんなくできているのか分からないけれども多分良い感じの解」に到達します。初期解として、今回はアイテムiを袋i%Dに入れるものとしました。

 

次に、遷移1→遷移2と二種類用意していますが、実装した時系列的にも、本質的にも、基本となるのは二つ目の遷移ですので、二つ目の遷移から先に紹介します。

遷移2 二つの袋を足して2で割る

　いったんアイテムを水とします。そうすると「二つのコップの水を足して2で割る」という操作、何度も繰り返すとかなり速いスピードで均等になる気がしませんか？（多分指数的に収束させられそう）

　ということでこの遷移を採用しました。また、この遷移を行うために、必然的に「重さ（あるいは全体に占める各荷物の割合）」を見つもる必要がありました。この見つもるステップについてはもう少し後で紹介します。

　この操作は、一番重い袋と一番軽い袋で行うと効果があります。ほかでも効果はありますが、他の袋を選んでしまうと二つとも平均より重い袋だったりして効率的でない可能性があります。かといって一番重い袋のアイテムがあまり融通が利かないタイプだったりして早々に局所解にはまってしまうなど、難しいと感じる場面では他の袋を選んだりします。

袋の重さ順はおそらく挿入ソートといわれるもので決定しました。

（重さ順の決定は初回はDlogD回くらいのクエリでできる。重い袋と軽い袋の中身を更新したときは重さ順の再決定に2*logD回くらいのクエリを要する）

よくよく考えるとこのソート方法の部分はいろいろクエリを節約する方法を考えてみてもよかったかもしれません。

　この足して2で割る操作は重さの推定値で行うので、実際には元の時よりならせているかを確認しなければなりません。この部分はほかの方でもよく見たので結論だけ書きますが、袋1を一番重い袋、袋2を一番軽い袋としたときに

(袋1→袋1となる予定のアイテム)>(袋2→袋2となる予定のアイテム)

(袋1→袋2となる予定のアイテム)>(袋2→袋1となる予定のアイテム)

が重さについて成り立っていればよいです。

　遷移2は重さの真値がわかっている場合にはすぐにいい解へたどり着けるのですが、今回のような真値がわかっていない場合にはある程度重さの推定値に確信がないと効果が安定せず、博打になります。特にクエリ数が少ない場合では運の良し悪しでスコアが乱高下してしまうので、これを他提出者のスコアと競わせると一部のケースで大幅に順位を落としてしまいます。

遷移1 一番重い袋から一番軽い袋へ一つ移動する

　遷移2の不安定さを解消するために生まれたのが、この遷移1になります。遷移2が博打タイプとすると、遷移1は着実タイプになります。というのも、この遷移では遷移に成功すると以下の二つのパターンが考えられますが、いずれもある程度大きいメリットがあるからです。

パターン1 遷移したが一番重い袋と一番軽い袋の重さが逆転しない場合

この場合はアイテム一個移動させた分二つの袋を順調に縮められているので嬉しいです。遷移2では軽い袋から重い袋に行った分も合わせると実際にはほとんど改善していない可能性もあるので・・・

パターン2 遷移した結果一番重い袋と一番軽い袋の重さが逆転した場合

この場合はどれだけよくなったかはよくわからないですが、この結果から「もうすべての袋にある程度均等に入っている」あるいは「移動させたアイテムがそれなりに重い」のどちらかであることがわかり、大事な情報が得られる点で嬉しいです。

遷移１ではこのほか遷移に失敗したときにもパターン2のような情報を得られるので、クエリに対してどのような結果が来てもある程度の成果が得られる点で安心です。

　遷移で改善するかの判定は遷移2と同じ方法を採用します。（この場合2つ目の不等式は明らかです）

 

補正1 これまでのクエリで得た不等式をすべて記録しておき、新しいクエリを実行するごとに重さを更新

　おそらく一番重要な補正部分の話になります。クエリは実行したら履歴として記憶しておき、クエリを実行するごとに、以下の修正をこれまでの各クエリに対して行います

(1)現在の重さの予想値について、クエリの結果と合致しているか見る

(2)合致していなかったら、少し過剰に修正する（"<"であれば、例えば45:55くらいになるように対象グループの重さを線形に縮める・伸ばす）

（２）での「過剰」の具合が大きいと重さの予測値は大きく変わり、この具合が小さいと、重さの予測値の変更はある程度穏やかになります。（もちろん、もとが70:30のような予想になっていたときは49.9:50.1のような値に変更する場合でも大きく変わります）

ここで、基本的に自分がクエリが投げるタイミングは

・遷移2の二分割の改善判定

・遷移後の袋の重さ順の更新

の二つなので、改善がうまくいっていくことを考えると必然的にクエリはどんどん真値が50:50に近いものを判定していくことがわかります。そのため、「過剰」の具合はクエリが進むごとに穏やかにしていくのが自然な流れになります。

この穏やかにするはやさですが、

穏やかにするのが早め→多くのケースでいい感じなものの一部の運が悪いケースで修正力が足りない

穏やかにするのが遅め→大きく失敗するケースはなくなるものの、どれだけうまくいっても「過剰」の具合の分だけ重さの推定値がぶれ続けるため、とても良い解（最適解や提出者内1位とかの解）への到達率は低くなる

という難しい問題があり、最終的に安定をとって後者を選択しました。結果的にこれが正解だったのかはわかりません。

 

補正2 これまでに袋にどんなアイテムが入っていて重さがどの順だったかを記録しておき、遷移を試すたびに重さを更新

　補正1の補正方法はあくまで各クエリに対して順番に処理していくだけなので、この操作の後にすべてのクエリの結果に反しない推定値になっているかというとそうではなく、また、このことに加えて、クエリには袋の重さ比較に関しては二分探索で必要だった部分しか入っていないため、袋の重さ順の情報が生かし切れていない雰囲気でした。そこで考えたのがこの補正2です。

　これは（金曜か土くらいの）1ページ目に入ってから入れた補正で、この補正は実装当時あまりうまくいく気がしなかったですが、着実に効いていました。

　補正2は、遷移を試すたびにいくつかのクエリによって推定値が変わるので、これが過去のアイテムの割り当てに対して、重さ順が正しくなっているかを確認します。

 

補正方法が面白いので図で紹介します。（効果の裏付けのないこの補正はだれもやらんやろと思ったら既にeijirouさんが同じような方法を紹介されていました・・・）

1.過去の割り当てに対して、現在の推定値で各袋の重さはどうなっているか調べる

 

過去のアイテム割り当てについて、現在の推定値では各袋の重さが上の図のように予想されたとします。ここで、実際には袋は左が一番重く、右が一番軽いことが分かっているとします。

2.重さの合計値をソート

各アイテムの情報を消して袋の重さの推定値をソートします。

ソート前

ソート後

3.シルエットに合うようにアイテムの重さを縮める・伸ばす

 

補正3 クエリ数が十分あるなら、最初に各アイテムの重い順を調べて、遷移を試すたびに重さを更新

クエリ数が十分にあるなら、各アイテムの重い順は確認したほうが圧倒的にパフォーマンスがよくなります。というのも、最初に重い順を調べておいた場合、山登りフェーズを以下の推定値（多分期待値）から始めることで非常にいいスタートを切ることができるからです。また、補正1・補正2の推定値の変更が適切な方向でなかったときや大きく変更を加えてしまったときは推定値がアイテムの重さ順に反していることが多く、重さ順を知っておくことで的外れな方向に進まなくなり、クエリ数が多くなるほど効果が顕著になります。

アイテムがN個の場合

(1番軽いアイテムの重さ)=100000/N

(2番目に軽いアイテムの重さ)=100000/N+100000/(N-1)

(1番重いアイテムの重さ)=100000/N+100000/(N-1)+・・・+100000/1

 

このアイテムの重さ順による補正は、それぞれをアイテム1つのグループとみなし、補正2の方法を使って遷移を試すたびに行います。

 

山登りフェーズを始める前にそれらしい初期状態・初期推定値を考える

山登りフェーズに入る前に、ある程度いい状態から始められるならそれに越したことはないので考えてみることにしました。クエリ数が大きいときにはあまり大した問題にはならないですが、クエリ数が小さい場合だと基本的に山は登り切れないのでそれなりに効果があります。

まず、全アイテムを二つのグループ（今の推定値で半々と思われる分け方）にします。これに対し、クエリを消費して結果を確認します。

この操作はクエリを使える回数に応じて5回~20回おこなわれ、そのたびに補正1が働きます。

 

重さの順番がわかっている場合は、補正3で述べた推定値と今の補正1がかなり筋の良い推定をしているので、全アイテムをD個のグループ(今の推定値でそれぞれ1/Dと思われる分け方)にし、これを初期解にします。これくらい正確です。

　重さの順がわかっていない場合は、5~20回のクエリでは必ずしも適切な方向に推定が行われておらず、重さ1万以下のアイテムが10万以上で見積もられていたりもします。上と同じように推定値で初期状態を設定しても良いんですが、その初期状態が良いかどうかは博打になります。今回の順位準拠スコアにおいて絶対に避けたいのが「i番目のアイテムをi%D番目に入れるのを初期状態としてシンプルな遷移を繰り返す」というタイプの手法に負けることで、このタイプに負けないためにi番目のアイテムをi%D番目に入れるのを初期状態とします。こうすることで、この初期状態がうまく遷移しやすい場合に大勢に抜かされる可能性を下げています。（なお本当にうまくいっているかは・・・？）

　加えて、重さの順がわかっていない場合は、この初期状態に対して袋の重さ順を確認すると、何となく各袋の重さがわかってきます（直感的にも、特にDが大きい場合には、一番軽かった袋は何となく平均よりかなり軽いことが予想できます）。これは具体的には指数分布の乱数を繰り返し生成することで期待値を求めて、アイテムの重さを縮める・伸ばすという操作を行います。

 

明らかに結果のわかっているクエリは省略する

いくつか、クエリを消費しなくても明らかにわかる結果があります。おおよそ以下の通りです。

・天秤の一方あるいは両方が空の場合（これは逆にクエリを投げるとWAになってしまいます）

・過去のクエリと同一の場合

・アイテムの重さ順がわかっていて、片方がもう一方の上位互換の場合（つまりもう一方の各アイテムに対して、一方に対応するそれより大きいアイテムがある場合）

これらの場合はクエリを消費せずにその結果を利用します。

おわりに

　ここまで読んでくださった方、ありがとうございました。久しぶりにがっつり取り組めたのもありますが、ratedのAHCでここまでのパフォーマンスが出たのは初めてだったので自分でもびっくりしています。CodinGameといい、もしかして対人要素が得意なのでは・・・？

　今回は天秤と分割というシンプルな問題でしたが、入力の値によって各方針の得意不得意が分かれる面白い問題でした。次回の長期AHCはまだ明らかになっていなかったと思いますが、次回のテーマが今から楽しみです。改めて、コンテストの開催に関わってくださっていた方々、他参加されていた方々、楽しい時間をありがとうございました！

おまけ

以下は解法の補足情報を雑多に書いたものです。

 

・実はクエリ数が多いときは局所解にはまることがちょくちょくあり、ひどい局所解で止まらないように根性で三つの袋を再編成する遷移が存在する（が、たぶん10ケースに1回ぐらいしかこの遷移見かけない）

 

・アイテムの重さ順を判定するかどうかは具体的にはクエリ数が

アイテムの重さ順を調べるのにかかる回数(NlogN)+初期解の袋の重さ順を調べるのにかかる回数(DlogD)+30(初期状態から何回か遷移を行うのにかかるとおもわれる回数)

を超えているかで決めていた。何回か遷移を行えないくらいぎりぎりだと、雑な初期解から遷移を繰り返したほうがパフォーマンスが高かった。

 

・指定したアイテム群を指定した数に分割する関数（中の実装は超高温の焼きなまし）を用意することで、全アイテム半分に分けるときや、D分割するとき、最大の袋と最小の袋を足して割るとき、三つの袋を再編成する遷移など、いろんなときに使える（ここは既存のアルゴリズムを採用してもよかったものの、厳密解でなくても、近似比が保証されてなくてもよかったのでまあいいか・・・）

 

・クエリを投げようとしている比較に対して、「今の推定値の予想に反する結果を仮定して補正をかけてみても過去のクエリ・重さ順の補正によって今の予想に戻ってくるか」という関数があり、何回も反する結果を仮定しなおして試すことで遷移2のクエリは安心な方を後回しにしてクエリを投げている

 

・補正2と補正3は実は同じ枠組みで管理している

 

・今回とくに高速化は求められなかったので、各袋のアイテムをslice(可変長配列)で管理するなど、ほとんどは愚直なデータ構造を用いている

 

・実は重さ順がわかっているときの推定値は若干補正しているが、ほぼ推定値の結果が誤差なので省略した

 

 

以下はコンテスト中・後に思ったことを雑多に書いたものです。

・使っていないものの、ソート済みのアイテムの重さの生成は、遷移3で述べた初期推定値の式を参考にすると多分O(NlogN)ではなくO(N)でできる

 

・各ケースでの順位によるスコア計算、良いアルゴリズムがかなり母集団によらないか・・・？（基本的には多くの人が到達する解に+αした点に到達できるプログラムがある程度強く、今回だと、第一の波として順番にアイテムを配置した初期解、第二の波として初期解から最大の袋から最小の袋へ移動させる遷移の局所解がありそう。クエリ数が多い場合で最適解を求めてくるみたいな異常集団の波もあるかと思ったがさすがにそんなことはなかった）

 

・遷移2を実装して「これからクエリ数の大きいケースについて最適解に近づけていくぞ」という気持ちになっていたところ、たまたま起きてしまったREによりクエリ数の大きいケースの失点は大した問題になっていないことが分かってしまった（重さ順を確認するケースは暫定テストで58ケースあり、ここでの失点は0.3Mだったので、当時のスコアから他42ケースで3M近く落としていたことが分かった）ので、最適解方向の話は打ち切ってクエリ数が小さい時の安定化を考えることになった。

 

・今回の点数は100Mから各ケースで順位を落とした分だけ下がるので、遷移2により90Mくらいまでは上がりやすかったものの97M→98Mへの改善が思ってた以上にかなり遠かった・・・（この試行錯誤の間に他の人も良くなったプログラムを提出して少しずつ各ケースでの争いが激しくなっていたのもあるかもしれない）

 

・「アイテムの重さ、一番当たりそうな数字を言ってください」といわれると1なのだが、もちろんこんな推定がいいわけがなく・・・。

 

・マージソートやLargest Differencing Methodなどがコンテスト後に話題になっていた。確認してみるとどちらも今のプログラムに取り入れられる部分があるなあとなり反省。

 

・いろいろな方の解法ツイートや記事を見る感じ、割と基本的な方針はみんな同じなのかな？遷移をどうするかと推定方法（あるいは推定しない）が何パターンかありそう。

 

・simanさんが作ってくださった統計を見るに、無事安定志向のプログラムになっていそう。途中でクエリが小さいほうの対策をしていなかったら悲惨なことになってただろうな・・・。統計によってNに対してそれぞれどのような方針が有効なのかが何となく透けて見えるのも面白い。

【Postmortem】トヨタ自動車 実課題プログラミングコンテスト 2023 Spring

AtCoder Postmortem

※画像は公式Visualizerよりお借りしています。

 

はじめに

　この記事は2023/03/05 - 2023/03/19にAtCoderで行われました実務解決型のコンテスト「トヨタ自動車 実課題プログラミングコンテスト 2023 Spring」の解法を紹介するものになります。

　3/5から3/19の二週間、トヨタ自動車 実課題プログラミングコンテスト（以下実課題コンテスト）に取り組みました。Visualizerが3Dなうえに、荷物しきつめ問題のプログラムは一度書いてみたかったので終始楽しみながら取り組むことができました！

　 まだシステスは行われていませんが暫定2位ですシステス後も2位でした。

　ところどころ間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。

問題の概要

こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「コンテナ内に直方体の荷物を積み込む」という問題です。

問題文はこちら

atcoder.jp

 

ここで用いる独自の表現

（荷物の）依存関係

　私のプログラムでは、山登りの際にどの順に荷物を積むかは確定させず、荷物の配置だけを考えます。しかし、その配置計画を採用して実際に積む際には、荷物の配置によって「この荷物を先に置かないとあの荷物は置けない」という縛りが発生します（わかりやすいのは「あの荷物はこの荷物の上に載っている」という配置）。この、配置計画における荷物同士の順序の縛りを依存関係と呼びます。

最終提出の解法

以下、最終提出の概要です。

言語:go言語

　これはただの好みです。goの並行処理で100ケース試すものを作ったり、今回は実行時間を気にするタイプの解法だったのでgoのpprofでプロファイリングしたりとそれなりに利点はありました。

解法:乱択+部分破壊による山登り法

　以下はTwitterで行った解法ツイートです。

もう少し詳細を確認していきます。

乱択で荷物を積み上げ

　まずはランダムに荷物を積んでいきます。荷物の配置を決める順ですが、このフェーズが来る度に

・底面積の大きい順

・完全ランダム順

のどちらかを採用します。

　荷物を積む際はすでに配置の決まった荷物の角（と四隅の角）と荷物の回転方向をランダムに選択します。そして、その角に対して下の図のように四方向からくっつけてみます。

　ケースによりますが、これらの設置の仕方は高確率で不正な設置になるため、不正でない設置が見つかるまで再挑戦します。ある程度再挑戦しても見つからない場合は候補手なしとみなしてこの積み上げフェーズを終了します（速さを優先したために実は有効手が存在しても少ない場合は見つける前に終了します）。

　積み上げの際には、これまでにしてきた最善の積み上げ結果を上回るようなペナルティを受けてしまうようなものは不正な設置とみなします（過激派）。これによりこれまでの積み上げよりも悪い積み上げを長々としてしまう可能性を防ぐことができます。

　ペナルティの計算について、正確な順序ペナルティを計算する際には積む順番を確定させる必要がありますが、この段階では順番を確定させていないため厳密な値とは違う値で計算しています。　最善の配置を見つける段階では「各荷物はその上に載っている荷物やさらにその上に載っている荷物よりも先に置かなければいけない」というのを利用し、その依存関係において荷物の種類番号が逆転していないかを確認します。逆転している場合は荷物の種類番号の差を仮転倒数として追加します。これは荷物の種類番号が近い場合（特に連続している場合）にはこれによる転倒数は1で済みますが、種類番号が離れている場合には他の場所でも順序入れ替えが発生したときに大幅に増加する恐れがあるからです。順序最適化についてはまた別の部分で紹介します。

　上で述べたペナルティですが、はじめのうちは順序ペナルティを一切許容せずにやっていきます。順序ペナルティありである程度の解ができてしまうと順序ペナルティなしの状態への遷移が難しくなってしまうのが理由です。

 

配置計画を評価

　乱択で配置計画ができた(or途中で候補が見つからず打ち切った)ら、配置計画を評価するフェーズになります。基本はペナルティ（順序関係については上述）をもとに評価しますが、荷物がコンテナをオーバーしている場合には追加の評価基準が与えられます。この追加基準はコンテストのスコアに基づく評価ではなく、山登りにおいて登りやすくするための評価であり、解が改善しにくそうな状態に減点が入ります。

より具体的には以下の要素がおよそ同じくらいの影響力になるように設定しています。

・x,yがそれぞれ0付近のエリアにおいて隙間がないか（これによりx=0,y=0側のコンテナの壁は比較的しっかりと埋まる）
・荷物が高いところにないか（下が密、上が疎になっているほうが破壊→積み上げをした際に改善させやすい）
・コンテナ内の荷物の表面積が大きくないか（荷物同士がくっつくと無駄がないので改善させやすい）

　この評価がこれまでのもっともよい評価を超えていたらこれを最善の配置計画として更新します。

 

部分的に破壊

最善の配置計画を部分的に破壊します。

まずオーバーしている荷物は問答無用で破壊します。転倒数0での収容に成功していて高さ勝負となっている場合は一番高い荷物も破壊します。

その後の破壊方法は3つあります。いずれも、対象のものを破壊したのちにその荷物の上に載っていた荷物を順次破壊します。

・（収容成功した場合に限り）荷物の依存関係で順序関係が入れ替わっているものをランダム選択し、どこかにねじ込む。その際めり込んだものを破壊

・ある程度の隙間ができてしまっているところを探す。その付近に直方体エリアを設定してエリア内の荷物を破壊

・各荷物を確率pで破壊

　一つ目は転倒数最適化において効果を発揮する破壊方法なので、まだコンテナを超えている段階や、転倒数0が達成された場合には使われません。

　破壊活動が終わったところで、再び乱択フェーズに入ります。

 

破壊の様子

 

最善の計画を行動として出力

　約0.6秒制限で3回上記の山登りを行います。その中でもっともよかったものを行動として出力するわけですが、ここにきて初めて荷物の積み込み順を考える必要があります。

　まずは、貪欲に順序を決めます。貪欲の方法ですが、「上に荷物がのっていない荷物で種類番号が最も大きいものを選び、取り除く」を荷物がなくなるまで繰り返します。そしてこの順を逆順にすることで貪欲な積み込み順が完成します。

　続いて順序をswapして最適な順序を求めます。ランダムに荷物を一つ選び、荷物の積み込み順を今の順番より後のどこかに設定します。この荷物と依存関係にある荷物はそれに合わせて移動したりします。（うまく伝えられないので下の例を見てください）

例：

荷物5の上に荷物6、さらにその上に荷物3があるとし、それ以外の荷物は離れ離れに置いてあるとします。また、設置順として1,2,5,6,3,4,7,8,9というものが貪欲で得られたとします。

このとき、荷物5の順序を2つ後ろに設定するというのはこのような遷移を表します。

荷物3や6は5と依存関係があるのでswapはできず後ろに続いていきます。

仮に荷物7が荷物5の上に載っている場合は次のような遷移になります。

転倒数の変化は途中の過程を追うことで求まるので、「ランダムで選んだ荷物に対しいくつ後ろに下げるのが最もよいかを求める」を繰り返すことにより短い時間で（ほぼ）最適を得ることができます。

おわりに

　ここまで読んでくださった方、ありがとうございました。この頃はコンテストに出るたびに自分が少しずつ成長できているのを実感できてうれしいです。

　Visualizerが3Dなのには驚いたとともに、自分のプログラムが荷物を積み込んでくれる様子がとても感動的でした（「えっそこ入るのに・・・」みたいなもどかしさもしばしばありましたが）。巷では次のヒューリスティックコンテストが始まっているとか。さすがにしばらくは体を休めて、落ち着いたらそちらのコンテストも見てみようかなあなどと考えています。改めて、このコンテストの開催に携わっていた方々、他の参加者の方々、楽しい時間をありがとうございました！

おまけ

以下は解法の補足情報を雑多に書いたものです。

・有効手の計算を行っていないために、一つの荷物を設置するために数十～数百回も設置を試みなければいけない。そのため、かなりの高速化が必要だった。

・有効手の計算を行わないことによる他の欠点として、合法手が作りにくいケース（上に荷物を載せられないもの・底面変更不可の大きなものがあるケース）では、山登りに十分な試行回数が確保できていないという点があった。

・「確率pで破壊」がほぼ全破壊の可能性もあるので十分な時間があれば必ず大域解に到達できるのだが2秒（0.6秒）ではケースによってほぼ無理だったり。山を登りきれていない印象が強かった。

・「順序入れ替えありなら収容できる」というケースは想像以上に少ない(seed0~99だと10ケースもなかったと思う)上に、頑張って収容させた結果転倒数勝負でほとんど相対スコアがもらえない可能性も高いので、まずは順序入れかえなしで血眼になって探すのがスコア的には良さそうだった。3回に分けたのも局所的なところに陥って順序入れ替えなしの解を逃すことが減るようにだったりする。代わりに時間が足りず収容できるとこまで登れなかったりするのでここはトレードオフ。

 

以下はコンテスト中・後に思ったことを雑多に書いたものです。

・言及可コンテストだったので最初の解法くらいは共有したいなあと思ったけど最後まで解法を変えなさそうだったので控えた

・中盤以降は新しいアイデアもなかったので高速化に躍起になっていたが、終盤で「速度を多少失ってでも一回一回で出て来る解をまともにしたほうが良いのでは」となり微改善した

・焼きなまし、optuna使いたいけどどちらも全く使えなかった。使い方が下手なのかもしれない。

・今回ローカルでの実行を並行処理にできたのは革新的だったが、コア数を上回らないように制限しているにもかかわらずパフォーマンスが安定しなかった。

・Visualizerは作れなかった。どちらかというとスコアやデバッグ情報とにらめっこする時間が多かった。

・実課題なのに「荷物を破壊」とか「ねじ込む」とかいう表現してごめんなさい

・プログラム中の構造体の名前がいつもの癖でGameStateとかActionとかになってる

・Goは十分速い言語だと思っているので言語の実行速度は言い訳にできないんだよなあ・・・

・コンテスト後半は微改善しつつ順位表で上振れを引いて相手を絶望させる戦術をとっていたんですが、逆に火をつけてしまったかその上振れさえも超えられてしまいました・・・

・bottom-left法・・・。知識不足でした。調べてきます

・複数コンテストの取り組み方の最適化に失敗。逆にAtCoderのヒューリスティックコンテスト開催日時をユーザーの満足度について最適化してもらったほうがいいのでは？

・どうやら0.6秒制限の試行のうち一回でもvalidな解の形成に失敗してしまうと、積むことのできた荷物まででペナルティ計算してしまい採用してしまうっぽい。多分システスの2WAはこれ。

【Postmortem】RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)

AtCoder Postmortem

※画像は公式Visualizerよりお借りしました

はじめに

　本日は2/18 - 2/26の期間にAtCoderで開催されたコンテスト「RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　2/18-2/26日の間、AHC018に取り組みました。AHC017に参加できなかった悔しさもあり相応の時間を費やしまして、最終順位は23位でした（システス後まで順位表一ページ目は保てなかった・・・）。AHCに参加するのはこれで四回目ですが、過去最高順位（そして初橙パフォ）でした！

問題設定も面白く、ヴィジュアライザで自分のプログラムの解を眺めるだけでも楽しかったです。

　Postmortemの経験も増えてきましたが、いまだ用語がよくわかっておらずところどころ間違っていたりすると思います。発見された方は優しくご指摘いただけると嬉しいです。 

問題概要

問題内容は、私自身が伝えるより問題文自体を見ていただいたほうが伝わるとおもうので以下にリンクを張っておきます。

atcoder.jp

　簡単にまとめると「水道を引きたいんですが地質調査してないのでいい感じのルート見つけながら掘ってください」という問題でした。

この記事で用いる独自表現

・flow

　水が流れているマスのことを言います。すなわち、

・水源マス

・水源マスとつながっているすでに掘削されたマス

の二つを指します。

 

最終提出AIの詳細（戦術など）

seed:0での様子を貼っておきます。

言語:Go言語

　いつもの。個人的な好みであり、特に言語的な利点はないです。

解法

以下、AIの概要です。

・基本は2フェーズ

掘削計画の基本は二つのフェーズからなっています。

 

フェーズ1: investigate

このフェーズでは代表点をとり未知のフィールドの様子をざっくりとつかみます。

1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む

2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める

ここでもしミニフィールドの最短路上の代表点で壊せていないところがなければフェーズ1を終えフェーズ2に移行

3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。

4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更

 

フェーズ2: destruct

このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。

1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完

2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）

3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）

4. 家側から順番に掘削

 

もう少し詳しいところは以下で見ていきます。もし長い文字列で目が滑ってしまうような場合には、上に乗せたseed=0での様子と照らし合わせてみるとよいかもしれません。

・フェーズ1: investigate

1. 200*200のフィールドを12マス間隔に取った代表点のフィールド(以下ミニフィールドという)に落とし込む

落とし込み方としては「家、水源、flowを最も近い代表点に丸める」という方法があると思いますが、最終提出では「左上、左下、右上、右下方向でそれぞれ一番近い代表点（計4点）に分裂させる」という手法をとっています。

 

2. 各代表点の頑丈さの推定値から、ミニフィールド上でflowから最も近い家とその最短路を求める

Dijkstra法です。

ミニフィールド上では、移動は8方向にとります。これは、200*200フィールドにおいて、代表点間は縦→横→縦→横→・・・と繰り返すことで上下左右の代表点に近づくことなく斜めの代表点に移動できることが関係しています。

　移動コストを考えるときには、各代表点の頑丈さの推定値を用います。

壊したことのあるマス・・・壊すまでにかかったパワー

パワーを加えたことがあるが壊せていないマス・・・そこに費やしたパワー×5

パワーを加えたことがないマス・・・C×5

といった具合に雑に推定しておきます。×5としているところを増加させると寄り道を考えずらくなり、逆に減少させるとあちこち調査するようになります。

　また、移動コストの計算は縦横移動と斜め移動で多少変わります。代表点を12マス間隔でとると17×17のミニフィールドが出来上がるわけですが、以下ではわかりやすく2×2のミニフィールドでいくつかの移動コスト例を見ます。

S_{i,j}を(i,j)の頑丈さの推定値とする。

(0,0)から(0,1)（横移動）のコスト: \displaystyle (\frac{S_{0,0} + S_{0,1}}{2}+C) \times 12

(0,0)から(1,1)（斜め移動）のコスト: \displaystyle (\frac{1}{3} S_{0,0}+\frac{1}{3} S_{1,1}+\frac{1}{6} S_{0,1}+\frac{1}{6} S_{1,0}+C) \times 24

(0,0)から(1,1)への移動の仕方は以下の3つが考えられます。

・(0,0)→(0,1)→(1,1)

\displaystyle (6 \times S_{0,0} +12 \times S_{0,1} + 6 \times S_{1,1}+24 \times C)

・(0,0)→(1,1)

\displaystyle (8 \times S_{0,1} +4 \times S_{0,1} + 4 \times S_{1,0} + 8 \times S_{1,1}+24 \times C)

・(0,0)→(1,0)→(1,1)

\displaystyle (6 \times S_{0,0} +12 \times S_{1,0} + 6 \times S_{1,1}+24 \times C)

この計算式により、(0,1),(1,0)の頑丈さによっては、斜めに突っ切るほうが近いと判定してもらえることがわかります。

なお、このコストの式はフェーズ2での補完の値との整合性が取れるようになっています。

 

3. ミニフィールドの最短路上の代表点でこれまでに加えた力が最も小さい場所を掘る。

パワーは

・まだ掘ったことがないなら、Cの値と同じだけの力で掘る

・掘ったことがあるならこれまで累計で与えた力と同じ力で掘る

といった具合です。この掘り方では最悪のケースでも最適な掘り方の二倍のコストで掘ることができます。

 

4. 壊せた・壊せなかったに応じて代表点の頑丈さの推定値を変更

今回掘ろうとしたマスに累計で与えたパワーを更新しておきます。

 

・フェーズ2: destruct

このフェーズではフェーズ1終了直前に求めた最も近い家をflowにくっつけます。

1. ミニフィールドの頑丈さの推定値によりフィールドの各マスの頑丈さの推定値を補完

以下は10マス間隔で代表点を取っていたころの図ですが、4つの代表点から正方形エリアをこのように補完します。（線型）

（この図は左下と右下が比較的柔らかく、左上と右下が硬い場合です）

この補完は補完の仕方よりもPhase1のミニフィールドでのコストの式と整合性をとることが重要です。

整合性が取れてないとこんな悲しいことに・・・

 

2. 頑丈さの推定値からflowまでの最短路を求める（掘削ルートはこれで決定）

お決まりのDijkstra法になります。

 

3. 掘削ルートで、まだ掘られていないところがあまりに連続しているところはより良い推定のためにサンプルとして少し掘削（ルート変更はしない）

追加調査前

追加調査後

このくらいの幅でサンプルを取っておくと頑丈さを大きく外すことはないので、これ以上幅を小さくしてもあまり効果はなかったです。

 

4. 家側から順番に掘削

「思ったよりも掘削に力が必要だった」、逆に「ちょっと軽めにたたいたつもりだったのに壊せちゃった」があれば、前後の掘削ルートの頑丈さの推定値を微妙に操作します。これも「微妙な操作」の式自体はあんまり関係がなくて（実際雑です）、「想定よりも硬い・柔らかい」が減衰しながら次以降の掘りに反映されているところが大事だと思われます。

 

おわりに

　ここまで読んでいただきありがとうございます。過去最高順位をとることができたのもうれしかったですが、何より自分のプログラムがしっかりと硬いところを避けて掘削しているのをVisualizerで見ることができて感動しました。私は戦略性+Visualizer（ゲームをするかのような頭の使い方と視覚的な要素）からヒューリスティック系のコンテストに興味を持ったタイプで、毎度公式Visualizerが用意されているのには頭が上がりません。

　次に参加するコンテストをどれにするかは未定ですが（早ければ今週末のあれかも）、次回コンテストでもまた楽しんでいきたいです。お世話になった方々、ありがとうございました！

 

おまけ

基本的にPostmortemは以上になります。ここからは見出しにもある通り完全におまけですので、見ても有益なものはないかもしれません。

 

思ったこと、追加情報をまとまりもなく書きとどめておきます。

追加情報

・Phase1での横移動・斜め移動のコストは、Phase2で補完したときの横移動×12の総コスト・（横移動＋縦移動）×12の総コストとほぼ一致する

・ミニフィールドに落とし込む際には、flowなどと代表点の距離を用いてDijkstra法の際に初期値を増やしておくことで誤差を減らすことができる

・掘削で頑丈さを計測する時、「計測を正確にしたい」と「破壊までにかかる回数をおさえたい」がトレードオフな関係なので、あまり丁寧な計測は効果がなかった

・Phase2の代表点間の補完は線形より良い近似もあるが、追加サンプルもふまえると正確さとしてはそれ以上突き詰める必要は感じなかった

・道をつなげるとき、一発目はCに応じて予想コストの0.8倍~0.95倍で掘削していた

・ローカルで実行する際、「phase1でかかったコストを無視するか」「最適な力で掘削するか」などフラグを用意しておくと自分のプログラムの問題点が把握しやすくてよかった

 

考えたこと

・インタラクティブ問題はローカルでの実行に壁を感じて参加者が少なくなるかと思ったけどそんなことなかった

・問題見たときに「水道つなげる前に地質調査しようよ」と思ったけど、本当に最初に地質調査する問題だった

・最も柔らかい部分と最も硬い部分の差が500倍もあるというのがあまり実感がわかず、最初は調査すると自明解より弱くなるんじゃないかと思っていた

・人間の温かみのあるパラメータ調整が自分の武器だと思っているので、全人類がOptunaをうまく使えるようになってしまうとなかなか苦しい

 

次回以降に向けて思ったこと

・みんなの自作ビジュアライザがかっこいいので自分も作りたい。（他の方のVisualizerって毎回すごい見た目してるけど典型みたいなものはあらかじめ持ってるのだろうか？はたまたコンテスト中に０から作っているのか・・・？）

・ローカルで大量テストができる環境作りたい。

・コンテスト中に焼きなまししたい。（ほんとは今回するつもりで意気込んでいたんだけど・・・）

【おまけ】Fall Challenge 2022の諸々

CodinGame 検討

 

 

はじめに

　今回のコンテストでは6位と自分の中ではかなり良い順位ではあるんですが、一方で最上位に数歩届かず悔しい思いもあります（もともとLeaderBoardで雲の上とみていた憧れの人たちとLegendリーグでマッチングしているだけでもうれしいんですが）。そこで、次回こそは勝ってやるんだという気持ちでもう少しまとめてみます。

　AIの方針はPostMortemにすでに書いた通りなのですが、もう少しだけ具体的にどう実装していたかを書き残しておきます。また最後の「解法の選択」はより次回以降のコンテストのために今の自分をまとめておこうと思い書きました。（次のコンテストまで意外と期間が空いたりして今の自分が得た知見が失われていたら嫌なので・・・）

　結構長くなりますので、読んでいただける方は目次から気になるところだけ読んでいただけたら。

　前提となっている自分のPostMortemはこちら

montplusa.hatenablog.com

 

いくつかのトピック

ユニットの割り当て

　以下で説明するのはあくまで自分のbotの元となるアイデアです。

下のような場面を考えます。

（これはPostMortemの衝突地点の話で使っていたものです。）

DefencePoint（青）は自分のユニットのほうが近いマスなのでまずはDefencePointを確実に塗りたいところ。

　まずは自然にこれらの衝突地点に一番近いユニットを割り当てるというのを考えました。どの衝突地点から割り当てるかで変わってきますが、以下が一例です。

　このように3体を配置したところで、まだ割り当てていないユニットではDefencePointを守り切れない（残っている一体は相手よりに先に到達できないので向かっても確実に塗れるとは限らない）ので手詰まりになってしまいました。

　ここで、DefencePointは本来「順当にいけば確実に塗れるはずの場所」だったことを思い出すと、DefencePointを担当したユニットは絶対に敵ユニットと相殺されない、つまりその他のDefencePointも担当できるのでは？という考えが浮かんできます。

　具体的には以下のようにDefencePointから距離が増加する方向へは複数のDefencePointを担当することができます。これは各衝突地点を頂点とした有向グラフとして保存しておくと何度も割り当てを考える際に比較的高速に処理が可能です。

（このほか衝突地点はおおよそのケースで64に収まるのでbitboardをつかって高速にする方法があります。が、今回は全力で高速化、というほどまでは詰めなくても割り当て速度が問題になることはなかったです）

一例として、この複数を担当することを考えると、このような割り当てを考えることができました。すべてのDefencePointを塗ることができ、また、いくつかのNeutralPointにも割り当てることができるようです。

　加えて、相手より2ターン早く到達できるDefencePointには最前線へのスポーンも有効です。これも考慮することにより、以下のような割り当ても可能になります。

（黄色の線は新たにスポーンさせ、そのユニットに割り当てていることを明確にするために色を変えただけです）

　これによりさらに割り当ての幅が広がります。あんまり変わらないように見えるかもしれませんが、中央に一人多く送り込むことができたりするだけでかなり多くの有利が取れる場合があります。

　最前線に間に合わないユニットの割り当ても同じロジックで考えることができます。例えば、上での到達ターン制限を+1すると1ターン遅れて到着するものも考慮することができます。特にNeutralPoint（到達に必要なターンが両者同じマス）では、最速で到達できるユニットが相手と同数の場合に、最速で到達できるユニット同士が相殺され、その次のターンに送り込んだユニット数勝負になることもしばしばあるので有効です。なお、2ターン以上遅れるとなると防衛の割り当て数などが不正確になっていくので、私はどの衝突地点にも2ターン以上で遅れてしまっているユニットは最寄りの衝突地点に向かわせていました。

 

　大事だと思う衝突地点から順に割り当ててそれを行動として出力してもよいですが、これらの割り当てを得点化し、良いものを採用するとよりよい動きをしてくれるようになりました。

　この例の試合では結果として序盤の中央勝負で有利をとることができました。

（うっすらと見える青、黄、赤はゲーム開始時点での衝突地点）

 

以下のリプレイでも真ん中一列をとることができ、これが勝因になりました。

https://www.codingame.com/replay/689120836

各地点間の距離計算

　本当ならばマップ上のすべての地点間の距離を知りたいところですが、最大のマップサイズでは12*24=288頂点となってしまいとても50msでは考えられそうにないです。

そこで、各ターン必要になりそうな距離だけをいわゆるBFSによりに求めます。今回はRecyclerでいずれ緑化するマスがあるのが特に逆順で距離を求める際に悩みました。

 

1. 自分のユニットのいるマスを距離0、ユニットのいない自分のマスを距離1として、そこからBFS→自陣から各地点への距離がわかる

2. 相手のユニットのいるマスを距離0、ユニットのいない相手のマスを距離1として、そこからBFS→敵陣から各地点への距離がわかる

 

ここで、1.と2.で得た距離の差が2以下の点を衝突地点として登録します。

 

3. 衝突地点を距離0としてそこからBFSを衝突地点ごとに行う→各地点から各衝突地点への距離がわかる（注意：衝突地点への距離を衝突地点から逆にたどって求めているのでrecyclerによる緑化判定が少し複雑になります！）

 

この場面での距離を見てみます。

1.はこんな感じに。recyclerの影響で行けない場所があったり、遠回りを要求されているところがあったりします。

2.はこんな感じに。

3.はこんな感じに。（下画像黄色の四角で囲んだ衝突地点についてBFSを行っています）

この3.は以下のような緑化による最短経路の違いに対応する必要があります。

おおよそこれで行動を選択するのに必要な距離がすべて手に入りました。

（衝突地点の数が膨れ上がっていて3.が時間がかかってしまう可能性が指摘されそうですが、通常の試合ではその点は問題ありません。厳密には敵と市松模様のような模様をつくられると全地点間距離を求めることになり時間をオーバーしてしまいますが、こちらが協力して自陣に入れない限りはそうはならないです。）

 

 

解法の選択

　これは良い手を探すのにどのような手法をとるかという他のコンテストを含めた話題になります。これはあくまでまだ新参者の自分の感覚で、一般的に正しいものであるというわけではないことにはご注意願いします。もしマラソン系、対戦系コンテストを始めて少しという方ならなんか得られるものがあるかも。逆にマラソン系、対戦系コンテスト玄人の方、ご指導ご鞭撻のほどよろしくお願いします。

　問題のテーマによってどのような手法が適用しやすいかは変わってきます。ここでは、自分が適用したことのある手法と適用しやすいと感じる問題のタイプを書いておきます。解法自体の説明については自分が説明するよりも他サイトの素晴らしい解説を見たほうが良いので割愛します。

 

全探索

　自分が全探索を使ったことがあるのはCodinGameのGreenCircleなど。

　全探索の雰囲気は「いや、全部自前のシミュレーターで試したらいいやん」というもので、実際のところ、ゲーム終了までのすべてのパターンを試せるならこれが最強です。

　ところが、大体のコンテストを見てみると、パターン数が膨大ですべてを試すことができないので、「1~3ターン先までの行動をすべて試す」or「ありえない手は外してもう少し先まで試す」という風に使っています。そもそも次ターン以降の自分の状況が予測不可能だったりする場合は消去法的によくこの手法を選んだりします。

　全探索の場合、自分は評価関数はその盤面に将来性があるかなどを考慮して比較的複雑なものにする傾向があります。深さが浅い全探索自体には将来性が反映されていないのと、全探索は深さが1増えるとパターン数が跳ね上がるために多少高速化しても深さを1増やすことはできないからです。

例えば、CodinGameのGreenCircleでは、カードのドロー後からターン終了までの可能なアクションは相応に限られていたので1ターン全探索を行いました。逆にこのコンテストでは次ターン以降はカードのドロー次第で状況が変わるので読みづらいゲームでした。

 

ビームサーチ

　自分がビームサーチを使ったことがあるのはCodinGameのMadPodRacing、SpringChallenge2021など。

　ビームサーチと全探索はかなり近い手法と思っています。ビームサーチは評価値の上位のものだけ次のターンを考えていくことで全探索に比べて時間やコストを節約できます。

　ターン制の対戦型コンテストにおいて、状況を得点化して、nターンの良さげな行動を探すというのが自分の中では多いです。しかし、ビームサーチ（と後述する焼きなまし）自体は相手の動きの影響に対して弱い（と私は思っている）ので、一ターンの敵の行動によって大きく状況が変わってしまうゲームよりは、敵の影響がある程度小さいゲーム、あるいは敵との衝突要素がないマラソン系だと考えやすいです。また、結構ターン（順序関係）を意識した手法な気がします。順序関係がないものでは無理やり順序関係を作ったり、重複を除去するなどの工夫が重要になりそうです。

　ビームサーチの場合、自分は評価関数は盤面の将来性があるかなどを考慮しつつも全探索よりは軽めにする傾向があります。将来性をある程度見積もらないと数ターン後に盤面がよくなるような手がビームサーチの幅から外れてしまい探索できない可能性がある一方で、軽めにすることで幅が増やせたり、深さが深くなったりするのが理由です。

例えば、CodinGameのMadPodRacingは1ターンでマシンの向き変化はせいぜい18度ほどなので、1,2ターンでの敵の動きは台風の予測円みたいにある程度のぶれに収まります。したがって、敵の妨害などがある場合でも、敵がある程度巧みなプレイヤーでなければマシンを走行可能でした。

SpringChallenge2021は、1ターンに複数行動ができるゲームでしたが、1ターンに得られるマナ（いろんな行動のもとになるもの）がそれなりに少ないので行動数がある程度限られたことや、アクションが種を植える、木を育てる、収穫といった具合でユニットが移動するタイプではなかったので相手の影響はある程度小さいゲームでした。

 

山登り法・焼きなまし法

　自分が山登り法を使ったことがあるのはCodinGameのSmashTheCodeなど。

また、ランダム+貪欲も個人的には山登りとほぼほぼ同じものだと思っています。

　ビームサーチの場合だと「これをしてから、これをして・・・」というような順序関係が根本にあるのですが、山登りは順序関係がないものにも使いやすいです。今回のコンテストだと1ターンのユニットの動きは「どのユニットから動かす」みたいな要素がないので、ユニットを雑に動かして、山登りにより改善、みたいな発想もあるかもしれません。（私は当初はこの予定でした）

　焼きなまし法は山登りの際に確率的に悪化するものを採用するということでかなり山登り法と近いものを感じます。採用しすぎると山登りよりも悪い結果になることもありますが、基本的には山登りよりもポテンシャルのある手法だと思います。（コンテスト期間中に実装した経験なし）

　例えば、CodinGameのSmashTheCodeはいわゆる「ぷよ〇よ」だったのですが、相手による影響は「連鎖を打ってくるか打たないか」の二択だけだったので、打った場合と打たなかった場合で6手の置き方の山登りを行いました。「ぷよ〇よ」は手順のあるゲームですが、連鎖を組む行為がしばしば「一時的に連鎖をつぶす・連鎖を打たない」というタイプの行為になるので、途中段階での評価が難しく、ビームサーチを私はうまく使えませんでした。

モンテカルロ木探索（MCTS）

　自分がモンテカルロ木探索を使ったことがあるのはCodinGameのUltimateTicTacToeなど。

　モンテカルロ木探索は自分と相手が交互に手を打つ場合に使いやすいと感じています。特にボードに駒を交互に置いていくタイプのゲーム（〇×ゲーム、五目並べ、オセロなど）では手を適用するのが高速で、ランダムな手でゲームの最後までをシミュレーションするのもかなりすぐに終わるので回数を稼ぎやすく、使いやすいです。

　一方で可能な手が多いタイプのゲームだと純粋に使うことはあまり効果が期待できなくて、ありえないと思われる手（五目並べで遠い彼方に駒を置くみたいな手など）を省くなどして対策するのがよさそうです。ゲームの最後までをランダムな手で実行するタイプの場合は評価値として勝ち/負けが利用できるので、良い手が人間では想像がつかない場合にも有効な気がします。

　例えばCodinGameのUltimateTicTacToeは、いわゆる〇×ゲームの革命的な拡張版ですが、人間では何が良い手なのかいまいちわからない問題でした。一方でマスは9*9、出てくるマスは〇と×だけ、駒の移動もなしというゲームなので、ゲーム終了までランダムな手で実行するのは比較的高速でした。

 

MiniMax法

　使ったことがあるのはCodinGameのUltimateTicTacToe（Goldリーグにいたころ）など。

　この手法も交互着手だと使いやすいです。あらかじめ候補手を絞らない場合は全探索と同じ感覚だと認識しています。なお、αβ探索に切り替える（不要な計算を省く）ことで、思ったよりも先の手まで探索することができたりしました。

　　CodinGameのUltimateTicTacToeは交互に行動するタイプであったためにMiniMax法が利用できそうな問題でしたが、UltimateTicTacToeのゲーム性が難しく、うまい評価関数が見つからなかったためGoldで止まってしまいました。もちろんMiniMax法を使うLegendの人もいるので、Goldで止まるのは自分の力不足です。（ゲーム終了までシミュレートするMCTSに切り替えたところLegendに到達しました。）

　今の自分はおおよそこんな理解です。まだコンテスト経験のない機械学習、遺伝的アルゴリズムなどはまだまだ感覚が得られていませんが、いつか挑戦できたらと思っている手法ではあります。

 

 

　さて、今回の問題で考えてみると、大量の候補手やゲーム終了状態までの長さ、同時着手ということからMCTSは不向きだと思っていて、全探索やビームサーチもパターン数的にあり得ない手を削るor一つ一つのユニットを独立に扱う必要がありそうです。Minimax法も相手の動きを仮定してから自分の動きを決めてしまうのをある程度解消しなければという感じがしました。必然的に貪欲or山登りあたりが自分の手持ちかな・・・と考えてました。自分は機械学習は門外漢なので機械学習なんかも得意なタイプなんじゃないかなあなどと考えていましたが、マップのサイズやコード長制限など、機械学習にも困難があったみたいです。

この他if文の条件分岐のみで行動を決定したり、目標に向けて貪欲に行動を決定していくのも有効です。個人的には貪欲法を実装したら「多少のランダム性をつける＆評価関数を作る」「部分的に破壊して適用し直す」へもっていくのが安心安全の流れだと思っています。

　ところでルールベースっていったいどういう区分なんでしょう？自分の中では結構あいまいなんですが・・・。

 

おわりに

　この駄文をここまで読んでくださった方いるんでしょうか・・・という感じですが、ここまで読んでいただきありがとうございます。今後のコンテストに向けて自分が成長できるように書いたものでもあるのですが、もし今読んでいる方のお役にも立てていたら幸いです。

【Postmortem】Fall Challenge 2022

CodinGame Postmortem

※画像は公式Visualizerよりお借りしました

 

はじめに

　本日は12/13 - 1/5の期間にCodinGameで開催されたコンテスト「Fall Challenge 2022」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

　CodinGameコンテストに参加するのは今回が4回目だったのですが、前回に引き続きLegendに到達することができました！

最終順位は

世界6位/4577人、日本4位/201人でした！（JP強すぎないか？？？）

　いまだ用語がよくわかっておらずところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。

（早く公開することを第一にしたために「何をしたか」しか書いておりません。解法共有の重要ポイントである「どのようにしてやったか」をかけていないので、諸々の箇所に「詳細を聞きたい方がいらっしゃれば教えてください」みたいな部分があります。該当箇所にかかわらずお気軽にお申し付けください。）

→おまけとしていくつか書いてみました。

montplusa.hatenablog.com

 

　前回書いたAHC016 のPostmortemはこちら

montplusa.hatenablog.com

 

ゲーム概要

　ゲームルールにつきましては、おそらくここにたどり着いている方の多くがご存じだと思いますので割愛します。雑にいえば色塗り合戦です。

最終提出AIの詳細（戦術など）

言語:Go言語

　いつもの。特に言語的な利点はないです。

解法:ランダム＋貪欲

　いわゆる乱択貪欲というものになるんでしょうか・・・。もともとLegend解放前は貪欲で戦っていたので、順当に時間いっぱい考えるようにした結果です。

以下、AIの概要です。

・衝突地点を割り出す

各ターンマップ上のマスのうち以下のような点を取り出します。

・自分のほうが1or2ターン早く到達できるマス(DefencePoint)

・両者同じターンで到達できるマス(NeutralPoint)

・相手のほうが1or2ターン早く到達できるマス(AttackPoint)

主にこの点を守るor攻撃することを考えます。

 

例として、ある試合のゲーム開始直後の衝突地点は以下のようになっています。

青:DefencePoint　黄:NeutralPoint　赤:AttackPoint

数字は近い側の陣営が到達するまでのターン数



（Recyclerなどによりあと何ターンでマスが通れなくなるかなどを考慮しながら各陣営からの距離を求めます。このあたりの詳細が知りたい方がいらっしゃれば教えてください。）

・衝突地点にユニットを割り当て

これら3種類のマスにそれぞれ4段階の割り当て数目標を与えます。ここでは次ターンで敵が攻撃に来うるようなDefencePointでの基準をやんわりと書きます。

 

1.隣接している敵が、防衛用のユニットを残したと仮定して、攻めてくる数

2.隣接している敵が、周辺のユニットをかき集めて防衛用のユニットを残したと仮定して、攻めてくる数

3.隣接している敵が全員で突っ込んできた場合の数

4.次ターンまでに突っ込んできうる最大数（つまり、3.に加えてspawn→moveの流れできうる数、距離2にいる敵なんかも加算されます）

（4は満たされることはほぼほぼないと思います）

割り当て可能なユニットが複数いる際は等確率で選び出します。

 

（DefencePoint、NeutralPoint、AttackPointに割り当て続けていたらユニットが足りなくないか？みたいな部分はもし聞きたい方がいらっしゃれば教えてください。）

・割り当てを評価

　上の割り当て方ですが、どの衝突地点から割り当てるか、どのユニットを割り当てるかによって解は大きく異なります。したがって、評価関数を用意し、最高点を出せた割り当てを採用します。

各衝突地点のスコアは

（衝突地点の重要度を数値化したもの）×（衝突地点の基準充足状況を数値化したもの）

を基本として、全衝突地点のスコアを足し合わせたものが割り当てのスコアになります。

・recyclerのbuildは割り当てとは無関係に雑に行う

　recyclerの設置は上の割り当ての前に以下を鑑みて設置します。

・自身のエリア確保状況（戦闘が終わりかけていて不利だとrecyclerは自陣を減らすことになるので基本置きません）

・ユニット、保有matter(戦線で戦えるユニット数や保有matterで上回っていると、マター集めのrecyclerはよほどの効率がないとしません。)

・隣接マスにいる敵ユニット(隣接する敵が多い場合など、防御効果が感じられる場合は防衛することがあります)

recyclerの設置で失う土地については

(消える自陣のマス)-(消える敵陣のマス)+(消える中立のマス)+(到達不可能にしてしまうマスの数)

として、この値と設置した場合に得られるmatterを天秤にかけて最終的に設置するかを考えます。

（到達不可能にしてしまうmatterの数はどう計算したのみたいなことが聞きたい方がいらっしゃれば教えてください）

弱点

序盤はなかなかに長期のコンテストで万事を尽くせるなどと思っていましたが、最終提出の自身のbotには数々の粗があります。うち、特に問題のある点を残しておきます（未来の自分がもしこのコンテストを継続する場合のことも考えて書き記しておきます）

・recycler設置係とユニット割り当て係のディスコミュニケーション

　これは最大の問題点。前のrecyclerの方針では「隣接マスにいる敵ユニット(敵が多い場合など、防御効果が感じられる場合は防衛することがあります)」などと書いておきながら、recycler設置係はあまり賢くないので切迫した状況にもかかわらず適当なところにbuildして、前線にspawnさせるためのmatterが足りなくなることが結構あります。

・割り当て評価のスコアが雑

全力でspawnしていたら最重要ポイント（ここはとれなかったら負け確定みたいな点）を守れていたのに、分散して守らせてしまったことにより敗北するというのもしばしばありました。今回終盤に割り当て評価をガラッと変えてしまったので調整が不完全です。（ここは多少のじゃんけん要素の絡むところではありますが・・・）

 

途中で世代交代となったbotたち

Wood Killerくん

　これは相手の陣地に全力で迫っていくタイプのもの。WoodBossを倒すことを目標に育成しました。WoodBossはmatterを使い切らないうえにbuildもしないので、毎ターン1スポーンすれば数で押し切れると思い、ただただ敵陣に向かって突っ込むように実装しました。BronzeBossもbuildをしないタイプだったので結果的にBronzeKillerにもなりました。

Falconくん

　silverでは、WoodKillerくんはrecyclerでマター集めをした人たちに返り討ちにあったり、そもそもrecyclerで進路が阻まれたり。そこでsilverリーグで限界を迎える初代 WoodKillerくんに代わる2代目Falconくん登場。Falconくんには高い周囲観察力や攻防の機敏さを期待してこの名前を付けました。

　FalconくんにはWoodKillerくんの数々の弱点を克服してもらいました。「防衛地点にユニットを割り当てる」という基本方針をここで固めました。また、Recyclerを、消してしまう土地に対して得られるmatterが最大のところに置くようになりました。

　他にも戦闘終了後に自陣を塗ったりなど、最後まで必要になる根幹はここで生まれました。割り当て順を工夫するなどしてFalconくんは当時の50位付近まで成長しました。

（ここで成長できたのがこの後コンテストへのモチベーションを保てた気がします）

Radial Flowくん

　RadialFlowくんはFalconくんの突撃体質による防御面の弱さを治すことを目標に生まれました。距離計算の際にrecyclerによる緑化を考慮したり、複数体スポーンさせないと守れないような衝突地点をBuildで防いだり。DefencePointを一体で複数カバーできる場合もあるので、複数に割り当ててみたり。RadialFlowくんは当時のメモによると12月末Goldリーグの14位まで行けたらしい。

Towering Cliffsくん

たぶんこのときのやつ。3代目RadialFlowくんの負けた試合を見ていると

「いや、ここはこのユニットに任せておけば真ん中一足先にとれるぞ」

「いやいやここはスポーンで対応したほうが・・・」

みたいな盤面をちょくちょく見かけました。これは山登り法を実装するときなのでは（あわよくば人生初焼きなましを・・・）、と思い、ToweringCliffsくんの育成に取り掛かりました。

まず山登りを実装する（割り当てをやり直したりする）にあたって、持っている割り当て情報をもう少し扱いやすくしなければならなかったので、RadialFlowくんのコードはほぼほぼ解体しました。また、扱いやすさのためにこれまでに実装していた多くの機能を失うことになりました。

　ツイートではn日かかるといっていましたが、ゲームのアクションをかなり制限した形での実装に2日、RadialFlowくんの持っていた機能の8～9割の復元にさらに2~3日かかっており、実装力のなさに危機感を覚えております・・・。それも結果的に山登りではなく貪欲を時間いっぱいやり直すという方針になりました・・・。

　ToweringCliffsくんはさらに、Recyclerを置いた際に自陣に到達不可能なマスを作ってしまうという問題や、無限ループ時に自分の拠点を塗らない問題を解決し、リサブの上振れ次第でちょくちょく1位に上がることもありました。（あれは潜伏、リサブの下振れ等いる中の仮初の1位だと思っていますが・・・。）

　なお、最終提出のThe Bumpinessくんとの違いは、「顔文字を出力するか」と若干のパラメータ調整くらいしかないです。

　

おわりに

　ここまで読んでいただきありがとうございます。CodinGameのコンテストに前回参加したのはGreenCircleになりますが、その時に引き続き一桁順位をとれたのがとてもうれしかったです。（もともと3桁順位の住人なので・・・）

　大変長いコンテストでしたが、コンテストを開催してくださったCodinGame様、Arenaでお世話になった皆さん、楽しい時間をありがとうございました！

【日記】HTTF（AHC016）

AtCoder 日記

以下はHTTFコンテスト期間時に考えたことをそのままメモしたものです。公開にあたって改めて見直していますがメモ程度のものだったので誤字脱字多いかもしれないです、コンテスト前半は体験記、問題の考察中心で、中盤以降は改善点中心です。

 

参加登録

　HTTFが今年も行われるみたい。去年は都合が合わず参加できなかったけど今年は参加したい。本選は数年ぶりのオンサイトらしく、大変めでたい話だ。就活一本の人もいるだろうから24卒対象者ではないとしておくか・・・。一応24卒対象者以外でも最上位10人は行けるみたいだが、そこまでの実力がないことはわかっているので、マラソンの経験を積むために参加させてもらおう。

一日目(11/11)

　問題文を読みました。

　よくわかりませんでした。よくわからないのでVisualizerにあるinputを使ってサンプルコードで試そうとしましたが、なぜかうまくいきませんでした。いつもはこれで問題がつかめるのに・・・。問題をよく見るとかなりインタラクティブなようで、これはローカルにいろいろ用意しなければという気持ちになりましたが、それは明日以降の自分に託すことにしました。

 

今日の取り組み

　・使うグラフの頂点数は少ないほうが良い

　・正答率は高いほうが良い

の二点から、可能な限り極端なグラフを用意して判別するのがよさそう。上で述べたグラフの頂点数が少ないほど正答率下がってしまうのでちょうどよいところを探したいが、それは序盤にやるべきではなさそう。（前科あり）

　極端なグラフといっても、頂点の番号を入れ替えると似たようになるものは、Hの生成方法を考えると判別しにくそう。雑にMと同じだけ頂点を用意してみるか・・・。辺の数が0~N-1個で判別しようとするとエラーに弱いので、等間隔に辺の数を離して 0~N(N-1)/2個で判別したほうが確実かな・・・？

　ん？だとするとエラー率が十分小さいときはそんなに頂点いらないのでは・・・？まあ考え出すときりがないので明日以降にするか・・・

上はそれぞれのGからエラー後の辺の数の期待値をとり、それが最も近いものを選んだ場合

下は頂点数N＝Mで、Gのうちで辺の数が一番近いものを選んだ場合

　辺の少ないグラフは基本エラーで増えるし、辺の多いグラフは基本エラーで減ってしまうので、確かに上のほうが合っていそう。

　どうしても問題が気になるので考察を続行した。

頂点の数少なくしすぎて全然判別できなかった。最終提出が採用されるので間違えたものを提出すると順位表駆け下りていくの面白い。

これらは自己記録よりかなり下だが、順位表ではベストとおなじくらいだった。相対評価、かなり奥が深い・・・

この日はいろいろやってみたがあまりつかめなかった・・・（まだローカルでテストできないけどたぶん正答率結構低い気がする）

　まだサンプルコードを流用しているのである程度考察出来たらGo言語で書いていきたいなあ・・・

 

 

二日目(11/12)

　まだコンテストも序盤、そう焦ることはないはず。この日はあまり取り組みませんでした。

 

　今日の取り組み

　初日のコードをGo言語で実装し、正答率を確認してみる。Seed=2での結果がこちら。

やはり正答率が厳しいか。かといってM=100,ε=0.40でまともに当てる方法も思いつかない。上位陣はどうにか判別できるのだろうか。

　なお、M,εがかなり大きい場合はあきらめてN=4にしたほうが良いんじゃないかと思っていたけれど、そんなことはなかった（最悪ケースではよくなるみたいだが、たぶん最高点からの相対得点ではほぼ無だろう）。ビジュアライザを見る限りもう計算のバグはなさそうなのでシンプルに新しい方針が必要。

　いったんHTTFから離れていると、各グラフから、与えられたHが生成される確率を正規分布に近似した確率計算により求めるのがよいのではないかという結論に至った。どうやら良い方針のようで、この時43位になった。

 

三日目(11/13)

　今日はほとんどコードを書きませんでした。前日に思いついた正規分布に近似した確率計算に希望を見出したのでそれをもとに構想を練っています。

今日は

・ローカルでseed=0,...,99の100ケースを試す機能

・より筋のよさそうな確率計算

をして多少改善しました。

 

四日目(11/14)

　三日目に考えていたことと合わせて、一応今回のコンテストでの方針を固めました。今回は順位表が相対評価であることもあって、どの部分に伸びしろがあるのかよくわからないです・・・。

 

今日の取り組み

今回の方針をまとめてみる。

1. epsが大きくなるにつれて極端に頂点数が増えるようにNを設定（(1-2*eps)が分母に入るようなのが正解か・・・？）

2. Gとして極端なグラフを用意（一部の頂点から大量に辺が伸びているのがよさそう？）

3. 与えられたHをGに可能な限り寄せる

4. GとHの差を確認し、その差がありえるかどうか計算する（各頂点で、辺の数の差は頂点数が十分大きいなら平均(N-1)*eps,標準偏差*1^(1/2)に従う？）

 

と書いたところで、突然強くなった。

　これはM個の極端なグラフの取り方によるものであろう。Gとして下の二種類を考えてみると、パターン1とパターン2は意外にも各頂点から出ている辺の数という点では十分区別できるようだ。

上二つは一部の頂点からあらゆる頂点へと辺が伸びている一方、下二つは一部の頂点間でのみ辺が伸びているため、3でのグラフの寄せ方次第ではかなりの差が生まれる。

パターン1

パターン2

この二タイプが区別できないようなエラー率のものはもともとはもっと壊滅的なので、純粋に全ケースで改善したと思われる。

一方でGの多様化により従来の3.の寄せ方（辺の多い頂点順に並べる）ではあまり正しく近づけなくなったので、3.の寄せ方として「i番目とj番目を入れ替えてみて、グラフの差が小さくなれば採用する」を繰り返すというのを実装するのがよさそうだ。

 

五日目(11/15)

　昨日はかなり得点を伸ばせたのでこの調子で進みたいところですが、今日は少しおやすみ。少しコードがまとまっていないので、最低限整理していきます。

　脱線しまして、ちょっとしたお話。私のコンテスト中の取り組み方は

思いつきを雑に実装→良ければ採用→思いつきを雑に実装→良ければ採用→...→一旦雑な実装を整理→思いつきを雑に実装→...

という風になっています。こうやって見ると山登り法みたいですね。思いつきは採用されないことも多いので、思い付きを実装するときに形を整えてしまうと時間がかかってしまいます。また、一つの思い付きを採用したのちにすぐ整えてしまうと直後の思い付きで破壊されることもあるので、ある程度良いタイミングを見計らって整えています。ほかの方はどうなさっているんでしょうか。

今日の取り組み

　昨日の実装で、方針3.のグラフの寄せ方としてグラフの頂点のswapを考えることになったので最低限の高速化が必要か。とりあえず文字列として辺の情報を持っておくのはあらゆる点で効率が悪く、早急に作り直したほうがよいだろう。ということでbitBoardになった。

あまりに思いつくままに書いていたので構造体、関数定義をしながら、HをGにできるだけ寄せる作業ができているか確認。

　swapも実装できたが、ちょっとswapの性能に自信がないので正規分布による確率計算ではなくグラフの差を評価基準に提出してみた。合計点が下がったが、意外と正規近似の際と張り合っている。

 

六日目～(11/16~11/20)

　急に雑になりました。というのも、この日以降なかなか改善ができない中でMON.T+α本人が執筆をあきらめてしまったからです。というわけで、コンテスト後の私がこの後の改善についてお話します。時間がたってしまっていることもあり、かいつまんでの紹介になります。紹介する順番ですが、互いに関係するところのみ時系列順です。

　六日目以降の取り組み

・確率計算、もうちょっとしっかりさせてみる

以下のようなHを考える

今回注目してほしいのは二列目の部分。上のHの二列目の形は下二つのGならどちらから生成されただろうか？

　

確率的に高いのは圧倒的に右（後者）である。これの詳しい話はAtCoder公式解説放送でお話しされていたので割愛。一方、5日目までのの計算システムではepsが小さめの時「わずかに右のほうがあり得る」といった結果だった。

　よくよく考えれば、「本来あるはずの辺がなくなっている」「本来ないはずの辺がある」数のカウントは足し合わせないほうが良い気がする。この二つを区別すると、左のグラフでは「5本のうち2本の辺がエラーでなくなった」右のグラフでは「なかった9本のうち2本の辺がエラーで増えた」となり、しっかり確率に差がつきそうだ。多少改善した

・確率計算、もっとしっかりさせてみる

　今の確率計算、そもそも問題点として、「エラーの起こる数の確率分布（二項分布）が正規分布に近似できるのか」という問題がある。

うーん・・・。epsが小さくて頂点数が小さいときは正規分布に近似できるかというとちょっと違うか・・・。と思うと同時に、「えっ頂点数少ないときは別に二項分布からそのまま計算したらいいのでは」ということに気づき実装した。

 

・eps=0のとき、あらかじめグラフ用意しておく

頂点数6のグラフは頂点の番号を区別しなくても100通りあるのであらかじめ100種類のグラフを用意した。

頂点数4,5のものも用意しておき、Mが小さいときは頂点数4,5のものを使用した。

 

・eps=0.01,0.02...のときもあらかじめグラフ用意しておく

epsがかなり小さいときはほとんどエラーが起こらないはずなので、互いのグラフの差が一定以上あるようなグラフ100個を用意すればよいということに気づいた。

大体eps=0.04くらいまでのものはN=15くらいまでで抑えられるようになった。

0.05あたりからは頂点数も増え、グラフを可能な限り近づける機能の能力限界により厳しかった

 

・与えられたHのグラフをGに寄せる方法、むちゃくちゃ無駄が多かった

これ、もう少し早く気づいていれば・・・。

swapを繰り返して求める方法、結局のところ行きつくのは局所解だったのだが、swapにおける局所解なら実はかなり簡単な貪欲法で見つけられたのである。そのうえ、こちらが決めたM個のグラフは形が単純なうえ大きく分けると二パターンしかなく、二パターン目は01を反転させたものになっているため、

貪欲法でHの頂点番号を決める→M/2個のグラフについてswapにおける局所解

Hの01を反転させた場合の貪欲法でHの頂点番号を決める→残りM/2個のグラフについてswapにおける局所解

となっていた。これにより超高速化を達成し、最終提出では1クエリ当たりこの貪欲法を無駄に数千回繰り返すものになっている。（一応初期解に多少依存するので、完全に無駄というわけではない）

おそらく大体こんなところです。

最終日のプログラムではSeed=2の場合はN=100で全問正解できるようになりました。二日目の自分にこの結果を見せたら喜ぶだろうなあ・・・

 

 

*1:N-1)*eps*(1-eps