競プロ始めました-kaede2020-

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

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

0.はじめに

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

今回は、MC Digital プログラミングコンテスト2023(AtCoder Heuristic Contest 019)に参加しました。開催期間は2023年3月18日(土)12:00から2023年4月2日(日)19:00までの16日間。2週間強の長期コンテストです。

この参加記は、ヒューリスティック・コンテストをもっと盛り上げたいという思いから書いています。これが公開するに値する記事なのかと考え始めると公開する気持ちが失せてしまうので、何も考えずに公開します。読む人にも軽い気持ちで読んでもらえたらうれしいです。そして、AtCoderの解説には誰でも投稿することができるので、たくさんの方の解法が記事となって残ることを望んでいます。みんな私のように気軽に投稿してしまいましょう。

それでは、がんばるぞー!

1.問題の概要
  • ブロックを使って立方体の一部が欠けている立体を作ります。
  • 正面から見た影、側面から見た影を考えます。
  • 正面から見た影と側面から見た影が01の入力で与えられるので、入力と同じ影ができるようにブロックの形と組み立て方を考えます。
  • ブロックの数は少ないほど良く、一つのブロックのサイズは大きいほどスコアが良くなります。
  • また、もう1種類別の影が入力で与えられるので、共通したブロックで作ることができると、さらにスコアが良くなります。
  • ブロックの形を考えて、できあがりの組み上げ方を2種類分、出力します。

atcoder.jp

2.最初の提出(サンプルコードの提出)

最初はいちばんシンプルな出力を提出することにします。問題文にpythonで書かれたサンプルコードがあったので、C++に書き直して提出をしました。絶対スコアは20,662,000,000,000、 相対スコアは258,199,876でした。

最初の提出(絶対スコア:20,662,000,000,000 )

相対スコア258,199,876、順位は313人中182位

seed0のビジュアライザです。1辺が1のブロックで埋め尽くされています。ここからブロックを間引いたり、つなげたりして、Scoreを下げていきたいと思います。(このScoreが小さいほど得点が良くなります。)

seed0、Score=98,000,000,000
3.最初の考察

まずは2個をつなげてみたいと思いました。2個がつなげられたら棒状に、棒状ができたら板状に、そこからは3次元のブロックにできたらと思います。一筆書きのイメージで、連続した部分を同じ番号にできたらと思います。

4.2、3回目の提出(サンプルコードを少しだけ変える)

ビジュアライザの見方にも慣れてきました。サンプルコードは1種類目と2種類目のブロックを全て別にしているので、1種類目の左側の立体が青っぽい色、2種類目の右側が赤っぽい色になります。

これを同じブロックを使いまわすようにします。単純に2種類目のIDを1にリセットしてナンバリングを始めます。

1種類目と2種類目のIDの数字の大きい方が出力時のn(ブロックの総数)になります。これを忘れて提出をしてWAになりました。30分待っている間にローカルでテストケースを連続でまわすコードを書いて、まだ時間が余っていたので、このブログを書いています。

seed0のスコアは53,000,000,000になりました。1回目の提出の半分近いスコアになります。ビジュアライザの色はブロックにIDをつけていて、IDが小さい方の数字が青、大きいIDを振ったブロックが赤色に変わっていきます。

seed0、Score=53,000,000,000

前回のRECRUIT日本橋ハーフマラソン2023冬(AHC018)の復習をしているときに、ローカルでの実行をかなり意識したので、今回はとてもスムーズに書き直すことができたのでうれしく思いました。
2回目の提出結果は、絶対スコアが11,479,000,000,000、相対スコアは289,767,725、383人中189位になりました。

絶対スコア:11,479,000,000,000

相対スコア:289,767,725 、383人中189位
5.4回目の提出(不要なブロックを取り除く)

ブロックを取っても影ができている場合にはブロックがなくても良さそうです。不要なブロックを取り除いてみたいと思います。そのために、必要なことを考えます。

  • ブロックが何個重なっているかを管理する。正面から見た場合と、側面から見た場合の両方を用意する。
  • ブロックを取っても大丈夫かを調べる。
  • ブロックを取った後にIDを詰める。

