問題 https://atcoder.jp/contests/abc214/tasks/abc214_f 略説 部分列dp 同じ文字列ならばindex列が辞書順最小になるように選択していくことで重複を回避する nxt[i][j] := i以降で最初に出現する文字jのindex dp[i] := i文字目までの文字列の種類数 (i文字…

問題 https://atcoder.jp/contests/abc214/tasks/abc214_e 略説 ボールをLについて昇順に見ていき、現時点で箱に入れられるボールをRについての昇順に入れていく ACコード #include <bits/stdc++.h> using namespace std; int T; int main() { cin >> T; while (T--) { int </bits/stdc++.h>…

問題 https://atcoder.jp/contests/abc213/tasks/abc213_f 略説 Sの接尾辞配列で考える(あとで帳尻を合わせる) sa := suffix_array(S) (O(N)で計算可能) lcp := f(sa[i], sa[i+1]) (O(N)で計算可能) f(l,r) = min(lcp[l, r)) g(l, r) := min(lcp[l, r)) (表…

問題 https://atcoder.jp/contests/abc213/tasks/abc213_e 略説 パンチを行うのは必要になったタイミングでよい あるマスから上下左右の移動可能なマスに重み0の辺、パンチを行うことで進めるようになるマスに重み1の辺を貼り、最短経路を求める(01BFS) 計算…

問題 https://atcoder.jp/contests/abc212/tasks/abc212_f 略説 高橋君の時刻0から時刻Zまでの行動は一意に定まる "高橋君がk番目に乗ったバスを乗り終わった時刻t