ABC231F まず，求める答えを式に直してみる． \(i,j \in N\) であって \(a_{i} \geq a_{j}\) かつ \(b_{j} \geq b_{i}\) となる 組\(\,(i,j)\) の個数を数える． \(b\) はマイナスを掛けて順序を反転させると， \(a\) と同じ形になって楽． 平面走査で数える…

数え上げの順序を変える． \(a_{l} \neq a_{r}\) かつ \(l < r\) となる \(l,r \in N\) に対して，これを含む連続した区間を数える． それは， \(min(l+1, N-r)\) と一致する． minを外すために，大小で場合分けすることと， \(l,r\) のうち \(l\) を全探索…

ABC272E \(A\) はサイズ \(N\) のリスト． このとき， \(mex(A) \leq N\) となる． つまり，答えの候補が小さい． 実際 \(A\) の元 \(e\) のうち， \(e < 0, \ N < e\) は取り除いても mex は変わらない． また， 調和級数の様な見積もりで \(O(N log N)\) …

ABC223E \(X \times Y\) の長方形 \(R\) を3分割して，それぞれの面積が \(A,B,C\) 以上にできるかを考える． 切り方は， \(R\) の辺と並行になる直線だけで余さそう． 斜めに長方形を配置するのは無駄が多そうだから． 切り方の候補は， (横,縦), (横,横) …

ABC283E ある行 \(a_{i}\) に孤立点が無いという判定を考える． これは，前後の行の影響を受け，それ以外の行は影響を受けない． よって，2行分の情報が必要なので，それを覚えながらDP. 注意は， \(a_{i}\) の時点では孤立点がなくても， \(a_{i+1}\) 次第…

ABC246E 状態を持たせたBFS. (そのマスに辿り着いた方向) \(\in 4\) を記録しながら BFS. 実装安全に行くなら，ルール通りに遷移する． つまり，一気に何マスも移動できる様に実装する． これは while 文で良い． TLE には注意．枝狩をするには，そのマスに…