これを書いていて思ったのは、ここが差分の計算になるので、ここで計算量を落とすことができると、高速化できて良さそうだと思いました。今は前から見ていくつもりですが、その後は1個のブロックの位置を1ずらしてOKかどうか判定するといったことをしていきたいと思っています。

まず、ブロックが何個重なっているかを調べてみました。正直なところ、頭の中で立体を想像するのが難しいので、ビジュアライザと並べてみました。1のところは削れませんが、2以上のところは削れそうです。

ブロックの重なった個数

削れそうなものがあるのはわかりましたが、どのブロックが不要なのかがわからないので、調べながら削っていきたと思います。

  • ブロックを1個選ぶ。
  • ブロックを取り除いても影ができるか調べる。
  • できるならば削る。できないならば削らない。

コードを書き上げました。書いてみてわかったのは、IDの連続性がなくなってしまうので、もう一度IDを振り直さなければいけないということです。また、XYZ方向がどちらの向きなのかわからずに手間取りました。

100テストケースの結果です。2回目の提出の3分の1程度になりました。

100テストケースの結果

seed0のScoreは22,000,000,000になりました。ビジュアライザを見ると、かなりすっきりとしたのがわかります。

seed0のビジュアライザ(Score=22000000000)

提出をします。絶対スコアは3,576,000,000,000でした。

絶対スコア:3,576,000,000,000

相対スコアは618,100,805、順位は440人中154位になりました。

相対スコア:618,100,805、154位(440人中)
6.2種類のオブジェクトで使うブロックの数を等しくする

ここで、問題文に戻ります。2つのオブジェクトで使用するブロックに差があるとスコアが悪くなるので、3回目の提出ではどちらも最小のブロック数にしましたが、ブロックの数をそろえたいと思います。

  • 1番目と2番目で使用したブロックの数が異なっていた場合、ブロック数が少ない方にブロックを足す
  • ブロックの足し方は、影になる場所にブロックが置いてなかったら置き、ブロック数のカウントを更新する
  • ブロック数が同じになるまで繰り返す
  • ブロック数が同じになったらIDを振り直して終了する

左右のオブジェクトのブロック数を同じにする

やってみましたが、得点は変わりませんでした。オブジェクト1とオブジェクト2のブロック数を同じにすることと、ブロック数が増えることの重みが同じだったからです。うーん、これは今やることではないなと思ったので、次にいきたいと思います。

7.5回目の提出(ブロックをZ方向に2個つなげる)

さて、ブロックをつなげてみたいと思います。まずは2個のブロックを作ってみたいと思います。

  • ブロックが隣接していたときに同じIDを入れる

seed0ではスコアが悪くなってしまったものの、100テストケースを回した結果は3割くらい改善していたので、提出をします。

100テストケースをまわした結果

seed0(Score=235,000,000,000)のビジュアライザ(2個の連結ブロックを作成)

絶対スコアは2,468,000,000になりました。

絶対スコア:2,468,000,000,000

相対スコアは793,264,233になり、457人中133位になりました。

相対スコア:793,264,233 133位(457人中)

特にスコアが良くなっていたseed94を見ます。

seed94 Score=65,000,000,000

左右のオブジェクトで共通するもっと大きなブロックを作ることができそうだなと思いました。

8.休憩中(ここまでの感想と悩んでいること)

思った以上に順調です。今回はいつもよりバグらせている時間が少ないと思っています。変だなと思ったときに、ひとつずつ基本的なデバッグを実行することと、コードの書き方もシンプルになるように気をつけていますが、こんなに効果が出るものなのでしょうか。問題のせいかな。理由はよくわかっていません。現在のコードは350行ほどになっています。

さて、今悩んでいることです。ブロックは回転させることができるのですが、今は同じ方向でしか一致するかどうかを見ることができていません。回転させてみたいと思っているのですが、ブロックの一致判定方法がわかりません。ブロックの一致判定ができないので、スコア計算をするコードも書けていない状態です。今は配布されているWindows用のコンパイル済みバイナリでスコアを計算しています。

