「競プロ典型 90 問」解いた感想

典型90問を全て解いた。
競プロ典型 90 問 - AtCoder

年始から初めておよそ3週間やった。典型90問は2021年4月くらいからオンラインジャッジが利用可能だったはずなのでかなり時代遅れになってしまった。
せっかくまとまった教材があるのでやってみよう。

感想

  • 90問は終わりの見える問題量でよい
  • すべての問題に解説がある。出題されたTwitterの方を見れば問題と解説が図示されていてとても良い。
  • AtCoderのジャッジで他人のソースコードを見ることができるのがよい
  • 問題が簡単すぎない。AtCoder Beginner Contest (ABC)の問Aや問Bのようなプログラミング言語の確認をするような問題ではなく、一番簡単な問題でも最低限の算数がある
  • 一部の星7レベルの問題はかなり難しい。90問を全て完璧に正解してAtCoder Problemsを緑に埋めたい強迫に駆られる場合は覚悟が要る。

勉強法として全ての問題を漏れなく解くのが理想だが、星7レベルは部分点だけ取って後回しとするのがよさそう。最後の問題の満点解法は ABC の問Exレベルで出題されそうではあるが、ABCを卒業するレート2000を目指すならオーバーなレベル。
公開された当時のABCは6問の問題セットだった。ABC212から8問に増え、2021年12月のABC233から問Hの名前が問Exに変更された。90問全て解けば現代のABCの8問のうち5問はカバーされていそう。6,7問は調子よくて時間が間に合えば応用できる人ならいけそう。問Exは典型90問だけじゃカバーしきれないので、別の方法で対策したい。

〇〇100本ノックのつもりで典型90問に挑戦するとあまりの難易度に驚くかもしれない。

個別問題の感想

006 Smallest Subsequence

「辞書順最小は貪欲」を金言にしている。「長さが固定なら先頭から決める」「長さが不定なら末尾から決める」 という解き方がよくある。
想定解と同様に、こういう文字列の問題はよく次のテーブルを使っている。

nxt[i][c] := S の i 文字目以降で文字 c が初めて現れるインデックス。

メモリ使用量が多いがクエリをテーブルにメモしているので実装するときに便利。

013 Passing

90問の中でダイクストラ法を使うのはこの問題だけなので必ず正解しておきたい。

035 Preserve Connectivity

この問題は当時Twitter上で話題になっていた記憶がある。別解の「Auxiliary Tree (補助木)」という名前が聞きなれないので。
極端な話、ダイクストラ法のヒープも補助木、クラスカル法のDSUも補助木、と言えなくもないので自分が専門用語として使いたいときは定義を書く必要があると思った。

040 Get More Money

必ず Project selection problem という名前も覚える。検索すれば Wikipedia (link) や、より詳しい解説が見つかるかもしれない。

043 Maze Challenge with Lack of Sleep

拡張ダイクストラについて、頂点数無限のグラフ上でキューにプッシュするまでその頂点を陽に作らないようなダイクストラ法の実装のことだと思っていた。それは誤りで正しくは、与えられたグラフの頂点数を増やしたグラフでのダイクストラ法のことを拡張ダイクストラと呼ぶようだ。

047 Monochromatic Diagonal

別解として書かれているが Z-algorithmでも解ける。この問題に対する解法はいつも「先頭からm文字v.s.途中からm文字」の比較になっているので。
Rolling hashなら「途中からv.s.途中から」の比較ができるので解ける問題も広くて良いのだが、実際はどちらでも難易度が変わらないなら Z-algorithm を優先して使うことが多い。Rolling hashは問題ごとに衝突の可能性を検討する必要があるから。

051 Typical Shop

読者の課題の O(2^(n/2)) のアルゴリズムを考えたい。これはマージソートでも使われる「マージ マージ - Wikipedia」を知っていればできる。

マージ
入力:2つのソートされた数列 A, B
出力:AとBの要素を全て含む、1つのソートされた数列 C

C++なら std::merge として実装されているがこれは AとBの長さの和を n として Θ(n) 時間のアルゴリズムである。
これを利用すると半分の要素の組み合わせを全列挙するときにソートが必要なくなり、Θ(2^(n/2)) になる。その後、もう半分と適合する要素を探すときは二分法ではなく尺取り法などで範囲を探せば全体でもΘ(n * 2^(n/2)) ではなくΘ(2^(n/2)) のアルゴリズムを達成できる。

053 Discrete Dowsing

三分探索や黄金分割探索ができる関数とは「上に凸な関数」というのはよくない。Unimodal (単峰) 関数の方が正確でこれは「凸関数」を含む。単峰性をもつ滑らかな関数は「途中までは傾きが正、途中からは傾きが負」の関数である、正と負のあいだに傾きが0の区間があってもよいが傾きが0の区間は峰の一箇所のみ。実際に問053は凸ではない(数列を折れ線で結んだものを関数だとする場合)。

  • 凸性:微分した関数が広義単調減少
  • 単峰性:微分した関数は、正から0、0から負と変化する

055 Select 5

「読者への課題」の N^5 より計算量の良いアルゴリズムについて。Pが素数のときは4重ループで最後の1要素をHashSetで見つければよい。しかし、一般のPについてはいまだ思いついてない。

067 Base 8 to 9

やるべきことは 文字列 -> 整数 -> 文字列 という2段階の変換。
整数型のことを10進法とは呼ばない気がする。