AHC001　参加記

atcoder　茶色rating:546(high: 655)のanpan_passです。

今回私が参加したAHC001についての、参加記です。（備忘録）

元々ヒューリスティックな知識もなく、ABC等のアルゴリズムコンテストの知識もあまり無く試しに参加してみた。AHCですが、とても楽しく今後アルゴリズムに合わせて精進していきたいと考えております。

まず概略からですが、

まず最初に行ったのが

10000 X 10000では、計算量的に厳しいだろうと考え、1マスを2*2などとし、圧縮することを考えました。

その後、r_iが小さいものを並び替え、小さいものから、面積を大きくしていくのが良いだろうと考えました。

また、正方形の場合、辺の長さが一番小さくすむので、まず正方形で実装することを考え、その後面積の被りをどうするか考えます。

そうすると、一番シンプルな実装が左上、右上、左下、右下に、点を基準に伸ばしていき一番面積が大きくなるように設定すれば、小さい順で並んでいるのでスコアが伸びそうと考え、実装していきました。

今回実装する中で得られた学び、今回の実装の方針で行う場合の改善点、今回のものよりより良いだろうと考える方針、また今後のAHCとの向き合い方を記していきます。

今回実装する中で得られた学びですが、

速度制限よりもメモリ制限に気を付けるべきという点です。

例えば最初に実装したやり方では、2次元配列をdeepCopyし、渡す...などしていたためすぐにメモリオーバーとなりました。これは比較的軽い実装なatcoderではかなり盲点だったと思います。

また速度面に関しては、今回の方針では上記の圧縮はあまり意味がなかったですし、2secではなく5secに慣れていかなければいけないなと感じました。

次に、今回の実装方針で行う場合も、点を基準に、左上...etcと行っていますが、正方形で良いとしても正方形内に点が存在している範囲の移動は考えてもよかったかなと思います。

次に別の方針に関しては他の人のを参考にすると、やきなまし法など私が知らない知識を使った方針などがあります。これらを吸収した後にもう一度AHC001で実装してみるなどします。

次に向き合い方ですが、ABC(or ARC)では、現状私に足りないのはアルゴリズムなどもありますが、少なくとも茶色で低迷しているのは

実装力 > 考察力 >>>　アルゴリズム力

だと感じており、単純なケアレスミスを意識する &&　過去問を行うなどが一番の解決策だと考えておりますが、

AHCでは最低限闘うためのアルゴリズムなどの知識が必要だと感じました。

これに関しては、今回の問題をTwitterなどの感想戦から拾い実際に実装してみるなどを考えております。(ヒューリスティックコンテストに対する蟻本などあったら読んでも良いかも知れません。)

また1週間などの長いスパンですので、ビジュアライザをより最適に見れるような、ツールの作成なども良いかと考えております。