典型90問 精進.
ルール
- 毎週月, 火で友人と★4と★5を埋めていく
- ★5は恐らくわからないので5分で方針を予想して解説ACをする
- アルゴリズムの引き出しを増やすのが目的
リポジトリ
https://github.com/wakame-tech/kyopro
- 1週目(07/27-10/11)
07/27
006 - Smallest Subsequence（★5）
- 貪欲 + 表で高速化
08/03
008 - AtCounter（★4）
- 部分列
012 - Red Painting（★4）
- 連結判定 -> 上下左右に対して連結
08/10
013 - Passing（★5）
- dijkstraは $s$ から $1 \cdots N$ までの最短, $1$ からと $N$ からやればok
- 木の直径も $1$ からBFS, 最遠からBFSすればよい
021 - Come Back in One Piece（★5）
強連結成分分解(SCC). 知らなかった.
- 各頂点を始点としてDFSして帰りがけ順に番号振る
- 辺の向きを逆にしたグラフに対して, 番号大きい順にDFS
- 逆向き $\because$ ループ以外をシャットアウト
snippet を作成.
08/17
026 - Independent Set on a Tree（★4）
BFSで隣接頂点は色変える, 多い方から $\frac{n}{2}$ 個選ぶ
028 - Cluttered Paper（★4）
二次元いもす法
08/25
029 - Long Bricks（★5）
- (座圧) + 遅延セグメント木, 聞いたことしかない.
snippet を作成.
08/30
030 - K Factors（★5）
- 素因数を1ずつ足していく
034 - There are few types of elements（★4）
- 尺取る
09/06
036 - Max Manhattan Distance（★5）
- マンハッタン距離は45°回転
- $(x + yi)(1 + i) = (x - y) + (x + y)i$
037 - Don't Leave the Spice（★5）
- 普通のDP + セグ木で高速化
- $\max(\mathrm{dp}[i - 1][j - R_i], \cdots \mathrm{dp}[i - 1][j - L_i])$ -> $\mathrm{segtree.query}(j - r, j - l + 1)$ にする
- RMQに帰着
09/07
039 - Tree Distance（★5）
- 子孫の数を木dp(=DFS) で出す
- 貢献度を求めて総和
- 主客転倒ともいうらしい
09/13
042 - Multiple of 9（★4）
- dp
- 和が $K$ = $\sum_{i = 1}^9 (i + \mathrm{和が} K - i)$
09/14
043 - Maze Challenge with Lack of Sleep（★4）
- 01-BFS
- Pythonで書いたが間に合わなくてJuliaで書いたがJITコンパイルのオーバーヘッドのせいで間に合わなくてC++で書いた.
051 - Typical Shop（★5）
- 半分全列挙: $O(2^N) \to O(N \cdot 2^{\frac{N}{2}})$
- 例外の処理で沼†
09/20
056 - Lucky Bag（★5）
- DP復元
- 見る行ずれてて少し沼
058 - Original Calculator（★4）
- 周期性
- IQ3で雰囲気コーディングをしてしまい沼
09/21
060 - Chimera（★5）
- 最長部分増加列(LIS)
- $A_i$ を山にしたときの両側LISを求め $P_i + Q_i - 1$
063 - Monochromatic Subgrid（★4）
- "変な制約" に着目できなかった
09/27
066 - Various Arrays（★5）
- $E[X + Y] = E[X] + E[Y]$ 確かに.
- 解説では $\mathcal{O}(N^2 \cdot \max_i({L_i, R_i})^2)$ で解いているが範囲内のある数より小さい数の個数は $\mathcal{O}(1)$ で求められるので $\mathcal{O}(N^2 \cdot \max_i(R_i - L_i))$ になりそう?.
070 - Plant Planning（★4）
10/07
072 - Loop Railway Plan（★4）
073 - We Need Both a and b（★5）
10/11
081 - Friendly Group（★5）
085 - Multiplication 085（★4）
感想
殆ど解法思いつかないし普通に難しい. 少し時間を置いてから2週目に取り組みたい.