記事の内容
本記事は基礎的なアルゴリズム問題もおぼつかない茶色コーダーが、Heuristic 部門がどのようなお題に取り組むのかも知らないまま、ノリで AHC に参加してみた開発ログもどきです。
私と同様に、AHCってどんなことすんの？ 勉強になるの？ 楽しいの？ と思っているかたの参考に少しでもなれば幸いです。
なお、考えたことや、やりたかったことのみにフォーカスしているので、ソースコードの引用は割愛しています。（ソース見せて説明する必要のあるレベルことはやってないので）
初日 11/29(金)
コンテスト開始の19時には、職場から帰宅途中の電車の中でした。ひとまずスマホで問題を開いて読んでみることにします。
ふむ、何を言ってるのか、まったくわからん
とりあえず問題に書いてある情報の構成だけでも把握しようと全体を眺めていたら、『サンプルプログラム』という項に python のコードが添付されています。中身は出力をランダムで生成しているだけのようでしたが、問題の理解の助けにはなるだろう、と帰宅後、自宅のPCからサンプルコードをそのまま提出してみました。
これまでは Algorithm 部門しか参加していないので、AC と言われるだけで条件反射で少し喜びましたが、コピペしただけだし、 そもそも何がどうなって正しいと言われているのかすらさっぱりわかりません。 ただまぁ、とりあえずスコアはついて０点は回避しました。ランキングを見る限り、まったく同じスコアがついていて、どうやら同じことをしている人が10人以上はいたので、少し安心。
仕方なくサンプルコードをローカルで動かしてみましたが、やはりあまりピンと来ず、初日は問題の読解力だけで足切りを食らいそうだという感触のみで、哀しみを抱えたまま就寝しました。
二日目 11/30(土)
昼から出かける予定があります。せめて外出中の暇に考え事をできる程度に問題を理解しておきたかったので、朝から再度問題と向き合います。
考察用に公開されている Visualizer の使い方も理解しないとダメそうなので、サンプルコードの出力をぶち込んでみたりしていじってみるも、まだピンと来ず。
こういうときは ABC の問題と同じく、とりあえず最低限の入力を受け取って、指定された出力形式の文字列を出すところだけ作ってみよう、とC++のコードを書き始めたところ、制約の確認などで問題文を精読したのがよかったのか、なんとなく意味がわかってきました。
- N 個の箱は入力の順番に詰めていかなければならない
- 入れたくない箱はスキップしてもよい。ただし、たいていの場合スコアは悪くなる
- N 個の箱を最初から詰めなおす作業を、最大で T 回試行できる。途中でやめてもいい
- 箱のサイズ測定には誤差がある
- 一度の試行に対して、並べた結果の縦サイズと横サイズが出力される。その結果も誤差を含む
- 途中で出力されるサイズは利用してもいいし、無視してもいい
- 採点については、T回の試行のうち、最も良い結果1つが採用される
ということは、サンプルのようにランダムで適当に生成した出力でも、超絶運が良ければ上位になれる可能性もある、ということですね。やる気出てきました。
とりあえず自分の理解が正しいことを確認するために、入力された箱を「長いと思われるほうを横にして倒した」状態でy軸（縦軸）合わせで下から投げて、奥から詰めていくだけの命令を、T回同じ内容で出力するコードを書いて、出力を Visualizer に投入。
お、合ってるっぽい。 せっかくなのでジャッジにも提出してみたところ無事 AC。
ここで算出される絶対スコアは低いほど良いので、完全ランダムのサンプルコードにすら負けてるわけですが、まぁ、ひとまずスタートラインには立てたようです。やったね。
...
その後、夜に帰宅して AtCoder ABC 382 に参加。結果は茶3の実力通りの ABC3完でレーティング横ばい。D問題で、方針は完全に合っていたのに、しょうもない実装のミスで通ってないのに、方針自体のミスを疑って迷走したのが敗因でした。4完できたなぁ。
三日目 12/1(日)
朝起きて、とりあえず前日のABCのD問題を復習。再修正したら割とあっさり AC。昨日の焦りまくりはなんだったん。
さて、この記事の本題のAHCのほうは、点数がついている中では順調に順位が下がっていってます。何もしていないのだから当たり前。
自分の理解が間違っていなければ、これは可能であれば荷物をすべて隙間なく並べて正方形になる操作がベストという問題のはずなので、隙間はあっても正方形に近づければスコアはあがるような気がします。試しに半分ぐらいの高さになったら、一列目で一番横長のはずのブロックに合わせて箱を下から投げて、二列目を作るようにしてみます。
まぁ、うん。極端なアスペクト比の箱がないのであれば、そんなひどいことにはならなさそうです。試しに提出してみます。
少しスコアが改善しました。あまり難しいコードを書いている余裕もないので、簡単に作れる範囲で、最大で試行回数(T)と等しくなるまで、分割する列数を増やしていくコードを書いてみます。（正確言うと、一列の最大の高さを総計の 1/1, 1/2, ..., 1/Tと縮めて行くコード）
同じサンプルで Visualizer に投入してみると、こうなりました。(AnimationGIFで最大長変更ごとの経緯を出力）
ひでぇな、これ。
まぁ、誤差があるのはわかっているので当然ですが、時々途中でひっかかった箱の上に、落ちものパズルで置きミスしたみたいな隙間ができてますね。まぁ、この誤差に対応するには試行ごとの出力を受け取って調整するしかないと思うので、今のところ無理です。
再度ジャッジにかけたところ、ようやくサンプルコードに勝ちました。ランダムっょぃ。
4日目 12/2(月)
ここからは平日なので普通にお仕事があります。使える時間もかなり渋いので、（自分にとって）大変な実装は速攻で諦めます。
というわけで、次の課題は以下の二点に絞りました。
- 初手から正方形に近い結果を得られそうな投げ方を試す
- 初手の結果を受け取って、どこかの列が途中でひっかかっているようなら該当箇所を突き止めて修正する
入力された箱をとりあえず横長に倒して列をそろえて下から順に投げる、という方針は当面そのまま。理由は考えることが少なくて実装が楽だからです。高さ（縦）は列を次の列に移すかの判定にしか使わないし、幅（横）はその列で一番長い箱(次に投げる列の基準にする箱）がどれかの判定にしか使いません。
とは言え、上記の2を行えるようにするためには、試行ごとの出力を受け取ってそれを元にして次に試す何かを作らないといけないので、試行のケースを保存して管理できるようにしないと当然無理です。ということは、最低限、箱クラスと、試行ケースクラスぐらいは作成しないとダメそうですね。
というわけで、今まで適当に書いていたコードは全部破棄して再実装を開始しました。ある程度区切りのいいところまで作れたので、いったんコンパイルして動かしてみます。速攻で SEGV。core 吐いて落ちました。まぁ、そんなもんだと思いながら就寝。
5日目 12/3(火)
- 初手から正方形に近い結果を得られそうな投げ方を試す
まず、これからやっつけます。といってももちろん難しいことはできないのでざっくり考えます。列の変更はそこまで積み上げた高さが規準を越えたら、というやり方は変えていないので、運が良ければ正方形っぽくなってくれるんじゃないかなぁ、という高さを先に求めておいてそれに従うだけにします。
求め方も超適当に、箱の推定総面積から逆算することにします。もし箱がキッチリ正方形に収まったと仮定するとその一辺は総面積の平方根になります。なので、隙間ができることを見込んで適当な係数で水増しして求めればそれなりの数字になりそうです。係数をどうするかは動かしてみて後から考えるとして、とりあえずざっくり充填率80%弱ぐらいの逆数で 1.3 にしておきます。
ここで念のため制約を確認したところ、箱の一辺の最大長が10^9、最大個数は10^2個なので、面積の合計が10^20のオーダになる可能性が一応あり64bitでは収まらないことに気づきました。なんでしょうね、この桁数。単位がミリメートルだとしても、1,000km になるんですけどね。高橋くんのグッズとダンボール箱で日本沈没です。
閑話休題。仕方なく変数にはgcc拡張の128bit整数型(__int128)を使うことにします。こうなると標準ライブラリ sqrt() は使えないので平方根は二分探索で求めて解決しました。
6日目 12/4(水)
2. 初手の結果を受け取って、どこかの列が途中でひっかかっているようなら該当箇所を突き止めて修正する
ごちゃごちゃとプログラムをいじって手直しを繰り替えしております。 しかしながらここまで、途中の結果の入力があっても無くても変わらないものしか作っていないので、まだアルゴリズム的なものは何一つ実装していないわけで、そろそろ自分が何をしているのかわからなくなってきています。
とはいえ、先にプログラム全体の流れが固まってないと安心してテストができないので、TLEの防止と試行回数制限を超えてプログラムが動くことを防止する終了ロジックに修正、あわせて、余った試行回数分をランダムで生成した命令で埋める関数など、本筋とはかけ離れたものを用意しているうちに一日が終わりました。お疲れ様です。
7日目 12/5(木)
ようやく②の実装を開始しました。といっても、仕事帰りに『モアナと伝説の海2』を観に行ってしまったのであまり時間がとれません。映画はとてもよかったので満足です。
ちなみに作ろうとしているロジックは以下ようなものです。
- 最初に作った試行ケースを投げてみる
- 高さを取得して予想より出っ張っているようなら原因を切り分けるモードに入る
- まず、2列投げるのを試す
- 高さを取得して出っ張っているようなら、投げるときの基準にしている箱を次の候補（幅が大きい可能性の高い箱）に変える
- 作り直したケースを試して、出っ張っているなら同じように基準を変更していく
- 出っ張りが収まったら3列目4列目...n列目を順に繰り返し
以上です。脳内でなんとなくのコードはできていたので、大急ぎで実装して動かしてみたら、また coredump でした。前の結果を引き継いで次の試行のケースを作る際に、クラスのプロパティやメソッドが整理できていなくて、前のケースから引き継ぐべきところと更新するべきところがゴチャついてるせいです。シンプルなコーディング力不足。
8日目 12/6(金)
山のようなバグを乗り越えて、なんとかやろうとしていることをやりきるプログラムは書けました。
Visualizer の力を借りながら、テスト用の入力を手で一つ一つ追加していって、なんとか作った動作イメージが↓こちらです。
精度低ぅ‥
‥まぁ、一応やりたかったロジックでACになるアウトプットを得られるものはできたのでよしとします。
いったんジャッジに出してみたところ、いったんここまでの自分の中ではハイスコアになりました。ふぅ。
9日目 12/7(土)
とりあえず作業が一段落したので、少し落ち着いて改めて問題文を眺めていたら、微妙な違和感に気づきました。
ツール(入力ジェネレータ・ローカルテスタ・ビジュアライザ)
あれ？ ローカルテスタとビジュアライザって、別に書いてあるのは何故？ ‥今までなんとなく Visualizer 自体がテスターも兼ねていると思ってたんだけど、もしかして別物？
実はここまで、サンプルで配布されている入力そのままでは作成したプログラムに試行の結果を入力する部分が試験できなかったので、その部分は 人力(手動)で作っていた のです。具体的には、途中まで試行させた結果を Visualizer に入れて、表示された高さと幅をテスト用の入力にコピペして、それで再度テストして結果を追加し、を繰り返して試験して、 めちゃくちゃ面倒くさいなぁ と思っていたのです。
試しにローカル版のzipをダウンロードして、中にあったREADME.htmlに従って Rust言語の環境構築から順にセットアップ。特に詰まるところもなく簡単にできました。さっそくREADME通りにテストを実行してみると。 ‥あー、できましたね。 そうか、サンプルの入力ってこのツールで使うためのものだったのか。だったら、もうちょいわかりやすく書いておいてほしかった‥
とりあえずサンプル100個分を今の自作プログラムに通して、Web 版の Visualizer にアップロードして結果を眺めてみると、だいたいのサンプルでは想定通りに動いているようで、一安心、一安心。ん？
（血の気が引く音）あれ？ これ、あんな面倒なロジック組んで下から投げてるより、2列目以降は愚直に右から投げて積んでいったほうがスコア上がるな？ なんで気づかなかったんだ？
ここまで読んでくれている奇特な人がいたら、だいぶ前からこいつ何してんだと不思議に思ってたでしょうね。人間、思い込みで動いているときはこんなもんです（開き直り）。いや、しかしあのデバグの苦労なんだったん、全部無意味だったじゃん。
なお、この直後に傷心のまま夜のABCに臨んだところ、B問題で題意を勝手にクソ面倒な設定と勘違いして時間を大幅にロスし、終了1分前に気づいたものの修正が間に合わずタイムアップ。自身ワーストの 1完 という輝かしい結果に完全に萎えて、そのままふて寝しました。
10日目 12/8(日)
さて、最終日です。日中出かけていたので、使える時間が寝る前の1時間程度しかありません。
昨日の気づきとABCの大ボケで、正直やる気は完全に萎えたままですが、やはり気にはなるので、二列目以降は一つ前の箱を基準に横から投げるだけのコードを書いてみました。前述のスクショと同じテストケースを通した結果がこちら↓。
まぁ、分かってましたが明らかに改善してますね、これ。試しにこのまま、ジャッジに提出してみます。
あ、スコア更新しましたね。よかったけど、気分は複雑。あー、こんなの初日に気づいてもいいのにっていう気持ち。
とはいえ、もう時間もないので、最終的な提出用のコードを作らないといけません。
最後の最後に少しだけ工夫をして、投げるプランを作るときの列の高さを10段階ぐらい刻みで作ってとりあえず投げてみる機能を追加しました。どこかの出っ張りがうまいこと隙間に入ってくれてスコアが上がってくれる可能性があるので、偶然にかけます。
さらにこの場合、試行回数はまず間違いなく余るので、残りはサンプルプログラムとほぼ同じロジックでランダムな合法入力を作って投げまくるという処理を追加して埋めます。サンプルと違うのは、疑似乱数が一定ではないので、ガチで実行ごとにスコアが変わることです。ダメ元。
以上を最終版としてジャッジに提出です。
実行時間制限が 3,000ms もあるのに、36ms しか使ってません。まぁ、プログラムの内部でほぼ何の計算もしてないのでそりゃそうです。
以上で、私のAHC初参戦は事実上終了しました。
最終日 12/9(月)
今、解説放送のアーカイブを拝見しながらこの文章を書いています。スポンサー様の告知を除いて、解説部分は正味70分ほどですかね。私のやったことは、最初の15分ぐらいで通過 していきましたね。そりゃそうです、数学的な工夫とかゼロですし。
自分がやれなかった先の考察は今の自分には簡単に飲み込めない内容なので、何度か拝見してゆっくり理解していこうと思います。
ところで、この程度の実装で順位はどれぐらいかというと、まだ最終結果が出ていないので暫定ではありますが
提出者 1179 人中、272位でした。 いや、問題の本質的なところにまったく踏み込んでない段階のわりには、意外と高順位ではないですかね。これでどの程度のパフォーマンスに評価していただけるのかはまだわかりませんが、個人的には満足できる結果でした。
感想とか
とりあえず 楽しかったです。競技プログラミングというものに触れてみてまだ数か月なので知らないことも多いのですが、ぶっちゃけ、何も知らないときに想像していた競プロは Heuristic 部門のほうだった ってことがわかりました。
問題に対して正解・不正解といえる結果がある Algorithm 部門のほうはパズル的で楽しいですが、正解というより、許容される処理時間内でできるだけ良い結果を競うというのが、ロボコンとか鳥人間コンテストとかみたいで良いですね。
数学的なことがわかっていなくても、ある程度の実装まで行きつけばそれなりの順位につけるみたいですし、プログラムを書くこと自体が好きな人なら間違いなく楽しめると思います。他の人と比べて、あまり強く順位にこだわるとしんどそうですけど、自分の書いたプログラムが、手を加えると徐々に改善されていくのを数字で実感できるのはなかなか気持ち良いです。
当面はABCのほうを頑張りたいところですが、長期戦が組まれたらまた参加したいと思います。
追記：結果発表 12/12(木)
本日、待ちに待った成績発表があったので追記です。さっそくですが、結果はこちらっ↓
まさかの水色perfでした。えー、はい、読んでくださっている方の言いたいことはだいたいわかりますので、自分で書きますね。
「これで？」
ええ、他でもない、自分が一番思ってますとも。他のAHCを知らないので比較はできないんですが、参加登録だけして一度も提出していない人が多すぎなんじゃないかっていう気がするんですけどねぇ。サンプルをコピペするだけで茶perfだったっぽいのに。
まぁ、結果は結果なので、素直に喜ぶことにします。しばらくの間は、心の中で「自分は実質水色コーダー」と思い込んで生きていこうと思います。
ありがとうございました。