問題ページ 解法 あみだくじでi番目の縦棒がどこにたどりつくのかはO(m)で求められる。v[i]=iで初期化し縦棒a[i]とa[i]+1をつなぐ

問題ページ 解法 DPをしろという制約と雰囲気があるのでDPをする。dp[i][j]=(i番目を最後に切って最短がjのとき、最小の最大ピースの長

問題ページ 解法 2次元グリッドをグラフに直して考えてみる。問題の条件的にこのグラフに閉路が存在することはなくDAGになっている。したがって閉路

問題ページ 解法 $a[i]$が中央値となる区間の数を求めて$m=\text{floor}(n*(n+1)/4)+1$番目の数を求める方針で考え