競プロを勉強してみた[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

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

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

サークルの同期のある人がインフラエンジニアに手を出してみたという題で毎日勉強を進めているのを見て、勉強意欲が触発されて何かを始めようと思った。

バイトや期末レポートでここのところずっと忙しかったが、6/20でどちらも落ち着き余裕ができるのでせっかくだからブログアウトプットしながらプログラミングに関することを勉強しようと思った。とはいえ、何もバックグラウンドがない状態で新しいことをゴリゴリと勉強していくほど、真面目でもなければ能力もない。なので、かじったことのある程度の競技プログラミングを一週間真剣に取り組んでみることにした。

2021/6/19現在atcoderのレートは851で緑（user id:igaryo）。

緑diffなら8割くらい解けるが、水diffだとあんまり解けない。

大学受験時は数学が割と得意だったが、大学に入ってからはほとんど勉強していない。

atcoder ploblemsのTrainingみたいなやつを解いた記憶がある。

とりあえずは、E869120さんの競プロ典型90問（競プロ典型 90 問 - AtCoder）を一気に解いていき、一問づつ残すべきことがあったら書きという形で勉強することにする。

一週間の目標は暇さえあれば競プロをしたくなるくらいやり込むこととする。