ABC248E 幾何の問題． \(O(N^3)\) は間に合うので， 直線すべてを全探探索して，各点に関して直線の上に乗っているかを数えればよい． 実装\(\,(x_{0}, y_{0}), (x_{1},y_{1})\) を通る直線の式は $$ (y_{0} - y_{1}) x - (x_{0} - x_{1}) y + (y_{1}x_{0} -…

ABC221E \(l < r\) とする． \(a_{l} \leq a_{r}\) を満たしていれば，その間の項は自由に選べるので， 答えは \begin{align} \displaystyle \sum_{ l, r \in N \times N \\ l < r \\ a_{l} \leq a_{r} } 2^{r-1-l}. \end{align} これを \(r,l\) の項に分解…

ABC255E \(a_{0}\) を決めれば， \(a\) の残りは一意に決まる． \((i,j) \in N \times M\) に対して， \(a_{i} = x_{j}\) となる \(a_{0}\) の条件を， \(x, s\) を用いて表せばよい． \(a_{0}\) を固定したときに， よい\((i,j\) の組に印をつけていく． 印…

PAST007E 問題文から， \((3^{k}+1)\cdot 3^{30-k} = n\) を満たす \(k\) を求めればよい． つまり， \(3^{30-k} = n - 3^{30}\) を満たす \(k\) を求める． \(i := 30-k\) とおいて， \(k \in [1,30]\) のとき \(i \in [0,30)\) ． これは全探索可能． 使っ…

ARC141A \(f_{x,a}\) := \(x\) を \(a\) 個並べた数 とする． \(N\) が \(k\) 桁， \(y\) を \(N\) の先頭 \(p\) 桁， \(p \geq 1\) とする． 基本的に答えは $$ max_{k \equiv 0 \ mod \ p} (f_{y, k/p}, f_{y-1, k/p}) \ \cdots \ (0). $$ しかし，これだ…

PAST008G Binary search で \(K\)-th を求める． \(P(x) := \) ((\(x\) 以下の個数) \(\geq K\) ) とすると， \(P\) は \(x\) に対して単調． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,k; ci…

PAST011E \(0\)-indexed，半開区間で考える． 操作を一つの単位として，ブロック毎に考える． 数列の値も \(1\) 引いて考える． \(i\)番目のブロックは \(i, i-1, i-2, \cdots , 0, 1, 2, \cdots, i-1, i\) の \(2i+1\) 個． \(i\) ブロックの \(x\) 番目は …

PAST011I \(H,W \leq 50\) と小さい． 盤面は，(人の座標，荷物の座標) さえ分かっていれば，後は何とかなる． 実装(人の座標，荷物の座標)を持ちながらBFS. グラフの頂点の個数は \(O(\ (H \times W)^{2}\ )\), 辺の個数は，頂点の4倍． よって，合計で \(O…

PAST009I 階は \(N \leq 10^{18}\)個と多く，エレベーターは \(M \leq 10^{5}\) 個と少ないので， エレベーターから考える． 最短経路問題と同じになる． エレベーターの始点，終点になっている階と， \(1,N\) 階のみ頂点としたグラフを考える． 階を小さい…

ABC289 新しく作ったグラフ上でBFS.もとのグラフを \(G = (V,E),\ V = N\) とする． 二人いるので，それらの居る場所をペアで管理してBFS. そのために，拡張したグラフ \(\hat{G} = ( \hat{V}, \hat{E}) \) を作る． \(\hat{V} = V \times V\)． 二人が(\(cx…

ABC289D 部分和DP. 移動出来ない場合に注意． 実装するときには，使ってない条件がないか確認しよう． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m, k, q; cin >> n; vll a(n); rep(i,n) { c…

ABC289 Bit 全探索を実装するだけ． 問題文通りに実装すればよい． 任意，あるを翻訳できれば大丈夫． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m, k, q; cin >> n >> m; vvll a(m); rep(i,…

ABC289B 綺麗な方法が分からなかったから，問題文にある通りグラフで考えた． DFSして，連結成分ごとに，辿り着いたvertices を手に入れて， 大きい順に出力． 公式解説公式解説を見て，while 文で実装． 使っている記号，マクロ等 "https://ecsmtlir.hatena…

PAST009H LCSと同様． \(s,t\) の最後の文字 \(s_{i}, t_{j}\) を使うかどうかで場合分け． \(s_{[0,i)}, t_{[0,j)}\) に対する答えを \(dp_{i,j}\) とおく． \(s_{i} \neq t_{j}\) のとき：使った方が良い． 言い換えると，使う最適な選び方が存在する． こ…

PAST009J類題:ABC199C - IPFL 補助的な盤面 回転や反転を愚直に実装すると， \(O(N^2)\) かかるので， クエリごとに計算しては間に合わない． そこで，回転や反転をどの程度行ったを記録しておいて， 盤面自体は回転させずに保持する．つまり， (実際の盤面)…

PAST009K ガソリンスタンドが \(K \leq min(N-1,20)\) と少ないので，そこから考える． ガソリンスタンドを経由するせいで，逆に簡単． ガソリンスタンド \(x\) を一つ固定してこれを経由する \(s \rightarrow t\) の最短距離は， \(dis[x][s] + dis[x][t]\)…

PAST007L 参考にした実装 https://blog.hamayanhamayan.com/entry/2021/07/24/203450 全ての \(j\) を求めるとあるが，まずは \(1\) 個求める． 特に，最小の \(j_{0}\) を求められれば， \(j_{0}+1\) 以降の中から 最小の \(j_{1}\) を求めることができる．…

PAST007J 有向グラフのサイクル検出トポロジカルソートと同じ．DFS,BFSでも可能．DFSによる実装頂点 \(i\) に対して， \(val_{i}\) を 0 : 訪れてない 1 : 訪れたが計算途中 2 : 訪れて計算が終わった として保持する． \(val_{i} = 1\) の状態で再び訪れた…

PAST007G 3冪の和で表すので，3進数の形から考える． 今回は，同じ3冪は使えないので， $$2 * 3^{i} = 3^{i+1} - 3^{i}$$ と書き直せばよい． 繰り上がりの様な計算が起きるので，下の桁から計算を確定させていく．メモこの問題は， 平衡3進法という問題らし…

PAST007I 複素数回転と平行移動のみなので，複素数による実装が簡単．実装右目と左目を区別することに注意． よって，平行移動と回転は一意に定まる．操作後の点たちを，平行移動 -> 回転 の順で求める． 平行移動を忘れずに． 使っている記号，マクロ等 "ht…

PAST007K まず min cost, 次に max scenery. また，コストは全て正． 答えは，min cost となるパス \(1 \rightarrow N\) 全体から max scenery をとる．これは Dijikstra を (cost, -scenery ) で昇順ソートの priority_queue で行えば良い． 使っている記号…

PAST008H LCAの前計算で高速化可能だが， 頂点毎にDFSをやりなおしても \( O(N^2) \) で間に合う．Tree においては，根からDFSしたときの距離が，根からの最短距離になる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131…

PAST008J 反転するペアは独立しているのがポイント． \(mod 2\) で区間和を求めればよい． これは segtree で実装できる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" ll op(ll a, ll b){ return a+b; } ll e() {…

ABC288D とりあえず，クエリは無視して考える.まず \(a_{[i,i+k)}\) の区間全体に \(-x\) を足す．次に \(a_{[i+1,i+1+k)}\) の区間全体に \(x\) を足す．すると，真ん中は変化せず， \(a_{i}\)と \(a_{i+k}\)だけ変化する．とくに， \(x = a_{i}\) として計…