前提 あるハイカーに注目する。標高の遷移をv_0, v_1, ... , v_L-1とし、保有エネルギーの遷移をe_0, e_1, ... , e_L-1とする。 e_i+1 = e_i - (v_i+1 - v_i) e_i+1 + v_i+1 = e_i + v_i つまり標高と保有エネルギーの和は常に一定。これをPとおく。 P = e_i…

問題 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

問題 https://atcoder.jp/contests/abc212/tasks/abc212_e 略説 dp[i][j] := i日目に都市jにいる場合の数 dp[i+1][j] = sum(dp[i]) - dp[i][k:=都市kと都市jは結ばれていない] iについての各ループにおいて、kの総数は高々2M+Nとなる。 よって計算量は O(K(N…