MC Digital プロコン2023(AHC019) 参加記(最終210位)

概要

2023年3月18日より開催されたMC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019)に参加しました。暫定順位209位、最終順位210位、パフォーマンスは1570となりました。

自己紹介

atcoder上での名前はKoi51です。使用言語はpythonです。
アルゴのレートは現在1003で色は緑です。ヒューリスティックについては、ahc017とahc018の2回だけ参加したことがあり、どちらもパフォーマンスは1150程度でした。

問題のリンク

最終解法概要

「シルエットが成立する最低限+αの立体について体積が1,2,3,4のブロックで立体を作れるよういい感じに体積1ブロックを繋げる」という事を時間一杯行い最も良かった答えを出力

最終解法

1.ブロックが置けるマス全てに体積1のブロック(以下1個ブロックと呼ぶ)を置く

2.シルエットが成立するように最低限ブロックを残しながら不必要なブロックを消していく (ただし低確率で不必要なブロックを残す)

3.それぞれの1個ブロックについて、隣に1個ブロックがある場合繋げて2個ブロックにする。無い場合、隣に1個ブロックが置ける場合1個ブロックを置いて2個ブロックにする

4.それぞれの1個ブロックについて、隣の2個ブロックと繋げて3個ブロックがそれぞれ何個作れるか数え、3個ブロックの余りが出ないようパズル1とパズル2で同じ数だけ、1個ブロックと2個ブロックを繋げて3個ブロックにする(3個ブロックは2種類ある)

5.2個ブロックの数を比べ、余りが出そうな場合2個ブロックが置ける場所に出来るだけ2個ブロックを置いて余りが出ないようにする。

6.それぞれの2個ブロックについて、隣の2個ブロックと繋げて4個ブロックがそれぞれ何個作れるか数え、4個ブロックの余りが出ないようパズル1とパズル2で同じ数だけ、2個ブロックと2個ブロックを繋げて4個ブロックにする(4個ブロックは6種類ある)

7.scoreを計算する

8.時間ギリギリまで2~7を行い、scoreが最も良かったときの答えを出力する

seed=0で最も良かったときの様子

感想

上位陣がとても大きなピースでパズルを作っていてとってもすごいなぁと思いました。
...本当にどうやったのか想像がつきません(dfs?)
私はかなり人力で無理やり解きました(特に3個ブロック、4個ブロックの同型判定など)が、作れるパズルのピースの体積も高々4であり相対スコアも満点(=50,000,000,000)のおよそ 7% であったことからも上位陣の凄さを思い知らされました。
余談ですが、前回のahcでも同じく相対スコアでしたがこのときは暫定スコアが満点のおよそ 32% でしたがパフォーマンスは今回の方が良さそうです。
追記:今回の方がパフォーマンスが良かったです。やった〜。
ここから下はほとんど日記なので読まないでも良いです。

今回新しく行ったこと

・qiitaで日記を書く(思考の整理にかなり役立った)
・C++を少し学ぶ(???)
・chatGPTを少し学ぶ(?????)

3/18(1日目)

問題を読んでみて、あんまり理解してないけどサンプルコードを提出してみる。

結果　絶対スコア:20,662,000,000,000(とてつもなく大きい)

seed=0でscore=98,000,000,000でした(とてつもなく大きい)

4位だ！うれし〜

問題とサンプルコードをよく読む。サンプルコードでは1番目のパズルと2番目のパズルで別々のブロックを使っていたので、できるだけ同じブロックを使うようにコードを改善する。
また、それぞれのブロックに対して「そのブロックが無くてもシルエットが成立する場合そのブロックを削除する」という操作も行う。

結果　絶対スコア:3,576,000,000,000(前回のコードの約17%)

seed=0でscore=22,000,000,000(見た目はだいぶスッキリした)

17位だ！うれし〜

Twitterなどを見ていると既に10個くらいのブロックで作れている人がいてすごいなあと感じる。

