競プロ始めました-kaede2020-

競技プログラミング初心者向けのブログです

estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)参加記

0.はじめに

はじめまして、もしくはお久しぶりです、競プロ歴2年半のかえでです。

今回は、estie *1プログラミングコンテスト2022(AtCoder Heuristic Contest 014)に参加しました。開催期間は2022年9月17日(土)15:00から2022年10月1日(土)19:00まで。2週間の長さの長期コンテストです。

この参加記は、コンテストの期間中に、自分がどんなことを考えて、どんなことをしたのかをありのままに書いています。コンテストが終わってみれば、間違っていて恥ずかしくなるような考察も、時間ばかりかかって無駄だった実装の過程もそのまま残しています。そのため、役に立つかどうかという目で見れば、正直なところ他の方の解法記事を読んでいただいた方が良いと思っています。

それでもこの参加記を書くのは、「ヒューリスティックコンテストって何?」という人に、コンテストに参加した気分を味わってもらうことができるのではないかと思っているからです。また、自分と同じように悪戦苦闘している人に、いっしょにがんばろうとエールを送ることができるのではないかと思っているからです。だからこれを読んだ人が、「何だか面白そう。自分も参加してみようかな」、「今回はダメだったけど、あきらめずに次もがんばろう」と思ってくれれば、これを書いてよかったなとうれしく思います。

そして、いつものように素敵な問題を作ってくださったwataさんには尊敬と感謝の念が尽きません。本当に、本当にどうもありがとうございます。これからの更なるヒューリスティックの盛り上がりと発展を心から祈っています。

それでは長くなりますが、どうぞ最後までお付き合いください。

1.前夜祭

コンテストが始まる前日の夜19時から、「estieコン2022 (AHC014) 前夜祭」というイベントが開かれていました*2。登壇者は、matsu7874さん、kenkooooさん、kageyuさんです。

kenkooooさんとkageyuさんが、30分間でAHC005にチャレンジしていました。AHC005は、私も参加していた過去に行われたコンテストです。実際のコンテスト時間は4時間でした。イベントの際、自分の提出を見返してみましたが、当日は全部のマスを見ることができていないくらいのイマイチな出来。(青が通ったルートで、ルートから見通せる部分が黄色になります。全部を黄色にし、かつルートが短い方が得点が高くなります。私の書いたコードは左上に白い部分が残ったままでした。)

kageyuさんが、30分という短い時間で、私と似たような状態から全部を黄色に塗るように変えていて、交差点から「一歩踏み込む」みたいな表現をしていたのが印象的でした。短時間でコードを書き上げていてすごい!と思いました。

Rustだったので私は読むことができなかったのですが、実際に考察を口にしながらコードを書いていく様子を見ることができ、とてもおもしろかったです。100人ほどの参加申し込みがあったようで、盛況に終わっていました。

過去のコンテスト中の自分の提出(AHC005)
2.問題文の概要
  • 2次元のグリッドに、あらかじめ点があります。
  • 今存在している3点に、格子上の新しい1点を足して、長方形を作ります。
  • 長方形は、水平、垂直か、斜め45°の線分のみを使用することができます。
  • 実行制限時間は5秒。スコアは次の通りです。

スコア計算式(AtCoder問題文より引用)

問題文から「例を見る」リンクを開くとseed0のサンプルを見ることができます。

atcoder.jp

3.最初の考察

コンテストが始まりました。2022年9月17日土曜日。時刻は15時15分。すでに問題文とビジュアライザを見ました。

今回はスピード提出を目指します。

最初に考えたこと

  • 使用していない点を1個ずつ見て、距離1(もしくは1辺が1←この辺は思考中)の長方形が作れるか、距離2の長方形を作れるかを端から調べていく。

でも無駄なことが多そう、と思って別のことを考えます。

  • 印のある点をランダムで1個選んで、半径もランダムで1個選んで、あと1個印を追加すれば長方形ができあがるかどうかを調べる

という方が効率が良さそうだと思います。ある点を選んだとき、1辺もしくは半径が決まっていれば、上下左右の8回調べれば良さそうです。

ただ、実装にちょっと時間がかかりそうなので、もっとシンプルなものを考えます。

  • 正方形を作る

これからスタートしようと思います。

今回は前夜祭のイベントでmatsu7874さんが話していたような、まずは「行って戻る」みたいなシンプルなコードから書き始めたいと思います。

4.最初の提出

さて、ビジュアライザを見ると、0のときも得点が出ます。そこで一番シンプルなコードを書きました。

  • 入力を受け取って、全て0を出力する。

しかし提出をするとWA。なぜ?と思いましたが、coutではなくcerrで出力をしていました...。一旦ACを取ってからコードの続きを書こうと思ったのに、相変わらずの凡ミス。ああ、30分もったいない…。

気を取り直して、今回のAHC014でもseed0のビジュアライザが共有OKだったので、他の方の共有してくれた画像を見ると、幾何学模様の、きれいな画像ができあがっていました。すでに30万から40万のスコアが出ています。

ひぇー、早すぎる!と思いますが、提出された得点と比較すると、どうも手動で出力した結果のようでした。さっそく私もビジュアライザのマニュアルモードを試します。

クリックをしてポチポチと頂点を追加していくのですが、正方形や長方形ができる場所にカーソルを合わせると、ちゃんとできるということを示して辺を表示してくれるので、面白い!簡単に点を追加していくことができます。

また、これを試すことによって、辺の重複が許されないというルールがわかりました。

  • 使用した辺は重複して使えない。

自分の理解が足りていなかったので、とても役に立ちました。また、ビジュアライザを試していてわかったのですが、外側に点を広げていくことが肝心ではないかと思います。このseed0が全面に幾何学模様の花で埋まるのではないかと想像したら、ものすごくわくわくしてきたのでした。

ビジュアライザのマニュアルモード(seed0)

そうこうしている間に30分が経ちました。無事ACして14048321点を獲得します。開始直後にこの点数がずらっと並んでいたのに気がついた方もいるかもしれません。それには、こういう理由があったのでした。

初提出(0を出力。得点14048321)
5.考察の続き

話を戻します。

  • ランダムで頂点を選択し、ランダムで1辺の長さを選択し、正方形ができるかを調べて、出力しました。

しかし、使った頂点の組のみをチェックしていたら、辺上に別の頂点がすでにあることがあってスコアが0になりました。

ランダムで頂点を選択、1辺もランダムで選択したところ(seed0)

もっとシンプルにしないとダメだと思います。

  • 辺上に別の頂点が来ない長さ(=1辺が1)の正方形を作る

これを満たすものだけを作成することにします。数的にはちょっと寂しいけど、思ったような正方形ができました。

ランダムで頂点を選び、1辺の長さが1の正方形を作る

これを提出するとRE。なぜ?と思います。Nの最大を勘違いして、配列外参照をしていました。まだテストケースを連続で試す準備をしていなくて、Web版ビジュアライザで2、3個テストケースを試しては提出しています。思い込みでがっつりコードを書き始める前に、考察をきちんとしようというのが今回の目標です。あと、最終提出にするコードは、テストケースを2000ケース試そうと思います。もう1回提出するには、30分待たなければいけないので、待っている間にこのブログを書いています。