9.ブロックをX方向とY方向にも2個つなげる

先ほどはZ方向にしかつなげていなかったので、X方向とY方向にもつなげられるブロックがあればつなげてみたいと思います。数は2個にします。

うーん、IDを再度振るときにバグります。ちょっと改善策が思い浮かばないので後回しにします。

10.ブロックの位置をずらしてみる

Z方向にブロックをずらすと2個のブロックを増やせるかもしれません。ブロックの位置をずらしてみたいと思います。

  • Z方向の隣にブロックがないことを確かめる
  • ブロックの位置をずらしたときに、影ができるかを確かめる
  • できるならずらす。できないときはずらさない。
  • オブジェクト1、オブジェクト2の両方について行う
  • IDを振り直す

書いてみましたが、めいいっぱいブロックを削った後なので、移動できるブロックがありませんでした。できるだけ連続したブロックになった状態で不要なブロックを削るようにしたいと思うので、ブロックを削るときの条件に加えてみたいと思います。

(時間経過)

やっぱり棒状に伸ばせるだけ伸ばしてみたいと思います。

(時間経過)

難しい~。オブジェクト2に使うとき、5はなくても2と3はあるとか、1と4はあるとかそういうことを考えたいけど書けない。あれ?なんかこのアルゴリズムを知っているような気がします。再帰かな?なんだか書けそうな気がしてきました。

んー、オブジェクト2は前から並べるのではなくて、サイズが大きい順に埋めていきたい。あとやっぱり回転をさせたい。

やりたいことがあるものの、うまく形にならなくなってきました。がんばろー。

(進捗0でコンテスト4日目が終了)

11.ブロックを2個つなげたものにする

順調だと思ったとたんにうまくいかなくなりました。そんなときにビジュアライザの共有でたきさんのツイートを見ました。4回目の提出で私と同じ得点だったので覚えていました。そのたきさんが2個つなげたブロックにしていました。

私の4回目の提出と比較してみましょう。1個目のオブジェクトの並びがとても似ていると思いました。これを参考にして、もう一度2個つなげたブロックを作ってみようと思いました。

seed0、2個ブロックをつなげる

考え方を変えて、2個ブロックが連続で残るように不要なブロックを取り除いていきたいと思います。

12.3方向に2個ブロックを作る(残りは1個)

考え続けてはいたもののピンと来なくて、手が動かないまま時間が経過しました。今はコンテスト7日目2023年3月24日金曜日の夜です。

やっぱり不要なブロックを取り除いたものを2個ブロックにしたいと思います。まずは今あるブロックを使用して、隣にブロックがあって3方向につなげられれば2個ブロックにして、余りは1個にしたいと思います。

seed0のScoreは11,500,000,000になりました。

絶対スコア:1,573,500,000,000

相対スコア:800,765,330 578人中208位

もともと隣にブロックがなくて1個になったとき、もし隣にブロックを置ける空間があって、シルエットの変更がないならばブロックを置いて2個にすることにしました。

もともとあるブロックを調べるときは3方向(下・後・右)でしたが、ブロックを挿入するときは、上下前後左右6方向調べるようにしました。それでも2個にできないときは1個のままにしてあります。

seed0のビジュアライザを見ます。Scoreは8,000,000,000になりました。

おおっ!

下がりました。

前回は11,500,000,000だったので、桁が一つ減りました。ビジュアライザの共有を見ていると、今よりも十分の一以下にスコアを減らせるようです。まだまだやることがたくさんありそうです。

seed0 Score=8,000,000,000

100テストケースの結果です。良くなっていたので提出します。

100テストケースの結果

絶対スコア:1,344,000,000,000

相対スコア:1,29,560,351 587人中187位

絶対スコアは1,344,000,000,000になり、相対スコアは1,29,560,351、順位は587人中187位になりました。一歩ずつ改善していることが感じられ、何をやっていけば良いのかということがまだまだたくさんあるので、今回の問題はとても楽しいなと思います。

