- 0.はじめに
- 1.問題
- 2.ビジュアライザを眺める
- 3.最初の提出
- 4.希望通りの区分けができた一番細い列幅を答えとする
- 5.ベストスコアとは何かを考える
- 6.スコア計算を実装する
- 7.テストケースの分布を調べる
- 8.考察からの列の数と列幅をランダムに選択した山登り
- 9.列数を増やしてみる
- 10.今後やりたいこと
- 11.一番最後の最後のパーティションを固定してみる
- 12.前の日のパーティションを使えるかの判定を加える
- 13.ベストな列幅（縦線の区切り）を考える
- 14.テストケースの中にi番目のMAX希望面積の和が100％を越えないものがどの程度あるかを調べる
- 15.2つを組み合わせてセットにして考える
- 16.複数個所に置ける場合に評価値で選択する
- 17.初期解を改善する
- 18.初期解の改善2
- 19.列幅を近傍遷移させてみる
- 20.評価関数の修正
- 21.前日の区切りを使う
- 22.最後の提出
- 23.終わりに
- 24.最終結果（2024月4月11日更新）
0.はじめに
はじめまして、もしくはお久しぶりです。競プロ歴4年4か月のかえでです。
今回は、 MC Digital プログラミングコンテスト2024（AtCoder Heuristic Contest 031）に参加しました。開催期間は2024年3月22日(金)19:00から2024年4月1日(月)19:00までの11日間の長期コンテストです。月曜日までの開催のため、今回は4月1日を休日出勤の振替休日として取得しました。最終日までがんばるつもりです。
さて、今日は3月23日、土曜日の朝です。すでに昨夜からコンテストは始まっています。最初の提出をして、考察をしながら眠りました。今回の問題と今考えていることをご紹介しながら解き進めたいと思います。そして、この参加記を読んでいる方にヒューリスティック・コンテストとはどのようなことをするコンテストなのかを知ってもらえたらうれしいです。一方、AHCの解説には誰でも解法を載せることができるので、コンテストに参加していた方にはぜひ解法や参加記を載せてもらえたらうれしいです。
それでは始めましょう。
1.問題
Event Hallという問題です。内容を簡単に抜き出すとこんな感じです。
- イベントホール（(0,0)から(W,W)まで）が1つある（W=1000で固定）
- D日貸し出す（Dは5以上50以下）
- 各日にはN個の予約が入っている（Nは5以上50以下）
- 各予約のそれぞれ希望面積Aiを考慮して長方形Biを割り当てる
- Biが希望面積より小さいとコストがかかる（100×（Ai-Bi））
- またパーティションを設置することになるため、その設置と撤去を行う際はコストが長さ分（L）かかる
- コストの合計が出来るだけ小さくなるように、貸し出す長方形区画を決定する。
2.ビジュアライザを眺める
最初に行うことは問題文中にある「例を見る」をクリックしてビジュアライザを開きます。
seed0のビジュアライザを眺めます。長方形が並びます。
長方形にカーソルを合わせると長方形の詳細が出ます。aが希望面積で、bが実際に割り当てた面積のようです。
3.最初の提出
問題文中のPythonのサンプルコードをC++に直して入出力の確認をします。k 番目の長方形として左上が (k,0)、右下が(k+1,W) のものを出力しているので、少しだけ工夫して、kとk+1の代わりに希望面積に合わせて縦の長さを調節したいと思います。
最初の提出をしてみると、50ケース中23ACして27WAが出ました。
WAなので絶対スコアは0点ですが、相対スコアは23ACの分から算出されます。相対スコアの順位は180人中50位でした。
区画の境界がダブっていたので修正します。提出するとWAは16個に減り、4.7Gくらいになりました。希望面積をかなえるように切り上げをしたので、Wを超えた値を出力しているケースがあって、WAになっているのだと思います。seed0ではスコア80001になりました。
4.希望通りの区分けができた一番細い列幅を答えとする
時刻が今朝（土曜の朝）の状況に移ります。寝ているときに考えていたのは、余りが少なくなる長方形の作り方です。今は横の長さをWに固定しているので、例えば希望面積が1010みたいなときは990余計に多い面積を渡してしまっています。横幅を1000ではなく500にすると余分を490にできます。というわけで、制限時間が3秒あるので、色々な横幅を試して一番スコアの良いものを提出するコードにしたいと思います。
パーティションの設置や撤去に関してはまだ何も考えていません。
例を見るのような個別の長方形の作成はその次にやってみたいと思います。
列幅を50,100,200,250,500,1000の6種類に分けて、それぞれ面積を確保します。小さい列幅から試して、面積通りに置けるものができたらそれを出力します。実装して提出をしました。まだ50ケース中11ケースでWAが出ます。
しかし相対スコアは上がって順位は提出前の151位から41位に上がりました。
seed0のビジュアライザです。幅500で入れたことによりスコアが40018まで下がりました。中央のパーティションをずっと置きっぱなしにできる分、幅1000よりもスコアを下げることができています。
WAをなくしたいので、もしどこにも入らない場合は他のものを削るかそれ自身の面積を削って配置することを考えます。その場合、余りが大きいものから削っていきたいと思います。
また、列幅を等間隔ではなく大きいものから小さいものまで複数を組み合わせて、1列をNをその列で割ったくらいの数に等分に分けられるように調整できたらなあと思います。
5.ベストスコアとは何かを考える
買い物に行っている間に考えていたことがありました。相対スコア1,000,000,000です。1ケースだけトップと同じスコアを取っていると考えると良さそうです。ベストなスコアとは何かといえば、初日に作ったパーティションのまま最終日まで使えること、かつ全て希望通りの面積を割り当てることができることです。そのときのコストは1。これがベストスコアになります。
それは各日の割り当てる部屋の希望面積のmaxを初日に割り振れば良さそうです。
自分の今のseed0も全て希望通りの面積を割り当てられているので、コストはパーティションの設置・撤去のみにかかっています。およそW×（D-1）×（N-1)くらいになっていると思います。そう考えると例えば一番下にあるパーティションは作成しなくても良いので、それを作らないだけでも今よりコストが1割ほど減ります。
一番下のパーティションの設置をやめることと、ベストな設置ができるかを最初に判断するコードを書いて提出します。
バグっていたようで40WA。それでも100位のスコアが出ました。
修正して100テストケースを試します。まだスコア計算は実装出来ていないので、配布されているツールを使用しました。
WAはもったいないので、初期解として縦をN等分、横はWとして答え入れておくことにしました。
コードを書いて提出すると、やっとACしました。絶対スコアは10,823,595,500、相対スコアは5,734,643,914、順位は452人中54位になりました。
6.スコア計算を実装する
実装しました。しかし微妙にずれます。例えばseed0では本当のスコアは32001なのですが、自分の計算結果だと31937みたいな感じです。だいたい合っているのでひとまず良しとします。
7.テストケースの分布を調べる
テストケースの分布も調べます。1000テストケースで希望面積がWの2乗（1000000）のうちどれくらいを占めるのかを調べた結果です。入力生成方法に書いてある数式が分かる人はそれを見れば同じことがわかると思います（私はわからないので生成された入力ファイルを解析しました）。今回はPythonのMatplotlibを用いてヒストグラムを作成しました。これまでは全てエクセルで処理していたのですが、少し成長したかもしれません。
空きスペースの割合が大きいものを1個でもベストスコアに持っていければ1Gアップするのでそれを目指すことが最善な気がします。
8.考察からの列の数と列幅をランダムに選択した山登り
- 貸し出す面積が小さいと100倍のペナルティがつくので、希望面積は極力叶える方がよいということ。
- その次にパーティションを動かすこと（設置と撤去）を少なくすること
を考えます。自分の方法だと縦のパーティションを固定しているので、縦横を設置するよりパーティションの設置は半分のコストになっています。
- 前の日と次の日を共通のパーティションで使いまわせるだけで、コストが下がります。
ビジュアライザで100テストケースを見てみましょう。10ケース程は初期値のままで希望面積を達成できていないので赤で表示されています。
見てわかることは結構空きスペースが余っているということ。1つずつの区割りをもう少しずつ広げれば使いまわせるように思います。全部の区割りをMAXにできるかを考えていましたが、1つの区分けをMAXにできるかを試してみることにしたいと思います。と思ったのですが、思った以上に値がばらけているので、次の日も使いまわせる設置を試すことにします。
また列の幅を6種類作っていましたが、列幅が50と100のものは使用されていなかったので、列の区切りは最大5分割としたいと思います。
それから、100テストケースのうちseed32でスコア1を達成していました。おおー、うれしい。
制限時間はまだまだ余っているので適当なケースを試したいと思います。
- 何分割するか（列数）をランダムで決める（分割0から5まで）
- どこで区切るか（列幅）をランダムで決める
- 貪欲に詰め込む
書いて提出しますがCE（コンパイル・エラー）でした。自分は言語にC++を使用しているのですがインクルードにsortを入れていなかったからです。AHCのときは#include <bits/stdc++.h>を使わないようにしていて、必要なものだけを追加するようにしています。CEの場合、30分待たずにすぐに提出することができました。結果は1ケースWAが出て0点。デバッグしたところ、唯一のスコア"1"になるケースを間違えていたようです。
相対スコアは提出前の4,401,053,582から1G落ちて89位から110位になりました。
修正して再度提出します。今度は4WAしました。しかし相対スコアは6,131,933,301に上がり、順位は593人中61位になりました。
ランダムに決めた際の計算や答えの出力が間違っていたので修正しました。提出をします。久しぶりにACしました。
相対スコアは8,018,429,224になり、605人中48位になりました。
おー！
思わず顔がにんまりします。コンテスト中に50位以内に入ったことはないかもしれません。うれしい。乱択で適当に作った列に貪欲に詰め込んでいく山登りですが、思った以上に効果があり驚きます。
seed0ではスコアが6458まで下がりました。
9.列数を増やしてみる
- スコア計算の2次元配列を1次元にしたら少し試行回数が増えました。
- 適当な列幅を2列から5列にしていたのを2列から10列までに増やしてランダムで選択するようにしました。
明らかにスコアが良くなりました。提出します。
ACしましたが、絶対スコアはほんの少しよくなった程度です。希望通りにできないもののコストが邪魔で改善が見づらい気がします。
相対スコアは提出前の7,942,825,053から10,734,837,719に上がりました。順位は55位から31位に上がりました。
おおー！！！
解法ガチャに当たったのかな。最後までこの成績を維持したいものです。最終的には1000人を超えてくると思うので、まだ参加していないけどこれから参加してくるだろう人が400人以上います。どうなるのかなー。わくわく。
初期解を改善します。均等割りを面積比に応じて行うようにしました。絶対スコアは前回の3.8％くらいにまで減少しましたが、相対スコアは提出前の10,752,445,568から10,613,894,861に下がり、順位も1つ落として37位になりました。
自分のイメージでは50ケース中、1割が初期解のまま（希望の面積の矩形を振り分けることができない）だと思っていて、それらが10分の1くらいのスコアになったと思っています。相対スコアが変動しないところから、やはりトップは全部希望通りの区割りができているのだなあと思いました。
初期解を微修正して再提出します。絶対スコアはさらに小さく、半分以下の104,137,020になりました。
相対スコアと順位はほとんど変わりません。
10.今後やりたいこと
さて、日時は2024年3月24日日曜日の夜9時です。まだ残り7日間あります。これから試したいことを書きだしたいと思います。
- N個の予約のそれぞれi番目の予約のMAXの総和がWの2乗（総面積）を超えない場合は最初にうまく長方形の形を作るとスコア1を達成できる。
- 連続する2日間を比べて、同じパーティションを使うことができないかを調整する。
前者ができると得点アップ必至です。ただ難しそう。
まずは後者から取り組んでいきたいと思います。例えば、seed2のビジュアライザの赤矢印の部分を見ると、パーティションを撤去して設置しています。しかし、境界をうまく調整すれば、同じものを使用できるのではないかと思っています。
11.一番最後の最後のパーティションを固定してみる
自分の解法だと大きい方の面積から順番に左上から貪欲に割り当てるため、一番最後の列の一番最後が希望よりも大きいスペースを割り当てているのではないかと思っています。
そこで一番最後の最後の面積のMAXに合わせて右下に固定スペースを設けてみることにします。これがうまくいけば、全ての列で下から合わせるといったことをしてみたいと思います。
できたので提出します。バグっていたようで39AC,11REが出ます。相対スコアは提出前の55位8,413,284,208から60位7,537,430,339に下がりました。どの部分でどの程度スコアを獲得できているのか、相対スコアの推定が大切なので記録しておくことにします。
100テストケースを試して確認します。ゼロ除算をしている箇所があったのでコードを修正してもう1度100テストケースを試します。修正できたので再提出をします。
今度はACしました。絶対スコアは、104,077,568と59452下がりました。相対スコアは前々回の提出より上がって8,603,976,860になり、761人中52位になりました。
良さそうです。とりあえず各列の一番下を修正してみます。提出してみましたが、スコアは良くなりませんでした。うーん…。
スコアが悪くなることがあるようだったので、スコアが良くなるようだったら採用するように修正して再提出をします。
これも変わりません。うーん…。
次は前のパーティションを使えるかどうかの判定に切り替えたいと思います。
今日は平日でもう夜遅いので、続きは明日行いたいと思います。
12.前の日のパーティションを使えるかの判定を加える
バグらせながらも何とか実装します。提出すると、絶対スコアも相対スコアもほんの少しだけ良くなりました。絶対スコアは103,896,189になりました。相対スコアは提出前の7,952,729,237から8,240,438,437になり、順位も58位から57位になりました。
この辺の改善はもうやめて、根本的な別のアイデアに移りたいと思います。
と思ったのですが、時間が経ったら貪欲に詰め込むのをやめてもう少し考えたい気がしてきました。
- 詰め込む順番を変えてみました。
あまり良くなりませんでした。
- ランダムで作る列の数を1から10だったのを、N/3からNの間に変更しました。
ランダムのベストスコア更新が増えました。100テストケースでも改善していそうなことがわかったので提出をします。しかし、絶対スコアは悪くなり、119,628,970になりました。
これに反して相対スコアは、提出前は7,819,097,702、66位でしたが、8,829,654,144、813人中56位に上がりました。
ベストな列幅を事前に求めることができると良さそうだと思いました。
思い出したので、スコア計算を高速化します。W×Wの盤面に0,1を入れて前日とのXORを取っていたのですが、unordered_setで線分上だけを計算することにしました。
提出しますが結果はほぼ変わりませんでした。
13.ベストな列幅（縦線の区切り）を考える
現在のseed0のベストスコアは2628です。区切りの数は7個。
最後にもう一度記録として出し直しておきます。
眠くなったのでここで終了。2024年3月26日火曜日の夜でした。まだ5日間あります。
14.テストケースの中にi番目のMAX希望面積の和が100％を越えないものがどの程度あるかを調べる
昨日は仕事が忙しくてAHCに取り組む時間がありませんでした。今日は2024年3月28日木曜日の夜です。今日もあまり時間はないのですが少しだけ考察を進めました。
100テストケースのうち、100％を越えないものは1ケースだけで、それはスコア1を達成していました。
これを見て思ったのは、2つのものを合わせてSUMを取り、100％を越えない組み合わせを見つけることができれば、コストを小さくできるのではないかということです。1つのスペースだけ区切りを変えてあげれば良いのではないかと思います。
調べてみます。Nの階乗かかるので、Nが大きいときに全通り調べるのはあまりうれしくない気がします。大きいもの2つ、小さいもの2つ、大きいものと小さいものの2つをとりあえず調べてみます。
seed0を見ながら組み合わせてみますがうまくいきません。その日の中で一番他よりも外れて大きいものと外れて小さいもののセットを考えます。8番目と9番目をセットにして考えるとmax面積が97.5%になりました。これなら8番目と9番目の間の区切りを入れ替えてそれ以外は固定したスペースを割り当てることができそうです。週末はこれを実装したいと思います。
- 良さそうな組み合わせを列挙する
- max面積が100％より下になったら1日目に固定の区切りを作る
- 2日目以降はセットにしたものの間の区切りだけを調整する
現在の相対スコアは8,135,917,618、すでに902人中86位まで下がっています。週末に巻き返せると良いのですが。
15.2つを組み合わせてセットにして考える
2つを組み合わせてみましたが、100％を切ることができたのは100ケース中1個、seed0のみでした。軒並み悪化してしまいました。別の方法を考えてみたいと思います。
16.複数個所に置ける場合に評価値で選択する
2024年3月30日土曜日の朝です。コンテストは残り3日間になりました。やっと週末を迎えてAHCに取り組む時間ができました。現在の順位は102位、7,681,965,321点です。推定パフォーマンスも青パフォまで落ちています。ここから何とか少しでも改善できればと思います。
そういえば、と思い出して、前日のパーティションのまま使えるかどうかで複数個所に置ける場合の評価値を出して、それがいちばん良い場所に置くことにします。これまでは最初に見つかった置ける場所に置いていました。
seed0のスコアは2386になり、久しぶりにスコアを更新しました。
評価の方法が難しくまだうまく書けません。とりあえず面積500くらいの差なら採用するとしました。100テストケースで少しだけよくなったので久しぶりに提出したいと思います。絶対スコアは117463679、相対スコアは7,909,071,063になり、順位は96位になりました。
17.初期解を改善する
希望の面積で区分けできなかったseed34ではスコアが23,986,401といったように、大きなコストがかかっていました。これを各日ごとに達成できたらOKとする初期解に修正しました。全部の日は区分けできないままですが、seed34では16,792,638になる等、少しだけよくなりました。提出をします。
初期解にスコア計算を入れたら3つTLEしました。あれ？達成が難しい面積のものが思った以上にスコアに影響があるようです。
スコアの修正とTLEの修正をしました。ループは前よりも回っています。提出前の111位からほんの少し上がります。うーん、良い改善にはなかなかつながりません。停滞期に入ってしまいました。
疲れたのでお昼寝をします。起きて、ああ、そうだと思って、余りが一番少なくなる列に入れるように変えました。提出をすると、97位になりました。
上がるんだ...
相対スコアが1Gくらい良くなったので、正直なところ驚いています。100テストケースを試した結果はちょっと良くなってそうくらいだったので。
ずっと「余りを少なくする長方形」というものを考えていました。作り方がわからないと思っていました。しかし、評価するときには使えるのだなあと思います。
案が尽きてきました。今は正方形の中に正方形を入れるみたいなことを考えています。これは希望面積をかなえることができずにいるケース用の解です。ルジンの問題というものが出てきて、こんな風に隙間なく正方形を入れてみたいなあと思いました。
とりあえず縦:横=2:1みたいな長方形で埋めてみたいと思います。
18.初期解の改善2
2024年3月31日、日曜日の朝です。コンテストは残り2日となりました。今回は月曜日に振休を取っているので、月曜にもまだ時間があります。考えていることは2つです。
- 希望面積の和が100％に近いものを希望通りに区分けすること
- これまでの列に分けて詰め込む際の選択をプレイアウトで選ぶこと
順番にやってみようと思います。今朝の順位は109位。少しでも順位を上げるようにがんばりたいと思います。
と思ったのですが、先に正方形の中にどのような長方形を作ればよいのかということをあらためて考えてみたいと思います。
考えていたけどわからず、眠くなってお昼寝してしまいました。起きたのでとりあえず実装してみます。最後の1個が入れられなくなるものがほとんどだったので、一番面積が希望通りにできるようものにしました。seed34だと残り3000くらいの面積が足りなくなります。seed34ではスコアが16,792,638から7,953,368 になりました。100テストケースで2、3個スコアが良くなりました。提出します。
絶対スコアは半分ほどの79,985,785になりましたが相対スコアは提出前の8,103,930,362、114位から7,755,439,892、120位に下がりました。提出者は1000人を超えて1007人になっています。
うーん、前回の提出との差分を取った方が良さそうです。こんなに下がるのはおかしい感じ。前回の提出とランダムで選ぶ列幅を変えた気がするので元に戻したいと思います。提出をします。絶対スコアはほんの少しだけ悪くなり、相対スコアはほぼ元に戻りました。うーん、うまく作れないところの改善はほとんど影響がなさそうです。それよりも列幅の選択で違いが出るということを考えると、試行回数が足りていないのかな。
ちょっと時間を伸ばして結果を見たいと思います。
時間を伸ばしてみましたがスコアは良くなりません。詰め込み方が貪欲だからでしょう。
というわけでこれまでのベストと比較しがら、swapができないかを考えてみます。swapした後の評価方法を考えます。スコアですよね、やっぱり。
ランダムである一定より良い何かが出たらそれをswapするみたいなことにしてみたいと思います。その時間があるのか、現在時間で回している箇所を1秒短くしてみます。結果は大丈夫なものと少し悪くなるものとある感じです。
1秒を使って1箇所入れ替えるということを繰り返してみたいと思います。
うーん、良い方法が思いつかないので一旦散歩に行ってきます。
19.列幅を近傍遷移させてみる
先ほど列幅が思ったよりも大事そうということを思っていました。散歩しながら考察して思ったのは、各日にちのAのMAXを列幅として採用していくということ。ちょっと実装してみたいと思います。
100ケースのうち2、3ケースで良くなった気がします。提出をします。提出前の順位表は113位です。相対スコアは8,158,382,020から8,221,262,265になり、ほんの少しだけ上がりました。順位は1022人中113位のままでした。
次はランダムである程度よくなった解の幅を近傍遷移させてみます。±2で幅を遷移させてみると、100テストケースを回した結果少しよくなっているようでした。
提出します。
提出前の相対スコア8,079,112,690が8,110,190,770に上がりましたが、順位は1030人中113位のままでした。
うーん…。
列幅固定ではなく、格子状にして横でも縦でもどちらにでも拡張できると良いなあと思いました。
20.評価関数の修正
どの列に置くか複数の選択肢がある場合、余りが少ない方から選ぶように評価関数を書いていました。が、ふと間違っていると気がつきます。余りが少ないというのは列幅から余りを引いた数のつもりでした。真逆のものを選んでいる気がします。
修正してみました。良くなっているものと悪くなっているものが半々です。
提出をしてみると、絶対スコアも相対スコアも悪くなりました。相対スコアは提出前の8,045,085,122から7,694,456,908に下がり、順位も122位から127位に下がりました。
21.前日の区切りを使う
列幅を近傍遷移させる際に、前日の区切りを使うようにしてみました。
提出します。提出前の120位から202位にさがりました。
おお！なぜ？
100テストケースでは良くなるものと悪くなるものが混ざっていて全体だと若干悪くなる感じでしたが、seed0で1183にスコアを更新していたので喜んで出していました。
絶対スコアが参考にならないので、評価が難しいなあと思います。
評価関数がまちがっていました。修正します。んー、間違っていたわけではないのかもしれません。
- 希望面積を叶えるときには前日の区切りを使って、その後達成でき無い（残りの面積を足すと100％を越える）ときは評価を下げる
どこかおかしい？よくわからなくなったので、120位だったコードを再提出しておきます。提出結果は127位になりました。結構ぶれます。正直システムテストでどれだけ下がるのか心配になってきました。
うーん、初期解をいじってみたりしたものの、あまり変わらず。今回のコンテストはこれで終了したいと思います。
一番よかったseed0のスコアは1183でした（再現できず）。
22.最後の提出
終わりにしたと言いつつまだ時間があったので、N,Dでのクロス集計をして、各アイデアの結果のよかったところを寄せ集めてみました。
- Dが少ないときは列数を1からNから選択する（それ以外はN/3からN*2/3）
- Nが10以下のときは後半で今一番良いスコアの答えから列幅の近傍遷移を行う
提出をします。絶対スコアはこれまでのベストの78,368,848になり、相対スコアは提出前の7,627,601,033、133位から7,903,195,390、128位に上がりました。
これを最終提出として終了したいと思います。
23.終わりに
コンテスト最終日、2024年4月1日のお昼です。出だしは好調だったものの、何も分からないまま終わってしまったなあと残念な気持ちでいます。どんな状態になると良さそうかといえば、パーティションを動かさずに済むことだろうと考えました。しかし、じゃあどうやってそれを達成するのかといえば、それを実装するのがとても難しく感じました。
頭の中にはAHC001が思い浮かんでいました。縦に長い長方形を横に長い長方形に変形しないとスコアが改善しないイメージです。私は縦のラインのパーティションを動かさないという縛りの中で改善を続けてきましたが、たとえばもう少し縦のラインを動かしても良いとか、取り払ってしまっても良いといった柔軟な動かし方をすればスコアが良くなりそうだと思うものの、どうやって実装しようかと考えている途中で手が止まってしまいました。
上位の人や他の人はどんな解法を考えたのだろうかと気になっているところです。
コンテスト終了後はAHC031の感想会をXのスペースで午後9時から行う予定です。自分の解法を話したい方も他の人の話を聞きたい方もお気軽に参加してもらえればうれしいです。一緒にクールダウンをしましょう。
また、明日2024年4月2日の午後8時からはAtCoderLiveでAHCラジオの配信も予定しています。wataさんからどんなお話を聞けるのか、今から楽しみにしています。そちらもぜひご覧ください。
今回もたくさん考えて、いろいろなことを試しました。ヒューリスティック・コンテストのおもしろさが、少しでも多くの人に伝わるといいなあと思います。そして、興味を持たれた方は、次はぜひ私と一緒にコンテストに参加しましょう。コンテストに参加していた方は次もまた対戦よろしくお願いします。
長い参加記をここまで読んでくださり、どうもありがとうございました！
24.最終結果（2024月4月11日更新）
更新するのが遅くなりました。システムテストの結果は2000ケース1WAでした。スコア1は28ケースあるうちの23個で取ることができました。
最終順位は暫定順位の131位より下がり137位でした。システムテストの途中でジャッジの経過がWAに変わり、ドキドキしながらシステムテストが終わるのを待ちました。もっと悪くなるかと思ったのでよかったです。
wleiteさんの作ってくださった統計資料を見ると空きスペースが少ないものの結果がとても悪かったです。うまく詰め切れませんでした。まだまだやれることはもっとあるなあという感じです。
AHC031 - Event Hall - Statistics
MC Digital Programming Contest 2024
— Wladimir Leite (@wleite) 2024年4月1日
AtCoder Heuristic Contest 031 #AHC031
Statistics:https://t.co/893alMSKDY
AHCラジオではwataさんが問題の解法について詳しく話してくれています。とてもおすすめなので、コンテストに参加した人全員に見てもらいたいと思っています。私も出演しています。パッと理解することができずに恥ずかしい箇所もあるのですが、後からそうかー、そうだよなーなどと思っています。後半の計算を軽くする詰め方の話は必見です。
コンテストの結果、ヒューリスティックのレーティングは56上がり、1656になりました。前回1600になったときはこれ以上レーティングを上げることができるのだろうかと絶望にも似た気持ちを感じましたが、まだ上を目指せるのかもしれません。これからもがんばっていきたいと思います。
