Problem - B - Codeforces $N$ 頂点 $ M $ 辺の連結な無向グラフ $G$ が与えられる。 更に、 $1 \le A,B \le N$ かつ $A \neq B$ を満たす整数 $A,B$ も与えられる。 以下の条件を満たす頂点組 $(U,V)$ を数えよ。 $U \neq A$ かつ $U \neq B$ $V \neq A$ か…

Problem - D - Codeforces (CFR507-D1D) に使いました 以下の条件を満たす $f$ を取り扱います。 $f$ は整数値を取る $f(k) \le N/k$ のように制約される ( $n$ 個のものをどうにかして $k$ 個ずつ個包装したい場合など… ) $f$ は(広義)単調減少する $f$ を…

Problem - E - Codeforces 問題概要 V, K, ? からなる文字列 $S$ が与えられる。 ? はワイルドカードである。 以下の条件を満たす $1$ 以上 $|S|$ 以下の整数 $k$ を全て求めよ。 $S$ 中の ? を V, K のどちらかに適切に置き換えたところ、 $S$ は周期 $k$ …

Problem - D - Codeforces 問題概要 整数 $N$ が与えられる。 $N$ 頂点 $0$ 辺のグラフ $G$ を用意する。頂点番号は $1,2,\dots,N$ である。 $\gcd(i,j) \neq 1$ を満たす全ての整数組 $1 \le i < j \le N$ に対し、 $G$ の頂点 $i,j$ 間に長さ $1$ の無向辺…

Problem - B - Codeforces 問題概要 長さ $N$ の $(0,1,\dots,N-1)$ の順列 $P$ (0-indexed) が存在し、隠されている。 $P$ の逆置換を $B$ とする。 以下の質問を高々 $2N$ 回使い、 $P$ を当てよ。 $0 \le i,j < N$ なる整数 $i,j$ を指定し、 $P_i \oplus…

Problem - F - Codeforces 問題概要 長さ $N$ の数列 $A$ が与えられる。 以下の条件を満たす $1,2$ からなる長さ $N$ の数列 $B$ があるか判定し、あるならひとつ構築せよ。 $B_i=1$ なる $i$ を並べた数列を $X$ とする。このとき、 $\gcd(A_{X_1},A_{X_2}…

項目 最大素因数 値 指数表記 備考 $1$ $2$ $2$ $2 \times 10^0$ $2$ $3$ $6$ $6 \times 10^0$ $3$ $5$ $30$ $3 \times 10^1$ $4$ $7$ $210$ $2.1 \times 10^2$ $5$ $11$ $2310$ $2.3 \times 10^3$ $6$ $13$ $30030$ $3.0 \times 10^4$ $7$ $17$ $510510$ $5…

D - Unique Subsequence 問題概要 長さ $N$ の数列 $A$ が与えられるので、(連続でなくともよい)部分列として取り出される方法が一意であるようなものを $\mod 998244353$ で数え上げよ。 $1 \le N \le 2 \times 10^5$ $1 \le A_i \le N$ 最初 $dp[$ 要素 $x…

Problem - E - Codeforces 問題概要 以下の条件を全て満たす長さ $l+1$ の数列を 入力列 と呼ぶ。 先頭の項が $l$ である。 それ以外の項は何でも良い。 入力列の例: (3,1,4,1),(1,100),(5,2,3,52,23,523),(0) 以下の条件を全て満たす数列を マルチテスト列 …

Problem - D - Codeforces Triangle おふざけはこのへんにしておきましょう。 問題概要 平面上の $n$ 点 $(x_i,y_i)$ が与えられる。 この中の $3$ 点を選んで、選んだ点を結んだ三角形の面積を $S$ と出来るか判定し、可能ならそのような三角形をひとつ復元…

Problem - B - Codeforces 詰まって自力で解けなかったのでメモ。 問題概要 $N$ 個の箱があり、箱 $i$ は座標 $i$ に置かれており、そのうち $K$ 個が光っている。 以下の質問を $60$ 回以下することで、光っている箱を ( $K$ 個のうち) $2$ つ当てよ。 $a$ …