スコアが悪化したseed7を見ると、オブジェクト2の方が複雑な形をしていて、ブロックの数が多くなっていました。

いつの間にか条件分岐が多くなりコードの可読性が悪くなってきたので、リファクタリングをしてから、もしオブジェクト1の2個ブロックが余るようだったら、1個に崩すようにします。少しだけ改善しました。

絶対スコア:1,332,000,000,000

相対スコア:1,048,373,386 608人中197位

今思っているのは、各ブロックが、6方向の連結情報を持っていると良いのかなということです。データ構造を追加したい気がしますが、ちょっとまだ悩み中です。ブロックを3個にすることを考えたいと思います。あと、オブジェクト1とオブジェクト2で使用ブロック数の差が大きいものがあるので、それも何とかしたいと思います。順番を変えると良いのかな。

13.暗転(出口の見つからない長いトンネル)

2023年3月26日の午後です。3個目に取りかかる前に、毎回余計なブロックを取り除く実装を加えます。

絶対スコア:1,225,000,000,000

相対スコア:1,114,308,686 618人中202位

3個を入れてみます。少し良くなりました。

絶対スコア:1,129,833,333,329

相対スコア:1,171,130,382 638人中209位

100テストケースの結果を見ると、良くなったものと悪くなったものがあります。悪くなったものは、オブジェクト1で3個つながったブロックを作ったものの、オブジェクト2で使うことができなかったというものでした。今はオブジェクト1で作れるだけ3個つながったブロックを作っていますが、オブジェクト2で使えなくなったら、作るのをやめた方がよさそうです。

今の順番

  1. オブジェクト1で3個つながったブロックを作る。
  2. オブジェクト1で2個つながったブロックを作る。
  3. オブジェクト1で1個足して2個つながったブロックを作る。
  4. オブジェクト1で1個のブロックを作る
  5. オブジェクト2でオブジェクト1で使った3個つながったブロックを使う
  6. オブジェクト2でオブジェクト1で使った2個つながったブロックを使う
  7. オブジェクト2で1個たしてオブジェクト1で使った2個つながったブロックを使う
  8. オブジェクト2でオブジェクト1で使った1個のブロックを使う
  9. オブジェクト2でオブジェクト1で使った2個つながったブロックが余っていたら1に崩して使う。
  10. オブジェクト2で新たに1個のブロックを作る。

うん、書き出しただけでも無駄がたくさんありそうです。順番を変えたいと思います。

3個のブロックを作るのをやめて、4個のブロックだけを作るようにしてみました。

絶対スコア:1,086,000,000,000

相対スコア:1,130,051,856 640人中216位

3個ブロックもあった方が良いのかな。

絶対スコア:1,077,833,333,328

相対スコア:1,125,451,118 641人中214位

うーん、あんまり変わらない。大きなブロックはオブジェクト2でも大きなブロックを作ることができるときだけ作るようにしようかと思います。

オブジェクト2で4個をつなげたブロックができるときにオブジェクト1で4個を作ることにしたら、ずっとバグらせています。今日は寝ます。シルエットが違うので、XYZ方向が間違っている気がします…。寝ます…。

朝です。寝て起きたら、バグってそうなところが思い浮かびました。見直してみます。何箇所か修正しているうちに、見つかったので修正します。

提出すると、少し良くなっていました。今はブロックを追加して作るということをしていないので、ブロックの変形を追加すればさらに良くなりそうです。

相対スコア:1,016,333,333,335

絶対スコア:1,230,795,783 647人中214位

スコアの悪いものをビジュアライザで見ます。使っているブロックの数に大きな差ができていました。余ったやつは全部つなげた方がよさそうだと思います。できることなら、余らないようにしたいものです。

頭の中がすっきりとしないまま、コードを書いています。「1個足して4個になるブロックを作ること」をしてみましたが、スコアは良くならず。ビジュアライザを見たり、デバッグをしたり、時間を無駄に過ごしている感じがします。また、オブジェクト1とオブジェクト2で使用しているブロックの差を出してみましたが、これも直したいと思いました。(下の図はseed0では、1個のブロックが2個余計に多くオブジェクト2で使われているということを示しています。)

