AtCoder Heuristics Contest 001 感想

#総合結果
* [Score] 956,690,192,681 pts/1,000,000,000,000 pts (95.67%)
* [Ranking] 294 th (Pretest: 314 th)
* [Performance] <font color=#0000FF> 1668 </font> ($\beta$)
* [Rating] <font color=#000000> 0 </font> → <font color=#804000> 668 </font>  ($\beta$) (+668)

##得点の推移
|Time|Score|Increase[^1]|Event|Submission|
|:--:|--:|--:|:--:|:--:|
|000:00:00|---||<font color=#FF0000><b>START</b></font>||
|000:36:31|<b>823,090 pts</b>|+ 823,090 pts|INTENTION SUBMISSION|[■](https://atcoder.jp/contests/ahc001/submissions/20677516)|
|003:29:56|<b>2,736,916,735 pts</b>|+ 2,736,093,645 pts|貪欲法(1)|[■](https://atcoder.jp/contests/ahc001/submissions/20680906)|
|004:01:08|<b>5,583,906,673 pts</b>|+ 2,846,989,938 pts|貪欲法(2)|[■](https://atcoder.jp/contests/ahc001/submissions/20681586)|
|006:20:31|<b>31,615,821,038 pts</b>|+ 26,031,914,365 pts|アニーリングの実装|[■](https://atcoder.jp/contests/ahc001/submissions/20684998)|
|007:21:22|26,708,127,830 pts||複数回のチャレンジでの最領値|[■](https://atcoder.jp/contests/ahc001/submissions/20686262)|
|007:51:59|<b>39,349,521,606 pts</b>|+ 7,733,700,568 pts|チェレンジ回数を減らす|[■](https://atcoder.jp/contests/ahc001/submissions/20686846)|
|008:22:51|<b>39,665,494,016 pts</b>|+ 315,972,410 pts|チェレンジ回数を減らす<br>アニーリング温度の変更|[■](https://atcoder.jp/contests/ahc001/submissions/20687504)|
|015:39:26|32,260,132,577 pts||長方形クラスの実装(ただし, 没)|[■](https://atcoder.jp/contests/ahc001/submissions/20740208)|
|016:53:45|<b>46,181,411,833 pts</b>|+ 6,515,917,817 pts|Resizeの実装|[■](https://atcoder.jp/contests/ahc001/submissions/20740804)|
|027:10:05|<b>46,305,984,857 pts</b>|+ 124,573,024 pts|$\exp$ 関数を多項式近似|[■](https://atcoder.jp/contests/ahc001/submissions/20748160)|
|031:23:56|<b>46,561,563,946 pts</b>|+ 255,579,089 pts|アニーリングの温度推移を変更<br>得点計算のバグを修正|[■](https://atcoder.jp/contests/ahc001/submissions/20753345)|
|040:32:33|<b>46,629,241,465 pts</b>|+ 67,677,519 pts|(再提出)|[■](https://atcoder.jp/contests/ahc001/submissions/20765611)|
|041:02:40|<b>47,837,049,349 pts</b>|+ 1,207,807,884 pts|2-optのようなものを実装|[■](https://atcoder.jp/contests/ahc001/submissions/20765750)|
|041:33:11|<b>47,876,440,591 pts</b>|+ 39,391,242 pts|(特筆事項なし)|[■](https://atcoder.jp/contests/ahc001/submissions/20765864)|
|052:11:40|47,688,102,965 pts||衝突時にもアニーリング実施|[■](https://atcoder.jp/contests/ahc001/submissions/20772364)|
|059:44:51|47,756,568,411 pts||Resizeの方法を変更|[■](https://atcoder.jp/contests/ahc001/submissions/20781282)|
|060:18:41|47,749,621,194 pts||拡張する大きさを $N$ によって変えるように実装|[■](https://atcoder.jp/contests/ahc001/submissions/20782016)|
|076:36:23|47,578,538,624 pts||チャンスの回数を $N$ によって変える|[■](https://atcoder.jp/contests/ahc001/submissions/20789323)|
|084:52:05|47,632,458,020 pts||Resizeの方法を変更(2)|[■](https://atcoder.jp/contests/ahc001/submissions/20800312)|
|198:46:35|<b><font color=#FF0000>47,905,451,168 pts</font></b>|+ 29,010,577 pts|パラメータを変更|[■](https://atcoder.jp/contests/ahc001/submissions/20926648)|
|199:47:25|47,896,029,667 pts||Sealing Submission|[■](https://atcoder.jp/contests/ahc001/submissions/20928012)|
|200:00:00|---||<font color=#FF0000><b>FINISH</b></font>||

[^1]: これまでの最高点から見た増加した点数

#詳細

## INTENTION SUBMISSION
参加の意思を示すために行う最初の提出. 問題文の理解の確認のためにも行う. 今回の場合, 各企業が要望する場所は全て異なるということから, 企業 $i$ の広告を $[x_i, x_i+1) \times [y_i, y_i+1)$ に設定すれば, 全ての企業の希望を満たし, 不正もないので正の得点を獲得することができる.

## 貪欲法
制限時間目一杯を使い, ランダムに広告と方向を選び, 伸ばして得するならばその広告を選んだ方向に伸ばすという実装を行った. なお, (2) では　(1) において得点計算の方法が誤っていたのを訂正したものになる. 

## アニーリングの実装
伸ばして得するだけではなく, 損になっても確率によって受け入れるというアニーリング(焼きなまし) を実装した.

## 複数回のチャレンジでの最領値
1回限りだったのを, 1回あたりの制限時間を減らす代わりに複数回チャレンジすることによって, 確率的に良い結果を引こうとした.

## 長方形クラスの実装
今後のために長方形クラスを作ったが, 遅くなってしまったため, 結局使われることはなかった.

## Resizeの実装
最終結果を出力の際に, 希望している面積よりも大きい広告になっていた場合, 自由に大きさを縮めることができることを利用して, 得点が大きくなるように広告を縮めて出力した.

## exp 関数の近似
$\exp$ はアニーリング温度の計算に用いられているが, 計算速度が遅い. そこで, 結果の誤差をある程度受け入れ, 指数関数のマクローリン展開
$$\exp x=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+o(x^3)$$
を利用して, $\exp$ を
$$\exp^{\*}(x):=\max \left(0,1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6} \right)$$
に置き換えた.

## アニーリング温度推移を変更
アニーリング法の温度推移を進行度合いを表す変数を $\rho \in [0,1]$ として, $\alpha$ を非常に小さい定数とする. 元々のアニーリング温度の推移は $\alpha^\rho$ であったが, 初期温度 $T_0$ もパラメータに加えた $T_0^{1-\rho} \cdot \alpha ^\rho$ に変更した.

## 2-optのようなものを実装
これまでの実装は全て1つの広告に注目したものであった. この状況から, 伸ばそうとした際に, 1つだけの広告に衝突するならば, その2つの広告について着目して結果が良くなるようであれば更新するように実装した.

## 衝突時にもアニーリング実施
衝突時に結果が悪くなるようであれば必ず却下していたものをアニーリングを実施し, 確率的に悪化する変化を受け入れるように実装した.

## Sealing Submission
システムテストに採用するプログラムを確定させる最後の提出.


#感想

##総評

##良かった点

* これまでのマラソンコンテストでは惨敗が続いていたので, 今回は初めて良い結果で終えることができた.
* 新たな手法を取り入れて, 得点が増えていく様子を楽しむことができた.
* アルゴリズム部門ではあまり登場しない数学の理論を役立てることができた.
* システムテストで順位を20ランク伸ばす事ができた.

##反省点

* 4日でモチベーションが切れてしまった.
* 2-opt のようなものの発展型を考えていたが, 実装できなかった.
* 後半は得点の伸びが発生しにくかった.

##今後やってみたいこと

* オリジナルビジュアライザの実装
* C++やRubyなどでの実装
* 長方形の移動
* 各パラメータを $N$ やデータによって変えられるようにする.
* 遺伝的アルゴリズム
* 等