https://www.acmicpc.net/problem/16041 $N$ 頂点 $M $ 辺のグラフ $G$ が与えられる。 頂点の部分集合 $S$ であって以下の条件を満たすものを $\mod 10^9+7$ で求めよ。 $S$ から誘導される部分グラフは完全グラフである。 頂点全体の集合を $V$ としたとき…

https://www.acmicpc.net/problem/12825 以下の条件を満たす $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ を 312-avoid と呼びます。 $1 \le i < j < k \le N$ を満たす全ての整数組 $(i,j,k)$ について、 $P_j < P_k < P_i$ となることがない。 312-av…

https://www.acmicpc.net/problem/28263 以下の条件を全て満たす長さ $11$ の整数列 $p_1,p_2,\dots,p_{11}$ を一組見つけよ。 $p_i$ は $10^7$ 以上 $10^8$ 未満の素数 $p_i < p_{i+1}$ ( $1 \le i \le 10$ ) $N = p_1 \times p_2 \times \dots \times p_{1…

Problem - H - Codeforces (だいぶ換言した) 問題概要 関数 $f(A)$ は数列 $A=(A_0,A_1,\dots,A_{|A|-1})$ を引数に取り、未知のパラメータ $p,m $ を用いて以下の通りに定義される。 $\displaystyle f(A) = \sum^{|A|-1}_{k=0} A_k \times p^k \mod m $ 以…

Tandem Repeats 長さ $L$ ( $L \le 10^5$ ) の A,G,T,C からなる文字列 $S$ が与えられる。 この文字列のうち連続する $2k$ 文字の連続部分列であって、同じ長さ $k$ の文字列が $2$ 度繰り返されているものの数を数えよ。 (文字種の制限は使わないので、任…

誤った成功体験 A - Leveling with a Dump Truck 初手 : 「足りない」「余ってる」どちらにせよ、全マスを 2 回巡れば全マス 0 にはできるので、これを実装。マスの高さは過不足を調整できるだけ調整。 S字を描くように巡って 260 、渦を描くように巡って 38…

Problem - E - Codeforces $xy$ 平面上の $N$ 点が与えられ、点 $i$ は $(x_i,y_i)$ にある。このとき、異なる $3$ 点は同一線上にない。 以下の通り $f(k)$ を定義する。 まず、点 $k$ を除いた $N-1$ 点の中から $4$ 点 $A,B,C,D$ を選択する。 このとき、…

https://www.acmicpc.net/problem/13323 https://www.acmicpc.net/problem/13324 [BalticOI 2004] Sequence 数字序列 - 洛谷 長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられる。 狭義単調増加整数列である $B$ であって、 $\displaystyle \sum_{i=1}…

この世で最も愚かなレート遷移 AtCoder Regular Contest 174 - AtCoder ARCの単独Writerができたので、くう疲みたいな怪文章をこの世にひとつ増やしたいと思います。 コンテスト観戦総括 Aはかなり素直なARC-Aなので、2080AC出て安心。Bは予想以上に通された…

https://kenkoooo.com/atcoder#/contest/show/4f518dfd-5208-4ed6-b193-d3cfb60f8ab0 1. C - Add Mod Operations (ばちゃ中2問目, 2500diff, 自力AC) とりあえず $(A+x)\%y$ という操作を観察する。 気付き1: 適当に操作をかけても $A_i-A_{i+1}$ の値は変え…

サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e 1-6問目はこちら : 自戒ばちゃ(1-6問目) - physics0523's 精進ログ 7-12問目はこちら : …

サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e 1-6問目はこちら : 自戒ばちゃ(1-6問目) - physics0523's 精進ログ 7. D - -1+2-1 (ばち…

サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e 1. B - Insert 1, 2, 3, ... (ばちゃ中1問目, 1663diff, 自力AC) 本番でめちゃくちゃ詰…

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$ …

Problem - C - Codeforces 問題概要 $ n $ 頂点 $ m $ 辺の単純無向連結グラフが与えられる。 このグラフを $3$ 頂点 $2$ 辺のパスに分解できるか判定し、可能なら分解の一例を出力せよ。 $1 \le n,m \le 10^5$ まず $m\%2 = 1$ なら当然無理。こんな判定問…

Problem - B - Codeforces この手の問題にどうしても慣れることが出来ないのでメモ。 問題概要 非負整数 $n$ に対して関数 $f(n)$ を以下のように定義する。 $f(0) = 0$ $n$ 以下の最大の立方数を $c$ としたとき、 $f(n)=f(n-c)+1$ 簡単には、 $ f(n)= $ 「…

この記事は、 (2つめ)ゲキ！チュウマイ Advent Calendar 2022 - Adventar の $2$ 日目の記事です。 はじめに: この記事は全国対戦でのトップ率がおおよそ $50\%$ までの方を対象としています。圧倒的な実力で相手を捻じ伏せることが高確率で可能な方にはこの…

Problem - F - Codeforces 問題概要 $N$ 頂点 $ M $ 辺の単純連結グラフが与えられるので、以下の問題のうちどちらかを解け。 1. ちょうど $\left \lceil \sqrt{n} \right \rceil$ 頂点の独立集合を見つけよ。 2. 長さ $\left \lceil \sqrt{n} \right \rceil…

F - Reflection 私はこの問題を実験で刺し切りました。すみません。 事前情報として、この問題に挑んでいる話を通話で聞いて「互除法っぽい問題だな」ということは他の方から聞いてから取り掛かったので、それを参考にして解き(?)進めたということは書いてお…

Problem - F - Codeforces 問題概要 整数 $N$ が与えられるので、以下の条件を満たす $(1,2,\dots,N)$ の順列 $P$ があるかどうかそれぞれ判定し、あれば $1$ つ構築してください。 A. 全ての整数 $1 \le i \le N$ について、 $P_i \neq i$ かつ $(P_i \& i)…