問題リンク 解説 C1は dp[i][j] := i番目まで見た時、次が+ならj=0 次が-ならj=1 みたいに定義したら解けます。 これの応用で[l, r]の区間で dp[j][k] := lが(+ or -)ではじまり、rが(+ or -)でおわる 見たいな風にするとセグ木にのります 提出コード codefo…

問題リンク 解説と少し違ったので 解説 の場合はサンプルにあります。 以下とします であるので、 です よって となるをみつけたらよく、これはの逆元です。 提出コード yukicoder.me

解説 区間DPです。 dp[l][r]:= [l, r)の部分列の回文の数とすると、 dp[l][r] += dp[l + 1][r] + dp[l][r-1] - dp[l+1][r-1] に加えて、s[l] == s[r-1]なら dp[l][r] += dp[l+1][r-1]+1 です 計算量は 提出コード #include <iostream> #include <string> #include <sstream> #include <stack> #</stack></sstream></string></iostream>…

問題リンク 解説 式変形すると となります。とは互いに素であるので、の素因数をとのどちらかに押し付けます あとは拡大ユークリッド互除法を用いれば、差が1でかつ最小になるようなものを求められます 提出コード atcoder.jp

問題リンク 解説 直接中央値がとなるようなsubstringを数え上げるのは大変です。 ここで とするとを求めるのはBITなどを用いて簡単です 中央値がとなるようなsubstringはとなり求めることができました。 提出コード codeforces.com

問題リンク 解説 最短経路木を列挙してくださいという問題です。 頂点1からBFSなどで各頂点までの最短経路を求めましょう。 ある頂点の親はとなるものに限り、かつこれを満たすならどれでも構わないです。 あとはこのパターンを列挙するだけで、列挙の仕方は…

問題リンク ゆきこにこれの簡単バージョンがある 解説 各経路を考えると大変なので、各辺が合計で何回通るかを考えましょう これは部分木サイズを注目することで、で求めることができます。 あとは通る回数が小さいほうから、小さいを割り当てていけば終わり…

問題リンク こんなド典型がDiv. 2 - Eで出るんですね 解説 交点が1つあるたびに長方形が1つできます。 ということで、これは明らかに平面操作をすればいいのでBITなどを利用して、などを管理して、程度で解けました 縦と横をぶった切ってるケースに注意 提出…

問題リンク 解説 複素平面上で考えると分かりやすいです。 複素平面上では距離の変更も回転も積であらわせます。 本質的にクエリ0とクエリ1は同じです。 クエリ2は各ベクトルの和であるので、言い換えると複素数の和です。 よって、クエリ0とクエリ1は区間積…

問題リンク 解説 クエリ問題であるので、クエリ無しで解くことを考えましょう。 ある値が達成できるかどうかを考えます。 この時,、 としていいです。 そうすると、 のとき のとき とすればいいことに気づきます。 よって、最大値のみ注目すればいいので、が…

問題リンク 解説 まず、移動パターンは4通りしかありません。 かつ < →番目から一番近い以上のところに行く かつ < →番目に一番近い以上のところからくる かつ < →番目から一番近い以下のところに行く かつ < →番目に一番近い以下のところからくる なので、…

解法 問題文を言い換えると、 かつのようなペアが何個あるか数え上げる問題になる。 桁数が同じ数字を考えると、であるので、桁数が異なる場合だけ考えればいい とすると、桁数がと ()のような上記の条件を満たす整数の組み合わせは簡単な算数で求められる。…