ところで、seed0の共有されたビジュアライザですが、しましまさんの提出がきれいでした。これを見ると何となく、良い動き方がありそうだなあと思います。

  • 点を追加した後に、その点を使ってまた長方形を作る

これができると効率が良さそうです。また、全面に作らなくても76万スコアが出るのだなと思いました。

今回の目標:一歩ずつがんばろう。

あれれ?提出してみたら、REはなくなったものの、WAでした。

なぜ?あ、それも1個だけ。これはもう連続テストケースをまわさないと見つからなそうです。ローカルでテストケースを試す実装をしたいと思います。まだ、スコアの実装もできていないし、やることは盛りだくさんです。

6.連続100テストケースを試す

ローカルで100ケースを試すコードを書きました。バグが見つかったので修正します。50ケースの予想スコアは14,861,821点で、実際に提出した得点は14,882,825点だったので、ほぼ同じです。まずはローカルで試せばいいなと思いました。

1辺が1の正方形を書く(得点14882825)

ローカル100テストケースの結果

まだ自分でスコア計算の実装が書けていないので、テキストに出力した結果を使って、スコア計算を行っています。バッチファイルを使って、問題文で提供されている「 Windows用のコンパイル済みバイナリ」でスコアを出しているので、すぐに終わって便利です。スコアはExcelで集計しています。

7.斜めの正方形(1辺が√2)を追加する

さて、1辺が1の正方形が作れたので、次は斜め45度の最小の正方形を作ります。

  • 1辺が√2の正方形(菱形)を追加する。

随分とバグらせましたが、書けました。

1辺が斜めの正方形を追加(seed0、スコア239898)

おお、と思います。明らかに正方形の数が増えました。GIFアニメーション出力がビジュアライザからできるのも便利です。

斜めの正方形(1辺が√2)を追加

100テストケースの結果も良くなりましたので、提出します。得点は17,667,125、順位は110位でした。現在のトップは、Rafbillさんで、得点は51,752,047です。自分もがんばって得点をのばしていきたいです。

得点は17,667,125、順位は110位(295人中)でした(9月18日16時現在)

コードは自分で描いた下の図を見ながら書いていました。

点Aがランダムに選んだ1点で、これはすでにある点の中から選びます。下の赤線の点B1、点C1、点D1のうち2点がすでに存在する点で、1点が空いているときに長方形を作ることにしました。

コードを書くときの座標参考図
8.長方形を追加する

次はサイズを大きくしていこうと思います。

とその前に、GitとGitHubVS Codeを連携してコードのバージョン管理をします。まだ慣れていないので、すぐに忘れてしまうけど、やり方を見ながら何とかコミット。

さて、辺上に頂点があるかどうかは、素直にグリッドで頂点を管理することにします。2頂点をランダムに選択し、縦横、もしくは斜め45度なら、その辺上に別の頂点がないかを確認します。縦横なら長さ1、斜め45度なら長さ√2の位置の頂点位置を調べます。1個なら頂点を加えて長方形にすることにします。

(時間経過)

バグらせたので今日はもう寝ます。

長方形の判定がバグっています

さて、翌日(9/19)になりましたが、まだバグは修正できません。考察を進めます。

長方形の場合、使った頂点を使うと、辺を共有しているのに気が付かないことがありそうです。

<対策>

  • 使った頂点は選ばないようにする配列を追加する
  • 長方形は長方形、斜めは斜めで使った頂点を管理する

これを実装して、10個くらいの結果を見ます。ついに修正できたかも!?何度も裏切られていますが、今回こそと100テストケースをまわします。100×5秒、約8分間、ドキドキしながら結果が出るまで待ちます。そのまま待つと長いので、その間にブログを書きます。

正方形とななめ正方形を2.5秒、長方形(縦長)を2.5秒追加

下がりました。ぐすん(泣)。そうだ、と思い出して、正方形と長方形を2.5秒ずつループを回していたのをに戻します。

あれれ?なんか下がっています。

おまけにあらたなバグの出現です。使った頂点は使っちゃダメなはずなのに…。

またバグです

見つけました。バグ。はぁ。また100ケースまわします。

次の未対応バグ

あ、そうか。斜めの頂点はノーケアでした。うーん、辺を使った管理をどうしようかな。辺上に新たな頂点は追加できるけど、その場合、それを使ってはダメですね。この辺の細かいところが難しい...。その上スコアも伸び悩んでいます。

スコアも伸び悩み

長方形(横)を追加(seed4、スコアは382631→418277になりました)

バグが消えたので、横長方形も追加。スコアは微増。

  • 1辺が1の正方形と最小の斜めの正方形と縦が1の長方形と横が1の長方形をブレンドして制限時間5秒いっぱいランダムで探索する。

これをしていたのですが、とにかくバグります。なんか、辺の管理をきちんと考えて、一気に普通の長方形と斜め長方形を作りたいなと思うようになりました。

これ以上やってもバグが増えるだけ。もっとシンプルに実装したい気がしました。

コードの行数はすでに714行になっていました。

9.仕切り直し。必要な情報を整理する。

必要な情報を整理します。

グリッドの点を3次元配列にして、上下左右、斜めの4方向(右上がり・右下がり・左上がり・左下がり)の8つの情報を各頂点に記録することにします。

各点において使用した線分の方向を記録する

使っている辺がこれでわかるようになりました

配列としては、int used[8][N][N]を用意しました。(これまでは、int used[N][N]にしてバグらせていました。)

また、これまではグリッド上の頂点を1個選んでいましたが、2個を選ぶことにして、対角線上の頂点であるとします。すると、長方形と、斜めの長方形の2パターンをチェックすれば良いことがわかります。かなりシンプルになると思いました。これまでは別の頂点にあたるまで辺を伸ばすといったことをしていました。そして、途中で使用済みの辺に出合っていることを判定できずにバグっていたのでした。

対角線上の2点を選んだときは2パターンになる

つないだあとは、辺上にあるマスを答えの行の数値で埋めることにします。また、新しく追加した頂点も答えの行で記録することにします。

  1. ランダムで2点を選ぶ(頂点を①②とする)
  2. 長方形パターンを考える(頂点を③④とする)
  3. 斜めの長方形パターンを考える(頂点を③’④’とする)

長方形ができる条件は、③(③’)か④(④’)のどちらか1つに頂点があり、すでに使っているマスを通らない、また辺上に他の頂点を通らないこと。

おお、何度かこの文章を書き直しているうちに、余計なものをそぎ落として、だいぶシンプルになってきたのではないかと思います。コンテスト3日目。時刻は9月19日の22時を過ぎていました。

10.いちから書き直す

さあ、もう一度書き直します。とはいえ、入力や出力等の使える部分はそのまま使うので、書き直すのはシミュレート部分です。

長方形も斜めの長方形も右上がり、右下がりの2種類に場合分けをしてあげれば良さそうです。

書き上げたので、ドキドキしながら実行します。重なっているみたいですが、あともうちょっとな感じ。あ、辺上に別の頂点があったらダメなのを忘れていました。ビジュアライザが見やすくて、デバッグをするのに便利です。

書き直したコードで実行したところ(seed0)

やった!長方形ができています。とりあえず、ここで100ケース試そうかな。

バグが消えた(seed0)

