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

Problem - E - Codeforces 教育的で面白い いい問題 Submission #149746040 - Codeforces

Problem - C - Codeforces 2300diffにしては難しくないか? けっこう苦労したのでメモ。 数列 $A=(A_1,A_2,...,A_N)$ に対して以下の操作を $0$ 度以上何度か行うことを考える。 $i=A_i$ なる整数 $i$ を選び、 $A_i$ を数列から消す。空いた添え字は詰められ…

Problem - F - Codeforces 整数 $n$ が与えられる。以下の問題を解け。 各要素が $1 \le a_i \le n$ であり、かつ要素に重複が無い数列 $a$ を考える。 このとき、この数列 $a$ はある整数 $ m $ について $\displaystyle \prod_{i=1}^{|a|}(a_i!) = m^2$ を…

Problem - B - Codeforces この手の問題死ぬほど苦手。1800diffなのに分からなかった… 問題概要 石を積んだ山が $N$ 個ある。 $i$ 個目の山に石が $A_i$ 個積んである。 プレイヤーは交互に山を $1$ つ選んでそこから石を $1$ つ取るが、前のプレイヤーと同…

Problem - F2 - Codeforces ちょっと思いつきにくそうなのでメモ。 長さ $N$ の数列 $A$ が与えられる。 $A$ の(連続でなくともよい)狭義単調増加列について、要素の XOR 和としてありうるものを列挙せよ。 $1 \le N \le 10^6$ $0 \le A_i \le 5000$ 真っ先…

Problem - H - Codeforces ぐろふぉのボス問自力討伐は流石にめちゃくちゃ嬉しいぜ、奥さん… 問題概要 以下のように生成されたサイズ $n$ の整数集合 $A$ がある。 $1$ 以上 $c$ 以下の全ての整数 $x$ について、 $x$ を確率 $0.5$ で含む。この決定はそれぞ…

Problem - D - Codeforces 問題概要 以下の方法で、全ての要素が $1$ 以上 $10^6$ 以下の整数である $k \times m $ 行列 $A$ を作成する。(ただし、添え字は 0-indexed とする) 全ての $0 \le j < m $ について、 $A$ の $j$ 列目を、全ての項が $1$ 以上 $1…