競プロ典型90問：https://atcoder.jp/contests/typical90
001 - Yokan Party
問題：https://atcoder.jp/contests/typical90/tasks/typical90_a
解答：https://atcoder.jp/contests/typical90/submissions/27846976
解法：「K+1個のピースにしたとき、最も小さいピースをx以上に出来るか」という判定問題を考える。これはようかんを前から見てゆき、ピースの長さがx以上となったら切れ目を入れてゆき、最終的にK個の切れ目を入れられれば出来る。本問ではこの判定問題を利用して二分探索を用いて、この判定問題が可能となる最大のxを求めればよい。
003 - Longest Circular Road
問題：https://atcoder.jp/contests/typical90/tasks/typical90_c
解答：https://atcoder.jp/contests/typical90/submissions/21919448
解法：その2頂点を結ぶ辺が木の直径となっている2頂点について辺を追加するのが最大となる。よって求める値は「木の直径+1」である。
008 - AtCounter
問題：https://atcoder.jp/contests/typical90/tasks/typical90_h
解答：https://atcoder.jp/contests/typical90/submissions/21919499
解法：Tを"atcoder"とする。dp[i][j]を「文字列Sのi文字目まで見たとき、そのi文字目で文字列Tのj文字目までを作成するときの通り数」と定義する。
このdp配列はS[i] = T[j]のときdp[i][j] += dp[i-1][j-1]と遷移する。このdpについてdp[N][7]が最終的な答えとなる。（提出コードでは添字iに関しdp配列を使いまわしている）
012 - Red Painting
問題：https://atcoder.jp/contests/typical90/tasks/typical90_l
解答：https://atcoder.jp/contests/typical90/submissions/25164513
解法：Union-Find木を用いる。クエリ1の実行時、赤色マスの上下左右4マスについて、赤色マスがあれば自マスとそのマスを併合する。クエリ2では対象の2マスが両方赤マスかつ同じグループであればYesを返し、そうでなければNoを返せばよい。
026 - Independent Set on a Tree
問題：https://atcoder.jp/contests/typical90/tasks/typical90_z
解答：https://atcoder.jp/contests/typical90/submissions/25164643
解法：重要な事実として、木は二部グラフである。そのため、二部グラフの頂点の塗り分けを行い、多い方の色の頂点を返せばよい。
028 - Cluttered Paper
問題：https://atcoder.jp/contests/typical90/tasks/typical90_ab
解答：https://atcoder.jp/contests/typical90/submissions/27850578
解法：2次元いもす法を用いる。具体的には以下の手順となる。
- 2次元配列
imos2dを準備する - 各長方形
lx[i], ly[i], rx[i], ry[i]に対し
imos2d[lx[i]][ly[i]], imos2d[rx[i]][ry[i]]に1を加算し
imos2d[lx[i]][ry[i]], imos2d[rx[i]][ly[i]]に1を減算する imos2dについて、行ごとに列方向の累積和を取るimos2dについて、列ごとに行方向の累積和を取る
034 - There are few types of elements
解答：https://atcoder.jp/contests/typical90/submissions/27855603
解法：区間[l, r]内にある整数の種類がK以下であるようなl, rをしゃくとり法を用いて走査してゆく。主に以下のような実装方針とした。
- lをforループとし、各lに対するrの最大値を求めてゆく(rは広義単調増加)。
- 各lに対し、rがn未満かつ[l, r]内の整数の種類数がKである限りrを増加させる。種類数の計算はmapを使用する。
- rを増加させきったら、次のループに備え種類数管理のmapを更新する。