コードの長さは320行で、ものすごくすっきりしました。同様に書けば、斜めも短いコードで実装できる感触があります。早く書き直せばよかったとも思うけど、何度も書いていたから、書き直しがこんなにすんなりといったのだと思います。

100ケースの結果もバグなく出ました。

ランダム長方形の100ケース結果

続いて斜めの長方形を実装します。と思いましたが、またバグりました。まずは1辺が√2の正方形のみを追加します。それでもseed0のスコアは良くなっていたので、100テストケースをまわします。

斜めは1辺が√2のみを追加(seed0スコア241789)

バグはなかったものの、あまり得点は、ぱっとしません。やはり、斜めの正方形の実装をきちんとしないとダメそうです。

長方形と1辺が√2の斜め正方形を追加

お風呂に入って考えていたのですが、正方形の斜め45度なら実装が楽そうです。まずはそれから始めたいと思います。

・同じ座標が縦方向か横方向にある(まずは縦方向にあるとする)

・差は偶数

・座標は(①+②)/2

正方形の斜め45度なら座標がわかりやすそう

判定はバグっているのですが、形は良さそうです。

 

斜め45度の正方形を追加

判定を追加しました。

seed0、スコア243586

100テストケースを実行して結果を見ます。斜めの正方形で、バグっていました。

斜め正方形の判定がバグっています(seed1)
11.長い時間をかけてデバッグを続ける(コンテスト5日目)

9月21日、水曜日の朝7時です。コンテスト5日目になりました。

トップはRafbillさんが独走を続けています。現在の得点は68,546,806です。提出者は529人になりました。私の順位は319位で出遅れ気味。いつもの1週間コンテストでもこんな感じの遅さなので、今回も相変わらずの自分です。全部ランダムで長方形を描けるようになったら、焼きなましたいと思っているので、そこまではがんばりたい!

ということで、昨日の続き、バグっていた判定を出力デバッグします。どうも、x座標が1ずれているっぽいので、添え字を修正します。バグが消えると「あっ!」と驚いた声が出るようになってしまいました。何か、添え字ガチャをしているのがバレそう。もちろん、適当で無理なときはきちんと考えます。

バグは消えたようです。

長方形と斜めの正方形をランダムで追加(seed0、スコア248536)

しかし、100テストケースを実行した結果は変わりません。次は斜めの長方形を実装したいと思います。

バグは消えたけどスコアは変わらず

斜めの長方形を実装します。形は何となく合ってきたけど、まだ変な形の長方形があるのと、判定がバグっています。

斜めの長方形を追加(バグっています)

辺を共有しているのと、内角が90度でない平行四辺形が混ざっているのがNG

デバッグはグリッドを出力して確認していましたが、これを使用している1点ずつの座標出力に切り替えて、思った通りに使用した線分の方向が記録できているかどうかを調べていきました。

そしてついに、長かったデバッグをやっと終えました。時刻は9月22日木曜日の夜8時半です。コンテスト6日目の夜でした。通常だと1週間コンテストなので、やっとこれからというときに終わっていました。今回はまだあと1週間あるので、がんばりたいと思います。

100テストケースを実行した結果です。やっとこれまでのスコアを更新することができました。提出したときの予測値は19894363点です。

バグをなくすまで長かった

ランダムにやっていましたが、全探索に変えたいと思います。再び100テストケースを実行して結果を見ます。しかし、スコアは微増でした。

全探索を時間いっぱい繰り返す

seed0は263349になりました。

seed0、スコア263349

全探索のしかたを全部の長方形の組み合わせをしてから全部の斜めの長方形の組み合わせを試すことを時間いっぱい繰り返していましたが、長方形と斜めの長方形を交互にするように変えてみます。

あ!

ここで致命的なコードの欠陥に気がつきます。新しい点を追加するのを忘れていました!どうりでスコアが上がらないはずです。

100テストケースを実行して結果を見ると、スコアが上がりました。

ここまでつらかった、本当に。

全探索を時間いっぱいする

うーん、やっぱりランダムの方が良いのかな。

もう一度100個のテストケースを実行します。その間にseed0を見ました。ちょっと見ただけで、まだ長方形がたくさん作れます(赤線で長方形を足してみました)。これは条件がまちがっていそう。見直すことにします。

seed0でまだ長方形がたくさん作れそうです

ランダムの結果も出ましたが微増でした。コードを見直します。

ランダムを時間いっぱい

条件をデバッグしました。先ほど目で見てすぐに見つかった長方形ができそうな場所はなくなりました。

seed0、スコア298903

また100テストケースを実行します。だんだん良くなってきているのがわかっていているので、ドキドキしながら結果を待ちます。数字を見て安心します。よかった。

100テストケースの結果

久しぶりに提出をしたいと思います。

ただいまジャッジ中

ジャッジ中は本当にドキドキします。途中で黄色いWAに変わったりするので、そんなときはがっかりしてしまいます。無事にACするのを見届けるまで気が抜けません。緊張しながら結果が出るのを待ちます。

結果は、322位/577人中、得点は24,480,199でした。

322位/577人中、スコアは24,480,199でした。

さあ、スコア計算を書いて、ここから改善を始めたいと思います。やっとスタートラインに立ててほっとしました。

12.やっとスタートラインに立てた(コンテスト7日目)

最初は焼きなましをしたいと思っていたけど、お風呂から出てきた今は、貪欲でビームサーチかchokudaiサーチをしたい気持ちでいます。あとは、追加した点をソートして全探索をしたいとか(これは今からやってみるつもり)。やっぱり編み物をするときみたいな、追加した点を使って次の長方形を作るみたいなのが強そうだなあと想像したりしています。

<明日やることリスト>

  • スコア計算の実装
  • 貪欲とビームサーチ(chokudaiサーチ)

それが終わったら評価関数を考えたり、キックして山登りとか。点を多く打ちたいというのと、外側に点を打ちたいというのがあって、最初は外側に点を打つ問題なのかと思っていたのですが、seed0の共有された画像を見ると、まずは点を多く打つ方向が良さそうな気がしています。

あと今思っているのは、5秒もかからずにわりとすぐに終わってしまうのかな、ということ。

さて、全探索にして、1周するごとに座標のペアをソートするようにしたら、seed0のスコアが357057になりました。

seed0、357057

そんなことで簡単にスコアが良くなるのかなと疑問に思いつつ、100個テストケースを実行して、結果を見ます。

上がっています!得点は25,511,806点でした。

得点は25,511,806点でした。

翌日になりました。2022年9月23日金曜日。今日は祝日です。今日からの3連休はゆっくりと時間をかけて取り組む時間が取れそうなので、楽しみにしています。平日も出勤前と帰宅後にコンテストに取り組んでいたものの、時間的には満足のいく時間が取れずに残念に思っていました。

さて、これまでは、斜めの長方形と垂直と水平な線で作られた長方形を交互に作っていました。今日は貪欲を書きたいと思います。

  • ある1点を選んだときに作ることのできる全ての長方形の中から、いちばん得点が高くなる長方形を選択していく。

ビジュアライザでseed0の共有がされているので、自分の現在の立ち位置は、わりと明確に把握できている気がします。この貪欲を書いて提出すれば、得点は3000万点近くになり、ビームサーチにすれば、3300万点くらいになるのではないかと思っています。さらに評価関数をうまく書けば、4000万点近くに届くのではと予測しています。そこまでがんばりたいものです。

