競プロを勉強してみた[1日目]

本日は6/20　1日目

001 Yokan Party

初見でしばらく考えたけどわからなかったので解法をみた。答えで二分探索をするものだった。そうすると答えが満たすかどうかの判定はO(N)でできる。この問題には境目がある(ある数がxより小さければ成り立ち、ある数がx以上であれば成り立たない)と感じたので二分探索をするべきだったなぁと思った。

002 Encyclopedia of Parentheses

bit全探索すればいいだろうなぁと思った。ACしたつもりで提出するとWA。テストケースの4でも間違えていると言われた。よく見てみると辞書順になっていない。冷静に考えてみるとビットは右から埋まるので逆から読み込ませたら上手くいってAC。

003 Longest Circular Road

都市N個に対してN-1本の道路が引かれており、どの都市も行き来できることから、このグラフは木構造を持つことがわかる。よって木の深さ？を求めればいいことには気づいたが、そこからどうすればいいか困った。ここで解答を見た。木の長さのことを木の直径とよび、それを求めるためには最短路計算を２回すればいいことがわかった。確かに一回最短路計算をして仕舞えばその端点は木の一番遠い葉か根のどちらかであるので納得できた。

本文には関係ないが、配列を宣言する時にint A[1 << 29]と言っていて賢いなぁと思った。

004 Cross Sum

縦と横の和を使った

005 Restricted Digits

むずかしそうだからパス(いつか解く、うん、いつか)

006 Smallest Subsequence

多分貪欲法だろうなと思いながら試すもO(SK)になっちゃう。解答を見る。前処理が必要らしい。正直読んでも「ほー、こんなやり方があるんか」としかならなくて自分で発想できる気がせん。いつまで経っても水になれなさそう。解説ACなのでいつかリベンジしたい。

007 CP Classes

Aをソートして二分探索すれば解けるかな〜と思ったらとけた。

008 AtCounter

もらうdpで解けるかなーって思ったら解けた。

009 Three Point Angle

ほしがむっつもあるからあとでやろう

010 Score Sum Queries

累積和使って解けるかなーって思ったら解けた