差分のブロックを出力してみた

平日になってしまったので、まとまった時間が取れなくて、細切れに考察をしています。余ったブロックをもう一方のオブジェクトに入れるもしくはくっつけて2個以上の塊にできるとスコアを改善することができそうです。1個だとブロックの増加分で差し引きゼロになってしまうのは以前試した通りなので。

seed1で11個のブロック(体積13)の差ができているので、これを解消することを考えます。ビジュアライザを見ます。余った体積1のブロックを2個くっついたブロックにつなげて、3個にすることができそうです。

ん、というか3個ができるのになぜ作っていないのかな?何となく自分の思った通りの実装ができていないように思います。まずはそこから見直したいと思います。

seed1のビジュアライザ

見直してみたら、1個たして3個にするというのをしていませんでした。書き足したいと思います。書き直してみたら少し良くなりました。

seed1のビジュアライザ

100テストケースの結果も少し良くなっていたので提出します。絶対スコアは、1,008,666,666,667、相対スコアは1,119,770,237、680人中237位になりました。

あんまり変わっていません…。

絶対スコア:1,008,666,666,667

相対スコア:1,119,770,237 680人中237位

行き詰っている感じがします。他のseedのビジュアライザ結果を見ていたのですが、seed8を見て、もっと板状にした方がいいなあと思います。今週に入ってからずっと考えているのですが、オブジェクト1とオブジェクト2のシルエットから、生成するブロックをもっと効率よく作る方法がありそうな気がしています。

seed8のビジュアライザ

 

絶対スコア:958,833,333,334

相対スコア:1,177,399,568 684人中234位

最後の悪あがき的なことをやって満足したので、明日から別のコードにしたいと思います。結局あまり変わらなかった。コードを1300行も書いてしまいました。うっかり1時までやってしまった…。明日の仕事大丈夫かな。

14.悩み中

2023年3月29日の夜です。残り5日。長いような、短いような期間です。昨日は全部最初から書き直そうみたいな気持ちになりましたが、まだ何もやっていない気持ちになって、もっと考えようと思います。

そういえば、ブロックの形が一致を確かめる方法をずっと考えていたのですが、3面(上・前・右)の情報があれば良さそうだと思いました。

なので、ブロックをくっつけてもいいのかな、とか、同じ数のブロックはIDを入れ替えても良いなと思ったりしています。あと、いろいろなやり方の中でいちばん得点がよかったものを出力したり、他点スタートを試したりもしたいと思います。

というわけで、やっとスコア計算を実装しました。

そして、最初にできるだけブロックを削った方が良いスコアになるケースと、ブロックを削らない方が良いスコアになるケースがあったので、両方試して良い方の解を出力するようにしました。seed0のビジュアライザは4個をつなげたブロックが多くなりました。

seed0 Score=6,833,333,333

100テストケースの結果も前回より9%ほど改善していました。

条件を変えてずっと試し続けているところ

提出します。絶対スコアは880,250,000,001になりました。相対スコアは1,259,718,031になり、697人中234位になりました。

絶対スコア:880,250,000,001

相対スコア:1,259,718,031 697人中234位

余っているブロックを移動させたいなあと思いつつ、もう寝る時間になってしまいました。残念…。昨日夜更かししたせいで昼間がとても眠かったので、今日は早く寝ます。

15.光が見えてきた?(コンテスト期間残り4日)

2023年3月30日の夜です。ふと頭に思い浮かびました。もともと使える面は3面あるのだから、残りの1面をもう1つのオブジェクトのシルエットを使えばいいな、と。しかしそれは難しそうなので、そこまでしなくても単純に、オブジェクト1とオブジェクト2のシルエットを重ね合わせるだけでも良いのではないかと思います。

たとえばseed8。

seed8のシルエット

共通部分を見ます。

 

seed8のシルエットの共通部分