今の自分の1ケースあたりのスコア平均は50万くらいですが、現在もトップ独走中のRafbillさんの得点が72,753,846点なので、1ケースあたり145万スコアくらい出ていることになります。すごい!まだまだ改善の余地はありそうです。

13.貪欲の実装

まず、ある点を選んだときに別の1点を選んで長方形ができるかを判定するメンバ関数を書きました。これで合法手を書きだすことができます。

判定だけすれば良いのか、追加する頂点をリストにしておくと良いのかは思案中。評価関数(今はスコアと同じ)を計算するときには、追加する点によって評価関数の値が変動するので、やはり持っておくと良さそうだなと思います。

あ、貪欲なら、追加する一点のスコアだけ持っていて判定すれば良さそう。

あと盤面はZobrist hashして重複を除去すれば高速にできそう。おお、夢が膨らみます。

がんばろ。

(時間経過)

夜です。思ったほど自由時間がありませんでした。

  • 長方形ができるかどうかを調べて合法手に入れて、合法手の中で一番スコアを高いものを選択して、一手進める。

やっとこれを書いて実装したところです。ところが、スコアが下がっています。おまけに目で見てもまだ長方形が作れます(赤枠)。はぁ、またデバッグの時間です。

seed0、スコア286705

あ、今回は早く見つかりました。よかった。大きなバグは消えたので、やっと100テストケースを実行しようという気持ちになりました。これで、昨日と同じくらいのスコアが出ていれば一回提出しようと思います。

思ったほどスコアは良くないので、1手貪欲をビームサーチに変えたいと思っているのですが、それ以外にもX座標の小さい点から見始めるとか、別の要因があるかもしれません。ランダムにして、様子を見たいと思います。

貪欲(合法手の中でスコアが一番良いものを選択し続ける)

ランダムにした結果です。seed0を見ると、やはりまだ作れそうな長方形を作ってません。ちょっと調べたいと思います。

seed0、スコア350438

seed0、まだ作れる長方形が見つかります

ランダム貪欲100テストケースの結果

ついでに100テストケースのスコアグラフも載せておきます。

100テストケースのスコア(ランダム貪欲5秒)

あ、(バグを)見つけたかも。

バグ消えた?(seed0、スコア332945)

100個のテストケースを実行します。

スコアが上がった!

100テストケースの結果(これが貪欲の本来のスコアっぽい)

提出します。まだバグがありそう。ちなみに先ほど見つけたバグはx座標とy座標を間違えて使用済みの配列に値を入力していました。しかも出力デバッグをした際には正しい座標を出していたため、気づくのが遅れたのでした。

提出結果は得点が27,400,917点、順位は348位(621人中)になりました。

得点は27,400,917点、順位は348位(621人中)

朝です。ビームサーチ用にコードを書きかえています。

問題点が、今、2点を選ぶようにしているのですが、2点目は合法手で全て選ぶのですが、1点目はx座標の小さい順で選んでいました。

1点目をランダムで選ぶようにしたら、スコアが下がってしまいました。

何だか目で見ただけでも作れる長方形がちらほらとわかります。

これを書きながら思ったのですが、1点目、2点目の全ての組を合法手としてピックアップすればいいのかな?5秒でできるのでしょうか。今、各点からの合法手は0から4くらいまで、合法手が0を省くとどれくらいになるのかな。

ビームサーチのために書き直した結果(seed0、スコア3266609)

あ、いけるかも。

2点の全ての組み合わせを合法手とした(seed0、スコア352424)

さりげなくスコアを更新してる!ただの貪欲でスコアが更新するならビームサーチも期待できそう。100ケースを試して結果を見ます。

14.いちばん熱い日(コンテスト8日目)

朝晩は涼しい風が吹くようになりましたが、まだまだ日中は暑い日が続きますね!という話ではもちろんありません。

私は長期コンテストに参加するようになってから、探索アルゴリズム、たとえばビームサーチやchokudaiサーチ、MCTSなどに憧れるようになりました。アルゴリズムを勉強していたときに動的計画法(DP、Dynamic Programming)を理解するのが難しくて、随分と苦労しました(今も継続中)。それでも、これは貪欲じゃないよね、DPじゃないと解けないよね、と、解けるかどうかは別として、問題文を読んで思うようになりました。長期コンテストでも、同じように思うようになりました。一手先の貪欲を選び続けるより、本当はもっと良い手があるよね、と。だから、私は長期コンテストでビームサーチを使えるようになりたいとずっと思っていました。今回、ビームサーチで良い結果が出るといいなと思います。

閑話休題、コンテストに戻ります。

先ほどの結果が出ました。結果は下がっているのですが、多分Mに依存します。時間が足りなくて、これまでは時間内に全て書き出せたものができなくなっているのではないかと予想しています。

結果が出ました。やはり、相関は高そう。

M(頂点数)とスコアの関係

解決策としては、合法手の数がある数以上になったら打ち切るか、今ある点のうち、合法手が0だとわかるから飛ばしてよいものを先にとばしたらどうかと考えました。まずは後者を選択してみます。

絶対に合法手が0であるものとしては、その点の周り8点が全て点で埋まっているものは上げられそうです。また自分から8本の辺が出ているものも使うことができないとわかります。それを事前にチェックしてみると、どうなるでしょうか。試してみます。

前(seed5、321572)

後(seed5、319304)

良くなるどころか、さらに下がっちゃった…。

結果

はい、結果もこの通り。

次は合法手の数を制限してみます。とりあえず、合法手の選択肢が10以上になったら打ち切ることにします。

お、回復傾向。でも、seed5は1点貪欲だと551835までスコアが出ているので、まだ考える余地はありそう。次は合法手5個で試してみようかな。あ、そうだ、ソートを入れてもいいかも。いまは追加した点のスコアで評価しているので、早く評価関数に取り組むところまで進みたいな~。

合法手を10個に制限(seed5、440066)

結果

ふむ。合法手5で、ソートを入れてみよう。

合法手5でソート(seed5、406960)

ん?なんか予想外のビジュアライザ。全然進まないってことなのか、いっぱい作れているってことなのか。ちょっと判断に迷う。これ、考えないと。点をつけ足さないときの元のスコアを持っていないと正しく評価できないかもしれない。ああ、そうか、評価に使っている、追加した点のスコアを出力しようかな。

単純に考えれば、付け加えた点が減っているので、スコアも減っている。ソートはしない方がいいのかな。やっぱり改善は1個ずつが良さそう。

結果です。上がっています。そして、これまで見たことのなかった数値が最大値にありました。

結果(合法手を5に制限、ソートあり)

seed98、スコア744418

合法手を5に制限した結果です。ソートありの方がスコアが良いようです。

合法手5の結果

そういえば、昨日寝る前にアサートを入れたらおかしいところがあったのを思い出しました(今頃?)。良いスコアが出ていたから、思わず消しちゃっていました。ヤバい、見ないと。多分座標の添え字がおかしいところがあるはずです(←え?)。

確認しましたが、大丈夫でした。よかった。とはいうものの、記憶違いかどうかもわからず。ちょっとお昼寝した方がよいのかな。

