読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.96

今回は初めて★4の問題に挑戦してみました.無論解法を確認しながらですが・・・

ほとんど丸1日かけてACまでこぎつけました.本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが,一回★4がどのくらいの難易度かみてみたかったので.これをプロ界隈は息を吐くように解くんですか!?!?

No.96 圏外です。 - yukicoder

今回手に入れたテクニック

  • mapのデータ構造.C#でdictionary使ったことあったのですがそれみたいな物ですかね.イテレータの扱いなどに慣れていなかったのもあって苦労しました(そして最終的には使うのをやめた)
  • 凸包を求めるアルゴリズム.無論初見だったので凸包の例題をyukicoderで解いて下準備せざるをえなかった.アンドリューのアルゴリズムはこの本見ながら実装しました.

    www.amazon.co.jp

    No.199 星を描こう - yukicoder

  • Union-Findのデータ構造.これはAtCoderATCで取り上げられていたのでそれで予習しました.ランクという概念は,意外なところで計算量の削減になっていてこれはまたどこかで出会いそうな予感.

    B: Union Find - AtCoder Typical Contest 001 | AtCoder

テクニックを複合的に使う難しさを体感できてよかったです.また基本が定着するまでしばらくは★3埋めに集中します.

 

yukicoder No.96