大きな同じ形のブロックを使うことができそうです。こんなふうに全てのパターンを重ね合わせて一番重なりの大きなものを使って最初にブロックを作ってあげると、スコアが良くなるのではないかと思いました。

1つ懸念があります。実装できる?

というわけで、まずはシルエットはそのまま、回転したり、上面に配置したりせずに、入力で受け取ったものをそのまま重ね合わせて共通ブロックを作ってみたいと思います。

これを初期解にしてもいいかなと。

あ、あと差分のブロックをもう1つのオブジェクトに入れて、もう一回やり直すというのもやりたい。1個ブロックをずらしてやり直すとか。時間はいっぱい余っているのだから何回もやって、いちばん良いものを出力するようにしたいと思います。

考えたことを実装しようとするのをやめたら、だいぶシンプルな解法になった気がします。細かい部分はこれまでの実装を使えば良さそう。

書きました。30分くらいで、わりとすんなり書けました。

seed8はscoreが1,172,619,048になりました。これまでのベストが3,750,000,000だったので、約69%、scoreを小さくすることができました。

うれしい。

ただ、本当は黄緑のブロックと水色のブロックは1つにまとめることができるのですが、連結判定部分がうまく書けていません。さっきの図では同じブロックにできるとわかるので、何かうまくできないかな…。

seed8のビジュアライザ score=1,172,619,048

全体では9%くらい改善したので提出をします。

絶対スコアは824,689,774,633になり、相対スコアは、1,370,712,437になりました。順位は715人中233位になりました。

絶対スコア:824,689,774,633

相対スコア:1,370,712,437 715人中233位

やっと光が見えてきたかもしれません。相対スコアも停滞していたところから、少し良くなってきました。実行時間は646 msで、6sという制限時間は十分に余っています。シルエットの重ね合わせを全て試していきたいと思います。

そのために、まずは上面から見た情報を管理したいと思います。

立体が苦手なので、小さな数から考えます。シルエットの正面と右側が1ずつだとしても、上部から見たときは5個置くことができます。思った以上に候補があるんだなと思いつつ、0のところにはブロックを置けないので、1つでも0のところにシルエットが重なってしまう場合はできない配置だなと思います。

また、オブジェクト2のシルエットを重ねるのは良さそうな案だと思いますが、座標の管理がよくわかりません。うーん、どうしよう。夜も更けてきたので、今日の考察はここまでです。明日は実装できるといいなと思います。

3×3の立方体で考える
16.ぐるぐると考え中(コンテスト残り3日)

金曜日の夜です。

回転したい。回転したい。回転したい。

seed0のビジュアライザ

オブジェクト2が合っていないけど、こんな形ができるのは良い感じ。ブロックを回転させて座標を一致させたい。

今日はここまで。土日にがんばりたい。

17.ブロックの向きを変える(コンテスト残り2日)

2023年4月1日の朝です。回転、座標軸を変えたらそれでいいんじゃない?と思ったので、変えてみます。

お、それっぽくなりました。

seed0のビジュアライザ(オブジェクト2のX座標をY座標に、Y座標をZ座標に、Z座標をX座標にしたところ)

①オブジェクト2のX座標をY座標に、Y座標をZ座標に、Z座標をX座標にする。

②オブジェクト2のX座標をZ座標に、Y座標をX座標に、Z座標をY座標にする。

この2種類を追加します。

100テストケースをまわすと9%くらい良くなっていたので、提出します。

ここでうっかり、ローカルと提出時の実行が異なるものを出してしまい、待つこと30分。もう1度提出しました。絶対スコアは、695,651,248,104になり、相対スコアは1,517,882,069、739人中244位になりました。順位はあまり良くなっていないものの、少しずつスコアが良くなっているので、うでしいです。

絶対スコア:695,651,248,104

相対スコア:1,517,882,069 739人中244位

スコアはベストではありませんが、seed0のオブジェクト2のX座標をZ座標に、Y座標をX座標に、Z座標をY座標にしたところビジュアライザのようなブロックができていました。

seed0のビジュアライザ(オブジェクト2のX座標をZ座標に、Y座標をX座標に、Z座標をY座標にしたところ)