これをTwitter上で検索すると色々見れる↓
(#ahc019,#visualizer) until:2023-03-19

4個ブロックや5個ブロックが同じ形であるかを判別する方法が全く思い浮かばなかったのでとりあえず1個ブロックをできるだけ2個ブロックにしてみる。(ひとまずこの考え方を方針にしていく)
結果　絶対スコア:1,413,000,000,000(前回のコードの約40%)

seed=0でscore=9,000,000,000(ようやくパズルっぽい見た目になった)

3/19(2日目)

問題文の評価値の計算方法をよく読む。(1個ブロックを除いて)余っているブロックは無理にでも使ったほうがscoreが良くなることに気づく。
なのでパズル1とパズル2を比較して2個ブロックが余っている場合は出来るだけ置ける場所に詰め込む。
結果　絶対スコア:1,041,000,000,000(前回のコードの約73%)

seed=0でscore=7,500,000,000(パズル1の見た目は変わらず)

3/20(3日目)

2個ブロックを繋げて4個ブロックにしたくなるが、1個ブロックと2個ブロックはそれぞれ1種類ずつしか無いのに対して4個ブロックは6種類もあるので同じ立体か判定できるようにしなければならない。
けど上手い方法が全く思いつかない。

6種類の4個ブロックそれぞれに対して、ある1ブロックの座標を(0,0,0)としたときの他の3つのブロックの座標を全て記録できればどの種類の4個ブロックか判定できそう。
↓
どうやって全て記録するの？
↓
(上手い考えが思い浮かばないので)全て人力で書けばいいじゃん！
↓
想像以上に多くて断念...(実際は150個あった)

3/21(4日目)

方法を無理やり編み出したので作る。(無理矢理書いた部分なので自分でもあまり分かっていない)

1. 3次元ベクトル(a,b,c)を90度回転してできるベクトルを幅優先探索で全て求める。
2. 6種類それぞれの4個ブロックについてその形が作れる移動方法を1つ作る。(例えば(0,0,0)から「下、下、右」と移動すると下のようなブロックが作れる)
   
3. 2で求めた移動方法を回転してできる移動方法を1を基に全て求める。(ふんわりとした説明)

これによりなんとか4個ブロックの種類の判定ができるようになったが無限にバグが出たため提出できなかった。

3/22(5日目)

どうにかバグを直してようやく提出。
今のコードがしていることをまとめると、

1. 1個ブロックが置ける場所全てに1個ブロックを置く。
2. 1個ブロックが無くてもシルエットが成立する場合その1個ブロックを消す。
3. 1個ブロックを出来るだけ繋げて2個ブロックにする。繋げられなくても、隣に1個ブロックを置いた場合に繋げられるなら1個ブロックを置いて繋げる。
4. 2個ブロックが余っている場合出来るだけ使う。
5. 全ての2個ブロックを適当に繋げて4個ブロックがそれぞれ何個できるか数える。
6. それぞれの4個ブロックの作成可能数に対してパズル1とパズル2で作れる数の内少ない数だけその種類の4個ブロックを作る。
7. いい感じに答えを出力する。(激ムズ)

結果　絶対スコア:580,500,000,000(前回のコードの約55%)

seed=0でscore=4,500,000,000(かなりパズルっぽくなってきた)

96位。なかなか良さげ

ヴィジュアライザからもわかる通り孤立している2個ブロックが結構多い(やや勿体無い)
孤立している2個ブロックの周りを...とするコードを考えるのはﾒﾝﾄﾞｸｻｲのでランダム要素を取り入れて無理矢理いいscoreが出るのを期待する。
すること

1. 1個ブロックが置ける場所全てに1個ブロックを置く。(前のコードと同じ)
2. 1個ブロックが無くてもシルエットが成立する場合その1個ブロックを消す。(ただし低確率で消さずに無視する)
3. 前のコードと同じように答えを求める。(このときscoreも計算して置く)
4. 2~3を時間ギリギリまで繰り返して一番良いscoreのときの答えを出力する。

かなり無理矢理感はしますがこれで提出してみました。
結果　絶対スコア:458,000,000,000(前回のコードの約78%)

seed=0でscore=3,250,000,000(6秒だと大抵このscoreに落ち着く)
一度だけ2,750,000,000点取れた様子↓

68位になりました。(かなり嬉しい)

3/23(6日目)

前のコードでは、「1個ブロックが無くてもシルエットが成立する場合その1個ブロックを消す。(ただし低確率で消さずに無視する)」としていたが、孤立して存在する1個ブロックは明らかに邪魔だし、最小ブロック構造の付近にランダムに増やす方向にしたほうが良さそう。→あんまり変わらなかったので改善案候補の1つとしておいた。

1個ブロックはscoreをかなり上昇させてしまうのでどうにかして1個ブロックを無くしたいので、近くに2個ブロックがある場合繋げて3個ブロックにしようと考える。(scoreの式から考えると4個ブロック+1個ブロックより2個ブロック+3個ブロックの方がscoreは良くなる。)

なので3個ブロック判定を作ろうと考えた。(2種類しかないし楽そう)

3/24(7日目)

特に何もせず（？）
一応前回提出したコードを全く変えずに再提出してみる。
結果　絶対スコア:454,250,000,000(前回のコードの約99%)
ほぼ誤差です。

3/25(8日目)

特に何もせず_1

3/26(9日目)

(アルゴの)レートが自分と大体同じFFの人が1日で無茶苦茶良さげなseed=0の結果をtwitterに挙げてて苦しむ。でも(自分と同じく例のレートの人が)1日で書ける内容なら頑張れば作れるかもと思い模索する(dfsをいい感じに書く？)が挫折。

3/27(10日目)

特に何もせず_2
一応前回提出したコードを制限時間を5.2sから5.5sに変えて再提出してみる。
結果　絶対スコア:454,750,000,000(前回のコードの約100.1%)
ほぼ誤差です2。ただ実行時間が5636msになり若干TLEが怖くなった。(システムテストでは実行時間が数%伸びるらしいので)

3/28(11日目)

頑張って3個ブロックを作る処理を書いた。
前回書いたコードがあまりにも普遍性に欠けていたせいで所々直す必要があったのが大変だった。
雑なコードを書いて後の自分を苦しめてはいけない(戒)
3個ブロックを作る処理は書けたが、必要に応じて3個ブロックを増やす処理を書くのを忘れたので後で書く。
これで提出するぞ！と思った...が致命的なバグを見つけたためまだ提出できず。

3/29(12日目)

単なるwhileループ内での初期化忘れでした...
ようやく提出する。
結果　絶対スコア:519,083,333,330(前回のコードの約114%)
????????????????
結果はACだったのでバグがあったとは考えづらい。
しかし単なる(randomによる)不運とも考えづらいので、手元のケースで確認する。

結局デバッグ用に定数値を変更したまま戻し忘れていただけだと判明したので直して再提出。
結果　絶対スコア:440,416,666,663(前々回のコードの約96%)
数値としては微妙ですが一応改善できました。(seed=0の結果は変わらないので省略)

3/30~4/1(13日目~15日目)

忙しかったので何もせず。(たまに同じコードを再提出したりして平均的な絶対スコアを見るなどしていた)

4/2(最終日)

細かい改善を行う。実行速度が定数倍速くなればスコアが良くなる(確率が上がる)がこれ以上定数倍高速化を思いつかなかった。
C++で書けばいいのでは！！！！！！
と思い**伝家の宝刀†chatGPT†**を使いpythonのコードをC++に変換する。(私はアルゴコンテスト中にchatGPTを使ったことはありません。禁止されてませんが念のため)
結果:C++を理解していないためバグを直せず死亡...
そんなに難しいテクニック(dp、二分探索など)を使ってなく、私は †緑コーダー† なので
今からC++を勉強すればいいのでは!!!!!!!!!!!
と思いAPG4bを見ながらC++のコードを書きました。

結果:型を宣言するのが大変すぎて死亡...
pythonってやっぱ書きやすいですね。(C++の実行速度の速さは実感したのでいつかリベンジしたい)
細かい改善をして最終提出
結果　絶対スコア:429,249,999,997

seed=0でscore=2,250,000,000(この記事を書いているときseed=0で実行したら最高scoreを更新しました)