- 0.はじめに
- 1.問題文の概要
- 2.ビジュアライザ
- 3.1×1の正方形を作ってみる
- 4.最初の提出
- 5.正方形を大きくする
- 6.上下左右に広げて長方形にする
- 7.ずらすことを考える
- 8.制限時間内ぎりぎりまで、ずらすことと広げることを繰り返す
- 9.長方形を変形する
- 10.満足度を計算する
- 11.最終提出に向けて
- 11.結果
- 12.終わりに
0.はじめに
競プロ歴1年のかえでです。よろしくお願いします。今回は、マラソンとも呼ばれるヒューリスティックコンテストに出たときの話について書きたいと思います。
AtCoderで2021年3月6日12時から3月14日20時までAtCoder Heuristic Contest 001が開催されていました。
ふだんはアルゴリズムコンテストにしか参加していないので、マラソンは全くの初心者です。半年ほど前に、初めてヒューリスティック・コンテスト*1に参加したときには、どうしたらよいのか全くわからず、小問Bで1点を取ることしかできませんでした。
難しかったという覚えしかありませんが、新しいレーティングで評価されるというので、チャレンジしてみることにしました。
参加してみた結果、思った以上によい評価を得られ、初心者でもとても楽しめました。今回参加されなかった方も次は参加してみようと思ってもらえるように、どんなことをしてみたのかを書いてみたいと思います。この参加記を書き始めて思ったことは、特別なことは何もしていなかったなということです。正直、恥ずかしく思う気持ちも多々あるのですが、記録することで、あとで振り返ったときに、自分の成長を感じられたらうれしいなと思います。
1.問題文の概要
まずは問題文を読みます。
簡単に言うと、大きな正方形のスペースに、各社の広告を希望通りのサイズで配置することを目標とします。
- 10000×10000のサイズの正方形の中に、50個以上200個以下の長方形を配置する。
- それぞれの長方形は、点座標を一つと、希望する面積を持っている。
- それぞれの長方形が希望する面積の総和は、10000×10000である。
- 実際に配置した長方形の面積と、希望していた面積から満足度が決まる。（満足度の計算式は後述）
- ただし、ｘ座標+0.5と、ｙ座標+0.5が長方形に含まれないとき、その長方形の満足度は0になる。
- 配置した長方形に重なりがあり、重なり部分が0より大きな面積であるときには、不正解となる。（辺は重なっても良い）
- 満足度の総和をできるだけ大きくする。
- 実行時間制限: 5 sec / メモリ制限: 1024 MB
2.ビジュアライザ
問題を解き始める前に最初にしたことは、ビジュアライザを準備することでした。
前回のヒューリスティック・コンテスト後に学んだことの一つが、ビジュアライザがないと考察ができないということです。高得点を目指すためにも、ここはがんばろうと思いました。
今回は公式ではRustで動くツールが提供されていました。c++を使っているので、Rustの環境構築から始めました。1時間ほどかかりましたが、無事に使えるようになりました。
その後、kenkooooさんがRustをインストールしなくてもブラウザ上で使えるツールを作成してくれました。
AHC001のテストケース生成とビジュアライズをブラウザ上で試せるツールを公開しました！自己責任でどうぞ！https://t.co/ApB44TRhhz pic.twitter.com/HQXsOIhmwH
— 宇宙ツイッタラーX (@kenkoooo) 2021年3月6日
kenkooooさんのツールはとても便利で、最初の頃はずっとこちらを使っていました。長方形の配置と得点を見ることができます。
使い方は、上のボックスに入力を入れ、下のボックスには別で実行した出力結果を入れ、Visualizeボタンをクリックします。
公式ツールでは、ビジュアライズと得点の表示に加えて、不正解となるとき、どの長方形とどの長方形が重なっているかという情報と、指定された座標が長方形に含まれず、得点が加点されない長方形があった場合に、それがどの長方形かを教えてくれます。
このプラスアルファの情報が後半になると有用だったので、公式ツールを使えるようにしたことはよかったと思います。
3.1×1の正方形を作ってみる
ビジュアライザの準備が終わり、やっと問題文をじっくりと読みます。まず試したことは、絶対に他と重ならない最小のサイズの長方形、1×1の正方形を配置することでした。結果をビジュアライザで見てみましょう。
すかすかだ！と思いました。スコアは6552でした。パーセンテージで表すと0.0006％です。
4.最初の提出
座標が重ならないことがわかっていたので、1次元10000の配列を、ｘ座標用とｙ座標用に2つ作りました。そして、次の座標が出る前まで、範囲をのばすことにしました。
ビジュアライザの得点は、99278087（9.9%）でした。AtCoderに提出すると、得点は2910692404になりました。AtCorerではテストケースが50個なので、約5.8％の結果になったことがわかります。これが最初の提出でした。そして、1日目最後のACとなりました。
5.正方形を大きくする
2日目になりました。10000×10000の2次元配列を作っても大丈夫だということがわかりました。ふだん参加しているコンテストでは、作ったことのない大きさだったので、最初はできるかどうかがわかりませんでした。この後はこの2次元配列を埋めることを行うことにしました。
まずは、与えられた座標を中心にして、正方形を大きくしてみます。希望の面積になるか、隣とぶつかるまで一回りずつ正方形を大きくしていきました。
おお！前よりも空白部分が減りました。そして、色が見えてきました。希望より少ない面積の場合は青、希望より大きいものはピンク、ぴったりの場合は紫色になります。
得点は540662424になりました。約54％です。大幅に改善された様子が、ビジュアライザからよくわかります。テンションが上がりました！
6.上下左右に広げて長方形にする
次にしたのは、希望の面積よりも小さい正方形があったときに、上下左右に広げることです。まずはｘ軸の0方向に広げてみます。これだけで得点が630780407（63％）になりました。
上下左右、4方向について同じことをしました。
面積がさらに広がりました。入力例1で出力した得点は、794589144（79％）になりました。これをAtCorerに提出すると、得点は38453671530（約76％）でした。
7.ずらすことを考える
良くなってきた感じがしますが、青い長方形を順番に見ていくと、隣の長方形がもうちょっとずれてくれたらさらに良くなりそうだと思います。長方形の中に指定した座標が含まれている間、空白があったら移動させることにしました。
ここで、ソースコードが長くなってきたので、一つ一つを関数にして分けることにしました。先ほど書いたコードは、希望面積より小さく、それぞれの向きに空白のスペースがあれば面積を広げるという、「上に広げる」「下に広げる」「右に広げる」「左に広げる」という4つの関数になりました。
ずらすことに関しても、希望面積よりも小さいときに、「ｘ軸の0方向にずらす」と「ｙ軸の0方向にずらす」という関数を作りました。
「ｘ軸方向にずらす→上下左右を広げる→ｙ軸方向にずらす→上下左右を広げる→ｘ軸方向にずらす→上下左右を広げる→ｙ軸方向にずらす→上下左右を広げる」ことをしたコードを2日目の最後に提出しました。
提出結果は43479974932（約87％）となりました。
8.制限時間内ぎりぎりまで、ずらすことと広げることを繰り返す
3日目になりました。
・clock関数を使って、制限時間内、ずらすことと広げることを繰り返すようにしました。
・極端に細長い長方形があると、上下左右に動かしたときに、つっかえ棒のようになって、動かなくなってしまいます。それがイヤだったので、正方形を作ったあとに、Ｌ字パーツをつけるような感じで2辺ずつを大きくした長方形を作ることにしました。
・ずらす関数に「x軸のプラス方向にずらす」と「y軸のプラス方向にずらす」を加えて、4種類に増やしました。
3日目の最終提出は、44710494883（約89.4％）となりました。
9.長方形を変形する
次に何をするかを考えたとき、下の図のような場所を見つけました。10と番号のついた青い長方形は、まだ希望サイズまで大きくなれていません。下にスペースがあるので、これが縦長の長方形だったら、もっと大きくなれるのではないかと思いました。
そこで面積が小さいときに長方形を変形することにしました。（ここで数時間経過。）その結果下のような形になりました。
10.満足度を計算する
次に何をするかを考察します。これまでは希望する面積になるまで、それぞれの長方形を広げることだけを考えてきました。だから、希望を満たした長方形はその形を維持したまま変わることはありません。下のピンクの11を見た時に、左右に広がってつぶれてくれれば（赤の枠線の形）、下の青い29の長方形の面積を広げることができる（水色の枠線の形）と考えました。
どんなときにつぶれてほしいのかを考えると、隣に面積が小さい長方形があるからです。トータルの評価が上がれば、ピンクはつぶれたときに、同じ面積を維持するだけでなく、小さくなっても良さそうです。
ここでやっと満足度の計算を始めました。rは希望する面積、sは実際の面積です。下の式は、指定された点を含む場合です。
（下の式は、AtCoderの問題文よりコピーさせていただきました。）
満足度 は以下のように定まる。
（中略）
面積を として
満足度の総和 109×∑n−1i=0pi/n
自分の出力結果から、ｎ個の長方形の、それぞれの満足度を出してみます。今の方法だと、ほぼ希望を満たした満足度が100%近い長方形と、満足度が40%～60%の希望よりも小さい長方形に、2極化するのがわかります。
また、面積を増やしていった時の満足度の変化を見て、100%の満足度を持つ長方形の満足度を下げても、満足度の低い長方形を改善した方が良さそうだと思いました。
満足度が低い長方形が隣にあるとき、もしつぶれた方が満足度の総和が上がるときには、長方形を変形する（つぶす）ようにしました。
さて、こんな風に修正を続けていると、ビジュアライザと自分の出力で、得点が異なることに気がつきました。
公式ツールの出番です。
必ず指定された点を含むようにソースコードを書いてきたはずなのに、長方形40ではその点が含まれていないことがわかります。（実は座標が1ずれていたのですが、これはビジュアライザで見ても、わかりませんでした。）
また、二つの長方形に重なりがあったときにも、詳細が出力されました。
11.最終提出に向けて
ここからはデバッグに時間を費やしました。エラー箇所を見つけるのが、本当に大変でした。平日の昼間は働いているので、平日の早朝と夜、土日の時間を使っていました。
あとはrand()関数を使って、呼び出す順番を変えたり、判定する基準に倍率をかけて変化する対象を変えてみたりしました。
この後は、高速化をしてみたいと思いましたが、すでにコンテストの終了時刻が近づいていました。また、どうしたら高速化できるのかもわかりませんでした。
テストケースを連続で実行する方法もわからなかったので、一つ一つ出力していました。なので、提出までに、最大でも30ケースほどしか試していません。もっと試さなければいけないことをコンテスト終了後に知りました。
最終提出の入力例1の出力結果は、973407506（97.3％）でした。
11.結果
システムテストの結果は、953655832652（約95.4％）でした。1000ケース全てにACしていました。また、ソースコードの行数は1853行（自分のつけたコメントその他を含む）になっていました。
12.終わりに
このブログを書きながら、試しに制限時間を100倍にすると、入力例1は、984879055（98.4％）になりました。と思ったら、964879056でした。公式ツールで調べてみたら、17の長方形の得点が0になっていました。何とソースコードがまだ間違っていたようです。
コンテスト終了後には、いろいろな方が解法を書いてくださっていて、自分と全然違っていたので、とてもびっくりしました。本当にすごいと思いました。
ブログを書いてみようと思ったのは、すごいことは何もできない自分が、どのようなことをしていたかを伝えたかったからです。これが私の初参加でした。
長々と書きましたが、自分のブログをここまで読んでくださった方、本当にありがとうございます。
次回以降は、テストケースを連続で試すこと、途中経過を見られるようにすること、高速化をすることにチャレンジしてみたいです。
コンテストに参加している間は、本当に楽しい一週間でした。寝るのを惜しんで夢中になって考えている自分が、おかしくもあり、幸せでした。
*1:2020.6.28に開催されたIntroduction to Heuristics Contest
