#ABC370 3完して椅子ぬくぬく
A B C よし
D これ何かの典型なんですか...?行(列)ごとに空間の左(上)端と右(下)端を管理(例:v[1] = {1, 2, 4, 6}なら1行目で壊れている列は1, 4, 5のみ)する方法しか思いつかないが,insertの時間計算量が不安(しかも書けない)
#ABC369 5完1ペナ
A B よし
C dp[i]を「長さ2以上,末尾がA_{i+1}の等差数列の個数」としてdp
D dp[i][j = 0, 1]を「i体目まで(j ? 奇数 : 偶数)体倒しているときの最大経験値」としてdp
E ワ―シャルフロイド後,橋の通り方をk!*(2^k)通り全探索
F 行を遅延伝播セグ木とみて区間加算・区間最大値取得?
最初はMで割った余りごとにiを格納してlower_bound等で数えるO(N logN)(たぶん)の解法で提出したがTLE。その後、LISを求めるように余りごとに数えていって(平面走査?)O(N)でAC。
E 置換のサイクル分解かと思いきや単射じゃない..。functional graphのサイクルを見つければいいのかな?
#ABC369 5完1ペナ
A B よし
C dp[i]を「長さ2以上,末尾がA_{i+1}の等差数列の個数」としてdp
D dp[i][j = 0, 1]を「i体目まで(j ? 奇数 : 偶数)体倒しているときの最大経験値」としてdp
E ワ―シャルフロイド後,橋の通り方をk!*(2^k)通り全探索
F 行を遅延伝播セグ木とみて区間加算・区間最大値取得?
最初はMで割った余りごとにiを格納してlower_bound等で数えるO(N logN)(たぶん)の解法で提出したがTLE。その後、LISを求めるように余りごとに数えていって(平面走査?)O(N)でAC。
E 置換のサイクル分解かと思いきや単射じゃない..。functional graphのサイクルを見つければいいのかな?