休憩して、ビームサーチに切り替えてみましたが、出力が0になってしまいます。途中までは評価も座標も入っているのになぜ?というのがわからないので、いったんコードを戻すことにしました。

先ほど合法手5に制限し、ソートをかけていたseed5をもう一度見ようとしたところ、結果が変わっていました。合法手を得るところで、制限時間を超えている感じだったので、実際はTLEすると思います。

合法手5とソート、TLE解法(seed5、スコア529412)

しかしスコアが伸びて全面が埋まっています。時間をかけてスコアがよくなるときは高速化が効くと聞いたので、高速化を考えます。一つは評価関数を毎回追加した点を全て足していたのを最後の1個だけにしようと思います。またソートはO(N)の計算量がかかるので、1個増えたものを二分探索でインサートするようにしたいと思います。

それから、合法手を4個にしてソートにすると全面になりましたがそこまでスコアが上がらなかったので(seed5で44万くらい)、合法手はやはり多くできれば得点が上がりそうです。

あとは、X座標の小さい順に見ていくのではなく、中心からの距離が近い順に見ていくとか、マンハッタン距離が近い座標から見るようにすると、合法手を5個集めるのが早くなりそうな気がしました。

やってみましたが、なんかイマイチでした(結果省略)。

あ、アサートのおかしかったところも見つかりました。よかった。記憶がおかしくなったのかと思った。でも何で?(これはちょっと後回し←解決済:追記9/24)

点の座標と照らし合わせてusedのデバッグしていたところ

もう一つ気がつきました。

  • 今ある点のうち、合法手が0だとわかるから飛ばす。

これがバグっていたので、やり直しました。リストから外していくということをしたら、スコアが上がりました。でも合法手の選択でTLEしてそう。

合法手を5に制限、ソートあり、使用不可な点をリストから外す

買い物をしている間に考えていたのですが、評価をする際に、①スコアが良いものを選択するとか、②距離が近いものを選択するといったことを考えていましたが、これが全く的外れなのではないかと思うようになりました。

本当は、他の選択肢がこれしかない、もしくは他の選択肢が少ない点を優先してつなぐのが良いのではないかと思うようになりました。もしくは、新しい点を追加することによって、新たに選択肢が多く増えるもの。この辺は思案中。

