ルール
- 毎週月, 火で友人と★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は から までの最短, からと からやればok
- 木の直径も からBFS, 最遠からBFSすればよい
021 - Come Back in One Piece（★5）
強連結成分分解(SCC). 知らなかった.
- 各頂点を始点としてDFSして帰りがけ順に番号振る
- 辺の向きを逆にしたグラフに対して, 番号大きい順にDFS
- 逆向き ループ以外をシャットアウト
snippet を作成.
08/17
026 - Independent Set on a Tree（★4）
BFSで隣接頂点は色変える, 多い方から 個選ぶ
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°回転
037 - Don’t Leave the Spice（★5）
- 普通のDP + セグ木で高速化
- -> にする
- RMQに帰着
09/07
039 - Tree Distance（★5）
- 子孫の数を木dp(=DFS) で出す
- 貢献度を求めて総和
- 主客転倒ともいうらしい
09/13
042 - Multiple of 9（★4）
- dp
- 和が =
09/14
043 - Maze Challenge with Lack of Sleep（★4）
- 01-BFS
- Pythonで書いたが間に合わなくてJuliaで書いたがJITコンパイルのオーバーヘッドのせいで間に合わなくてC++で書いた.
051 - Typical Shop（★5）
- 半分全列挙:
- 例外の処理で沼†
09/20
056 - Lucky Bag（★5）
- DP復元
- 見る行ずれてて少し沼
058 - Original Calculator（★4）
- 周期性
- IQ3で雰囲気コーディングをしてしまい沼
09/21
060 - Chimera（★5）
- 最長部分増加列(LIS)
- を山にしたときの両側LISを求め
063 - Monochromatic Subgrid（★4）
- “変な制約” に着目できなかった
09/27
066 - Various Arrays（★5）
- 確かに.
- 解説では で解いているが範囲内のある数より小さい数の個数は で求められるので になりそう?.
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週目に取り組みたい.