回転させながらブロックを作っていけないかなあと考えます。

やってみました。

seed0のビジュアライザを見ます。スコアは悪くなっていますが、いろいろな形のブロックが使われているのがわかります。無駄なブロックがあるので、小さなブロックから取り除くということができればと思います。

seed0のビジュアライザ

取り除いてみました。

seed0のスコアは5,100,000,000になりました。

seed0のビジュアライザ

提出します。

絶対スコア:650,712,235,930

相対スコア:1,570,293,495 744人中246位

順番を変えたり、ブロックを削除したり、時間いっぱいいろいろなパターンを試して、一番良いものを出力したいと思います。

とりあえず、2個以下のブロックを消しながら回転させてみます。seed0のスコアは、3,433,333,333になりました。100テストケースの結果も少し改善したので提出します。

seed0のビジュアライザ score=3,433,333,333

相対スコア:632,881,685,524

絶対スコア1,625,506,149 751人中241位

今日はここまで。明日は最終日。最後までがんばります。

18.コンテスト最終日

2023年4月2日の朝です。いつの間にか4月に入っていました。昨日からずっと考えていること、それは…。

つなげたい。つなげたい。つなげたい。

今日の目標は分割されているブロックを「つなげること」です。

体積2のブロックと体積3のブロックの2個があるとスコアは1/2+1/3=5/6になりますが、体積5のブロック1つならスコアが1/5になります。それを目指したいと思います。

つなげました。seed0のスコアは2,794,444,444になりました。

seed0のビジュアライザ score=2,794,444,444

100テストケースをまわして結果を見ます。

ん、何かバグってる…

(時間経過)

バグっています…。もうダメかも...。

(時間経過)

時刻は18時を過ぎました。ブログも書かずにずっとデバッグをしていました。(途中で少しだけ桜を見に行きました。)症状としては、つながっていないブロックに同じIDが振られていること。たとえばseed13のビジュアライザを見るとこんな感じでした。

seed13のビジュアライザ

バグを修正して、もう一度提出したかった…。残念…。

現在の暫定順位は785人中271位です。

785人中271位

最終提出の100テストケースのスコア

条件を変えながら100テストケースの結果を見ました
19.終わりに

こうして、長いと思っていたコンテストが終了しました。きれいなコードを書けていたのは最初の数日だけでした。気がつけば2000行を超えるような、重複のたくさんあるプログラムを書いてしまいました。最終日はバグを修正できませんでしたが、それでもいつもよりもデバッグにかける時間は少なく、たくさん考察することができました。だから、満足しています。とても、とても楽しい時間でした。

余談ですが、自宅用にワークチェアを買いました。価格が驚くほど高いので悩んでいたのですが、お給料が出たので買いました。とても快適で、時間が経っているのに気がつきません。昨日も今日も、コードを書いていたらあっという間に時間が経ってしまいました。

さて、コンテストが終わったらスペースを開くつもりです。2023年4月2日21時から1時間程度の予定。いろいろな方から話を聞くことができたら良いと思っています。話したい方も聞きたい方も気軽に来てもらえたらうれしいです。また2023年4月5日20時からはAtCoder LiveでAHCラジオも放送予定。こちらも楽しみにしていただければと思います。

これからも多くの方にAHCに参加してもらえるよう、自分のできることを続けていければと思っています。このブログやスペース、そしてAHCラジオを見て、興味を持ってくださる方が増えていったらうれしく思います。

最後に、長い文章をここまで読んでくださり、本当にありがとうございました!

20.最終結果(2023年4月3日更新)

システムテストの結果が出ました。システムテスト前の暫定順位は274位、システムテスト後の順位も274位と変わりませんでした。

最終順位:787人中274位

システムテスト2000ケースのうち、12ケースでWAでした。

システムテスト2000ケースの結果

ヒューリスティックのRatingは14上がって1384になりました。

ヒューリスティックのRatingは14上がって1384になりました

今月は長期コンテストがないので、復習をがんばりたいと思います。