したがって、新たな配列を追加したいと思います。

  • 配列[組み合わせることができる点の数を追加。

あと、計算量削減としては、一回2点の組み合せを調べたらもう一度調べる必要はないので、次は新しい組み合わせを追加するだけで良さそうです。

そうだ、使った組み合わせは減らさないと…。

・使えない点は削除していった方がよい

・ソートはスコアが変動しなくなってからでよさそう

・1回目のソートはMが大きいときに効く

seed0、スコア384101

使った組み合わせを減らせてない。組みの相手がどの点かを記録しておかないとダメ。あ、そうだ、使った辺が多い順にしてみよう。ABCに参加して頭を切り替えてこよう。

13.コンテスト9日目(2022年9月25日)

コンテスト9日目の朝です。特に良くなった気はしていなかったのですが、昨日の夜寝る前に1回提出をしておきました。するとスコアが上がって、28,259,522点になりました。順位は655人中372位です。

372位(655人中)得点28,259,552点

昨日は熱くならないまま(結果が出ないまま)終わってしまったので、偽りの章タイトルになってしまいました。スコアがぐーんと上がるのでは?と読み進めてくれた方がいたら、ごめんなさい。昨晩参加したトヨタ自動車プロコン2022(ABC270)も2完でレートが下がりました。しょんぼり。

さて、今朝はお布団の中で、ビジュアライザのマニュアルモードを試していたのですが、5個の点が並ぶと良い形になるなあと思いました。

ビジュアライザのマニュアルモードで試したこと
  • スタート位置は上のような5個のかたまりがあればそこからスタートにする
  • 前に追加した点との距離が近い順に並び替えをする
  • 点を追加したときに、作成できる長方形の数が増えていたら、評価関数の値を増やす

追加する点を前に追加した点から近い方に評価関数を足したら、seed0のスコアが良くなりました。seed0、スコア432421。

seed0、スコア432421

一方、悪くなったのが、全然終わっていない感じのseed5(スコア338669)

seed5、スコア338669

あ、合法手の個数を制限するのを忘れていました。

seed5、スコア404087

追加できる点のx座標が大きい順に並び替えることにしました。ちょっとまだ途中の更新はできていないのですが、スコアが少しよくなりました。

追加できる点のX座標が大きい順に並び替えた結果

だんだん何を追加したかわからなくなってきたので、一度提出することにします。前回の提出を少しだけ更新していました。得点は28,341,753、順位は375位でした。

提出結果 得点28,341,753点 今の順位は375位(659人中)

テストケースごとのスコア(100テストケース)

Mが大きくなるとスコアが下がるのは、seed5のように全部見終わっていないからです。

(時間経過)

ある使っていない点から作れる長方形は、最大4個までだなと思います。

  • 空いた点から長方形を作る。

こちらの方が良いのではないかと思います。これまでは、すでにある頂点を2つ選んで長方形を作っていました。私自身、どのようなデータ構造を使えば良いのかが、今回最大の苦心している点です。

  • 水平、垂直、右上がり斜線、右下がり斜線のすでにある頂点の位置を記録した4つの配列を作り、各点を配置する。

これをすれば、自分が作れる可能性のある長方形のリストがわりと簡単に作れるのではないかと思いました。使うときには二分探索をする感じ。点を追加した後にBFSでいちばん近い使っていない点に移動するみたいなことを時間いっぱい繰り返すのはどうでしょうか。

図にします。

描いてみたら面倒だったので、やめます。

書いたメモ(供養)

今ある点で、どの点を追加できるかをリストにしてぶら下げてみる方が楽そうなので、そちらを選択したいと思います。あと、見る順番がイマイチすぎるので、追加した頂点からBFSをすることにしたいと思います。

  • いちばん近い、使っていない点を使って長方形ができる点に移動する。

これ、寝起きのマニュアルモードで追加する点に意識を置いていたけど、自分の場合、長方形を作れる点を意識した方が良さそう。

どの2点を選べば新しい点を追加できるか(赤が新しい点)

色付けしてみました。赤が新しく追加した点、黄色が新しく追加するために必要な2点です(自分の場合、対角線上の2点を選択すると長方形を描けるコードを実装済)。わかったことです。

  • 新しく追加した点で長方形を作成している。

「新しく追加した点からいちばん近い、まだ使っていない点」とは「新しく追加した点」自体なんだなと思います。ということで、探索の順番を変えたいと思います。

ところで、余談なんですけど、「これ、やっていて楽しいんですか?」と、もし聞かれたとしたら、「めちゃめちゃ楽しい」としか返答の仕様がありません。私にとっては熱中できる遊びなんですね。おいしい食事もゲームも、温泉や麻雀も、もちろん好きなのですが、それでも競プロをしている時間が、今いちばん楽しいのです。

(時間経過)

スコア計算のメンバ関数を実装しました。今さら?と思うことでしょう。これまではコンパイル済みの提供されたツールでスコアを調べていました。実装したものの、まだスコアが微妙にずれています。評価関数では、新しく追加した点から長方形を作るときの評価が上がるようにしました。

次はBFS。その前に100テストケースを実行して、コードを保存しようと思います。

結果はパッとしませんが。

評価を修正。スコア計算追加。

新しく追加した点との距離が近い方に評価を足す

最高スコアを出していたseed56。これを見ると、やっぱり外に点を打てると良いのかな?Mが小さいときの方が高スコアを出しやすい?

seed56、スコア766206

記録代わりに提出しておきます。ちなみに今のコードは1420行(コメントや使わないメンバ関数を含む)。得点は27339866点でした。

得点27339866点

何だかBFSは効率が悪いなあと思って、1点ソートに戻って、など迷走してきたので、マニュアルモードを試します。N=10、M=20です。実際はこんなに小さなテストケースはありませんが、ビジュアライザはこういった使い方もできて便利です。中を埋めて外側を増やすみたいなのは、わりと良い案かもしれません。

N=10、M=20のサンプル スコア902778

というわけで、やってみたい案です。

  • 1辺が1の正方形と、1辺が√2の菱形正方形を使用できる点から調べて先に埋める。行き詰ったら、すでに作っている2点から調べる方法で長方形を追加する。
  • 偶奇を決めておいて、それに合ったものしか置かないようにする。

下の最後に追加した菱形は置いてはダメにしたい。

偶奇をそろえたい

N=10、M=20、スコア1086111

そうかー、現在40位以内くらいの50Mを超える得点をとるって、こんな感じなのかなあと想像しました。もう一度実装を整理します。

  • 1辺の長さが1の正方形、1辺の長さが√2の菱形正方形をできるだけ作る。
  • 小さな正方形が作れなくなったら長方形を足す。

上の2つを繰り返してみたいと思います。また、正方形の判定は、新しく追加する頂点を基準にして調べたいと思います。

他に思いついたこと。

  • 追加した長方形を消したりする。方法としては、追加した頂点を使った長方形をUnionFindで管理して、同じグループのものを一気に消す。

やりたいことは決まったものの、バグらせ続けています。あとちょっと。正方形は消したから、あとは√2の菱形正方形。

14.コンテスト10日目(2022年9月26日)

月曜日の朝です。今日からまた仕事なので、取り組める時間が少なくなってしまいます。おまけに腱鞘炎(!?)になりそうな右手の痛さ。

さあ、デバッグからです。

seed0、スコア0

水色の辺が重複しているバグ(左:1手前の図)

判定が間違っていたので、修正。100テストケースをまわして確認します。

今は長方形を使いすぎている(連続で入れている)ので、1個長方形を足したら、やめて小さな正方形に戻るように修正したいと思います。

(時間経過)

夜です。バグ、消えました。100ケース回した結果、点数は下がっていますが、一回提出してきます。

100ケースの結果

提出した得点24769120

今長方形を1個ではなく、たくさん追加しているので、1個にします。

エラーは出なくなりましたが、seed0でまだ長方形がたくさん追加できるのが見てわかります。判定か使用した頂点や辺の管理が間違っているかのどちらかだと思うので、見直したいと思います。

seed0、スコア329257

バグらせまくり。

重複は消えたけど、うーん、まだ判定間違っていそう。もうちょっと。

seed0、381265

判定は間違っているけど、やり方の方向性は悪くなさそう。

100テストケースの結果

また提出しておきます。

ハイスコアを更新していました。得点は29,054,023点、順位は688人中391位でした。

得点は29,054,023点、順位は391位(688人中)でした。
15.コンテスト11日目(2022年9月27日)

もうデバッグする箇所も見つからないので、印刷して、通勤時にでも見ようと思ったら、28ページにもなりました。寝る前に見ていたら、確認していない箇所がありました。よかった。確認する箇所が見つかって。

というわけで、早朝から起きています。

直った、はず。seed0のスコアが509015になりました。

seed0、509015

100テストケースを実行して、結果を確認します。どきどきする…。

最高スコアを見つけました。seed44で955634点。

seed44、スコア955634

上がりました。はっきりと。

涙が出ました。

デバッグ、本当につらかった...。

提出します。

100テストケースの結果

100テストケースのスコア

結果は、得点が31,959,841点、順位は332位になりました。やっと30Mを超えました。

提出した結果、得点は31,959,841、順位は332位(689人中)でした

やっとスタートラインに立ったのを感じました。コンテスト11日目の朝でした。

今回はアサートの大事さを感じました、本当に。自分の想定していない値だったときにちゃんとエラー出力をするの、本当に大切だなと痛感しました。

さあ、やっと評価を考えるところに来ました。

今は小さな正方形たちが作れなくなったときに、初期座標で追加できる点のx座標が小さい順に足していっていました。でも本当は、ここに点があったらいいなという場所があるはずで、そこに点が打てるような長方形を足してあげるのが良いはずです。また、追加された点や、使ってしまった辺や点で、作ることのできる長方形が変わっているので、その情報も更新してあげたいと思います。

また、M(初期の点の数)が小さい方が得点が低くなっているので、そこも改善したいと思います。

あと、偶奇を揃えるとか。

seed0アニメーション、スコア509015
  • 追加できる点を全探索して①最後に追加した点からいちばん近い点を追加する長方形を選択する②いちばん辺の長さが小さい長方形を選択する。
  • 最初に追加した長方形の左上を偶奇のポジションとして記録し、最初はそれに合った正方形や菱形だけを追加していく。

何をしようかな。ここからはビジュアライザとにらめっこです。

①を書いて、もう一度朝、出勤前に1回提出しました。得点は32,635,950点、319位でした。

得点は32,635,950点、319位でした

夜です。帰宅後にしたことです。

  • 朝の微修正。直前に追加した2点の距離ではなく、今追加しようとしている点と直前に追加した距離が小さいものを高く評価するに修正。→seed0のスコアは569911になったものの、100テストケースの結果は微減。
  • 評価を「追加した点から近い」+「長方形のサイズが小さい」ものが良いとする。→100テストケースの結果は減少。
  • 追加できる点の個数が多いことを高く評価する。→100テストケースの結果は微減。時間切れで全部見ることのできないものがあり得点が低い(seed53)。

赤色が距離が近いことを評価、黄色が追加できる点の数が多いことを評価

距離が近い、追加できる点の数が多いことを評価してみた結果

結果が出ないことで、いろいろと迷走しましたが、今見直してみると、距離が近いことを評価する方が安定した結果が得られるようだと思ったので、こちらを進めてみたいと思います。

距離が近いこと

コードを保存していなくて、戻れませんでしたが、何とか近い形に戻しました。

今考えていること。

  • Mが少ないときのスコアの底上げ(青枠部分)

Mが少ないときは「1点の追加」の重みが大きいので、スコアにすぐに影響してしまいます。逆にいえば、良い案が浮かべば、一気に高スコアを出せるのではないかとも思いました。この青枠の低スコア帯を60万以上に底上げできたら、平均を今の64万から70万くらいに上げることができるのではないかとおもいます。そうすれば、提出したときに35Mくらいの得点を出すことが予想できます。

Mが小さいときのスコアの底上げが必要

時間が余っているので、かたまりがくっつくときに、小さなかたまりを全て消し去るみたいなことをしたらどうかなと思っています。9日目に考えていたような、UnionFindで管理して。今の状態だと、かたまりがくっつくときに、溝ができてしまうので。

小さいグループ(赤枠部分)を全部消してみるとどうかな
  • 一番大きいかたまりを残して、小さなかたまりを全部消す。

これを実装してみたいと思います。

16.コンテスト12日目(2022年9月28日)

眠いです。今考えることリスト。Mが150以下の場合のみ。

  • 多点スタートでいちばん良い解を出力する。
  • 小さいサイズから作る(作れない場合は近くに点を打てるものを優先していたので、長方形の小さいサイズを作るようにする。一度やったような気もするけどやはりダメなのかな?)
  • UnionFindで新しく追加した点を使った長方形どうしをマージする。最後の長方形を追加したら、いちばん大きなグループを残して、それ以外を消す。これを時間いっぱい繰り返し、いちばんよかった解を出力する。
  • 追加する長方形はランダムで選び、いちばんよかった解を出力する。

(時間経過)

3時間ほど迷走していました。お風呂に入って、思考を整理してきました。何をやっていたのかというと、評価関数を変えて、結果を調べていました。

評価関数の優先事項

  1. スコアが高い
  2. K(追加する頂点数が多い)
  3. 前回追加した点からの位置が近い
  4. 長方形の面積が小さい

逆転できないように重みづけをします。

100テストケースを実行する時間が長く感じて、記録したり、最後まで行わずに次の改善(改悪?)を進めてしまい、元に戻れない状態がもどかしくて時間を費やしましたが、UnionFindの方に進みたいと思います。

現状です。

100テストケースの結果(ここから再スタート)

100テストケースのスコアとM(初期頂点数)の分布

これ以上迷走しないように、1回提出をしておきます。得点は32,367,568でした。

得点は32,367,568でした。

さて、UnionFindですが、

  1. 点数が上がらなくなったら(追加する点がゼロになったら)
  2. いちばん大きいグループを調べて
  3. そのグループだけを新しい出力用配列に入れる
  4. また点を追加する
  5. 追加する点がなくなったら、スコアを比べ、高い方を最終提出用配列に入れる

としたいと思います。

17.コンテスト13日目(2022年9月29日)

朝です。昨夜はUnionFindを使ってグループ分けしていましたが、思ったような分け方ができずに悪戦苦闘していました。

ちょっと仕切り直し。

  • 評価関数に乱数を入れて、時間いっぱい最初からやり直す

これに変えたいと思います。

(時間経過)

帰宅!得点を更新するぞ!

スコア計算を直しました。NやMがdoubleで計算されていなかったのが原因でした。1回目はそのまま、2回目以降は評価関数に乱数を足します。最終的にスコアがいちばんよかったものを出力するようにしました。評価関数は追加した点が前回と近いものを高くするようにしました。100テストケースを実行している5秒×50=250秒(約8分)の時間が長く感じます。

次は、スタート位置が(0,0)だったのを変えていきたいと思います。上下左右の四隅からと、うず巻き(外側からと内側から)の6通りを試したいと思います。

開始位置を変えてみた(評価関数に乱択を入れる山登り)

やってみました。結果はぱっとせず。うーん、バグっているのか、考えている方向性が悪いのかちょっとわかりません。

開始位置を変えてみた(評価関数に乱択を入れる山登り)

悩んだときはビジュアライザのマニュアルモードをポチポチとクリックして、考えます。正方形と菱形(斜めの正方形もしくは長方形のこと)はうまく並べると、連続して増やすことができます。4個目の点を打ってしまうと終了なので、4個目を打たないゲームなのかな?4個目を打つときは、辺が4本出る形が望ましい。

赤い点を打つときは、青の点が打てるときに限るとすると良い?考察がまとまらないうちに日付が変わってしまいました。日中は仕事なので、そろそろ寝なければいけません。

<疑問点>

  • 山登りをして、なぜスコアが良くならないのか
  • 評価関数は何が良いのか
  • Mが少ないときに得点を高くするにはどうすれば良いのか
  • 連続で点を追加するにはどんな条件が必要なのか
  • スタート位置はスコアに影響しないのか
  • クラスタ(連続で点を打てている塊)を連結するときの条件は?

書き出してみると、わからないことだらけだなと思います。寝て起きたら、考えがまとまっていると良いのですが。土曜日の19時が終了時刻です。コンテスト終了まであと約2日になりました。時刻は0時半。おやすみなさい。

18.コンテスト14日目(2022年9月30日)

青点:提出した最高スコア 赤点:2昨夜のスコア

100テストケースの結果

夜です。帰宅したので、やっと思いっきりできる~!と思いつつ、眠くて死にそう。がんばるだけがんばったら、寝ます。

日中考えていたことは、2つのクラスタをくっつける方法です。間が1列なら、どこか1点を打てれば連続して菱形を作れそうだと思いますが、その1点が斜線だとダメだったりします。形が限定されるなあと思ったら、やはり、1つづつ作っていくのが良さそうだと思いました。なので今からやることです。

  • 初期のスタート点を列挙しておく。
  • 1つずつ8方向BFSで点を追加していく。
  • BFSの条件は追加の点を打つことができること。点を打てるかどうかを調べて、点を打つことができる場合のみ、その点をキューにプッシュする。
  • 初期のスタート地点を全て試し、いちばんスコアの良かったものを出力する。

実装しました。提出した結果、32,285,465点でした。最高スコアの更新はできませんでした。提出の前にテストケースを試しているので、予想通りの結果ですが。

提出結果(32285465点)

100テストケースの結果

100テストケースのスコア(青が提出の最高、赤がBFSをした現在)

久しぶりに最高スコアを更新していました。seed98で965587のスコアが出ていました。

seed98(スコア965587)

seed0はこんな感じ。とても形が悪くて、真ん中に点を打てず、無駄にしています。

seed0、スコア533317

seed0は下の図のように2つのクラスタがくっつく場面が出るのですが、この後、真ん中を下からふさいでしまうので、有効活用できずに無駄にしてしまうのです。この有効活用について、日中考えていたのですが、結論としては、くっつくときに、片方を全て消し去ってしまえば良いのではないかと思いました。

2つのクラスタがくっつくときに、片方を消したい

これはUnionFindで管理して、実装したいと思います。

19.コンテスト最終日(2022年10月1日)

今日の19時がタイムリミット。今日やりたいことです。

  • クラスタがくっつくときに片方を消す
  • 1000ケース試す

前回と近い点を優先

使用できる点をX値でソート

現状悩んでいる点です。

  • Nが大きいときにMが小さいときのスコアが悪い(大きな盤面で使える点が少ないときのスコアが悪いということ)

逆にいえば、盤面(N)が広いときでも初期の点の数(M)が多ければ順番につないでいくと70万くらいのスコアが出るようです。50ケースで35Mは70万平均スコアなので、そこをまずは目指したいですね。

得点32517633

1回提出してスコアを確認。得点は32517633でした。ちなみに、一番良いと思っていたスコア(32.6M)のコードを再提出したら、同じスコアが出なかった(32M未満)ので、今が一番良いスコアが出ています。さあ、残り時間、がんばります。コードを実装する間に1000テストケースを実行したいと思います。

なんか440ケースで止まってしまっていました。

平均は637424.5、maxは965587、minは397942でした。一旦このままで。

440テストケースのスコア

そういえば、評価関数をちょこちょこといじっていたら、こんな感じにseed0が出力されて「おおっ」とうれしく思ったのですが、同じコードでもう1度実行したら別の出力が出て、2度と再現できませんでした。うーん、なぜ?

幻のseed0、スコア618988

うーん、途中まで実装したものの挫折しました。

  • 点のグループサイズが1のとき連結する・・・問題ない
  • 点のグループが前回と同じとき連結する・・・問題ない
  • それ以外は消す・・・連結しようとした点は?もう一度やり直す?

判定が初期点ベースのBFS(小さい正方形と菱形正方形)、空きマス(小さい正方形と菱形正方形)、今ある2点の全探索(作る長方形と45°回転した長方形)を組み合わせているので、いろいろと複雑すぎて、頭がついていきません。

seed0ではなく、普通のNが大きくてMが小さい盤面の考察に切り替えたいと思います。現在の時刻は午後1時。残りは6時間です。

スコアが悪かったものを並べてみました。

スコアのワースト4

seed28をマニュアルモードをやってみてわかりました。

seed28をマニュアルモードでやったところ

自分の頭が何も考えていないなあということが。もう一度チャレンジ。

2回目(331990)

自分の出力スコアは514052なので、まだまだ負けています。やっていてわかったのは、この長方形がじゃまだから、これがなかったら良いのではないかと思ったこと。

  • 長方形を1個消す。

残りの時間でこれができるでしょうか。実装するときに問題になりそうなのは、追加した点が後に使われていないかということ。書いていて、ああ、これ前もやろうとしたな、と思います。

今のコードの流れ。

  1. 初期セットからの1辺が1の正方形、もしくは菱形正方形を置いていくBFS。
  2. 全ての空きマス(使用していない点)からの1辺が1の正方形、もしくは菱形正方形を全てに置く。
  3.  1,2ができなくなったら、大きな長方形を置く。
  4.  1から3を繰り返し、置ける長方形がなくなったら、盤面をリセットし、1から3を時間いっぱい繰り返す。
  5. いちばんよかった答えを出力する。

これ、評価関数が同じなら、同じ結果になるので、評価関数に乱数を加えています。でも、その評価関数がなぁ…(←イマイチ)。

というわけで、4で盤面をリセットしていたかわりに、長方形を1個削除することができれば、この方が山登りになって良さそうです。

3で追加していた長方形に目印をつけておいて、この長方形をどれか削除することを行いたいと思います。

<長方形を削除するときに行うこと>

  • 答えからその長方形を指定した1行を削除する。
  • 使用した辺のフラグを未使用に変更する。
  • 追加した点のフラグを未使用に変更する。
  • 追加した点のリストから点を削除する。

これくらいかな。

(時間経過)

やはり盤面山登りのスコア更新がおかしいのでチェックしていたら、スコア計算を実装する前の名残で、「追加した点の数が多いとき」という判定をしていたのを見つけたので修正しました。何やってるんだろう?今頃。

そして、提出しました。

得点は32,830,787点、順位は366位(770人中)

4日ぶりのHight更新です。得点は32,830,787点、順位は366位でした。

すごいな、これ。公開されている情報では、ほんの少し点数が上がっただけ。この4日間私がやっていたことは、ブログを書かなければ誰にもわからないまま。

だから、私はTwitterで点数を公開する人に、いいねを押さずにはいられないのかもしれません。見えないところでやっている積み重ねを想像して。

知らないうちに涙が頬を伝います。

さあ、もうひとがんばりだ!

100テストケースの結果

100テストケースの結果

seed0、スコア523577
20.終わりに

もうすぐコンテストが終わります。そうしたら、このブログを公開します。AtCoderの解説にもリンクを貼ります。多くの人に読んでもらいたいなと思います。楽しそうだなと思ってもらえるでしょうか。わかりません。もっと良い得点を出したかったと思うけど、自分の提出はここで終わりました。いくつかのしたいと思ったけどできなかったことを残したまま。

人生の何に価値を見出していますか。偶然入り込んだ競技プログラミングというこの世界。時間を忘れて熱中できるものに出合えたことに本当に感謝しています。他の人よりも秀でていなければ、やる価値がないですか。雲の上のような上位の人とも、ライバルたちとも、同じ土俵で戦えることに私は喜びを感じています。良い結果を出したいと思っているけど、そうそううまくはいかなくて、悔しく思ったり、思い悩んだりすることも多くあります。それでも、好きだと思う気持ちはもちろん、マイナスな方向に心が傾くことさえも、自分の中に生まれる全ての感情をいとおしく思っています。この2週間、土日の自由時間と、平日の出勤前と帰宅後、限界までコンテストにチャレンジしていました。寝不足になって、昼休みは10分でお弁当を食べて、オフィスのデスクで熟睡していました。とにかくコンテストに参加したい!その気持ちだけでした。コンテストに参加していた時間は、私にとって、とても、とても幸せな時間でした。

これで私の参加記は終了です。長い文章をここまで最後まで読んでくださり、どうもありがとうございました!

2022年10月1日23時から、Twitter上でAHC014感想会スペースを開く予定です。自分はこんなふうに解いたと、ぜひいっしょに感想を語り合いましょう。リスナー参加でも、もちろん大丈夫です。お気軽にどうぞ。お待ちしています。

そして、今回は参加しなかったけど興味がわいたという方がいらしたら、次回はぜひ私といっしょに参加しましょう!

21.コンテストの結果(2022年10月2日更新)

コンテストが終了し、一晩明けた翌日、2000ケースのシステムテストが終わって、最終順位が決定しました。788人中369位でした。システムテスト前の暫定順位は377位でしたので、少し順位が上がりました。

システムテストの結果最終順位は369位でした

Wladimir Leiteさんの作成してくださったシステムテストの統計資料

Wladimir Leite on Twitter: "estie Programming Contest 2022 (AtCoder Heuristic Contest 014) #AHC014 statistics: https://t.co/K8VNmDMO0F Awesome problem and contest! Unfortunately, I didn't have enough time to compete. Congratulations to @bowwowforeach! Another impressive win!" / Twitter

2000テストケースのスコア

今回、AtCoderの解説放送がありました。writerのwataさんがわかりやすく解説してくれていて、とてもよいのでおすすめします。少しだけピックアップさせてもらうと、29分くらいから始まる重要な考察の話は、自分が特に聞きたかった話です。これが35分くらいの評価関数の話につながります。

www.youtube.com

重要な考察2

解説放送の35分くらいの評価関数の考え方の説明が特によかった

また、2022年10月1日の23時からはAHC014感想会スペースを開きました。estieのmatsu7874さんが(話しても良い範囲での)企業コン裏話をしてくださったり、どんな解法だったかをお一人ずつに話してもらったり、和気あいあいとした感じで、楽しい時間を過ごすことができました。

そして、コンテストは終わったけど、私はまだもうちょっとこの問題に取り組み続けたい気持ちでいます。私に足りなかったのは何なのかを知りたい欲が出てきました。自分がどこにたどり着くのかはわからないけど、また、たどり着けるのかもわからないけど、それでも進んでみたいと思います。

これで本当にこの参加記は終わりです。最後まで読んでくださり、どうもありがとうございました!

AHCレーティング

*1:読み方は「エスティ」

*2:

estie.connpass.com