yukicoder No.96
今回は初めて★4の問題に挑戦してみました．無論解法を確認しながらですが・・・
ほとんど丸1日かけてACまでこぎつけました．本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが，一回★4がどのくらいの難易度かみてみたかったので．これをプロ界隈は息を吐くように解くんですか!?!?
今回手に入れたテクニック
- mapのデータ構造．C#でdictionary使ったことあったのですがそれみたいな物ですかね．イテレータの扱いなどに慣れていなかったのもあって苦労しました(そして最終的には使うのをやめた)
- 凸包を求めるアルゴリズム．無論初見だったので凸包の例題をyukicoderで解いて下準備せざるをえなかった．アンドリューのアルゴリズムはこの本見ながら実装しました．
- Union-Findのデータ構造．これはAtCoderのATCで取り上げられていたのでそれで予習しました．ランクという概念は，意外なところで計算量の削減になっていてこれはまたどこかで出会いそうな予感．
テクニックを複合的に使う難しさを体感できてよかったです．また基本が定着するまでしばらくは★3埋めに集中します．
