問題: E - ひも 問題概要 $N ( \leq 10^5)$ 個の区別できるノードがある。 $i (1 \leq i \leq N)$ 番目のノードの次数が $a_i (1 \leq a_i \leq 3) $であり、すべてのノードが直接または間接的に辺で繋がれており、かつ辺が全体で $N-1$ 本となるようなグラ…

問題: D - L 解説: 公式解説 問題概要 二次元の平面上の点 $(0, 0), (0, 1), (1, 0)$ に石が一つずつ並んでいる。このような石の置き方をくの字であると呼ぶ (詳細な条件は問題文参照) 。 3つの石の中から1つ選んで好きな位置に移動させる操作を好きだけ行う…

問題: C - Fair Elevator 解説: 公式解説 問題概要 $1$ 以上 $2N$ 以下の整数からなる数列 $A = A_1, A_2, \dots A_N$ および $B = B_1, B_2, \dots B_N$ が与えられる。ただし $A$, $B$ は一部の値が欠損している場合がある。$A$, $B$ の欠損した値を適切に…

問題: F - Intervals on Tree 公式解説: 解説 pdf 問題概要 $N (\leq 2 \times 10^5)$ 頂点の無向木がある。整数 $1 \leq L \leq R \leq N$ について，関数 $f(L, R)$ を次のように定義する。 $S$ を$L$ 以上 $R$ 以下の番号のついた頂点からなる集合とする…

問題: Problem - E - Codeforces 公式解説: Editorial — Codeforces Round #651 - Codeforces 問題概要 長さ $n (1 \leq n \leq 10^6)$ の 01 文字列 $s. t$ が与えられる。この文字列 $s$ に次の操作を繰り返し， $t$ と等しくする。 操作: $s$ の部分文字…

問題: B - Joker 公式解説: 解説 pdf 問題概要 $N \times N$ の正方形の座席を持つ劇場に $N^2$ 人の客が座っている。客が席を立つ順番が与えられるので，以下を求めよ。 客が自席から外周へと出るまでに通る，人の座っている座席の数の，すべての客について…

問題: F - . (Single Dot) 公式解説: 解説 pdf 問題概要 無限に広がる平面上に $N (\leq 1000)$ 本の縦線と $M (\leq 1000)$ 本の横線がある。 縦線と横線の端点の座標の値は$-10^9$ 以上 $10^9$ 以下の範囲に収まる。 座標 $(0, 0)$ から動くことのできる範…

問題: Problem - E - Codeforces 公式解説: Codeforces Round #641 Editorial - Codeforces 問題概要 $n \times m (1 \leq n, \mathit{m} \leq 1000)$ の行列 $A$ が与えられる。$i$ 行 $j$ 列の要素は $a_{i, j}$ であり，0 なら白，1 なら黒である。 この…

問題: O - Variable Spanning Trees 問題概要 $N ( \leq 10^5)$ 頂点 $M (\leq 10^5)$ 辺の無向グラフが与えられる。$i$ 番目の辺は頂点 $a_i, b_i$ を結び，$c_i$ の重みを持つ。 各辺について，その辺を含む最小の重みの全域木を求め，その重みを出力せよ…

問題: ESAb ATAd - Code Jam 問題概要 '0' と'1' のみからなる長さ$B$ の文字列が与えられる (制約は本節最後を参照)。この文字列に対して，次のクエリを 150 回まで投げることができる。 文字列の $i$ 文字目は '0' と'1' のどちら？ 1回目，11回目，21回目…

問題: J - ボール 問題概要 $N (\leq 16)$ 個の障害物が $x$ 軸上に置かれていて，$i$ 番目の障害物の座標は $x_i (0 \leq x_i \leq 15)$ である。 すぬけ君がボールを座標 $x$ めがけて投げると，$x-1$，$x$，$x+1$ にそれぞれ $\frac{1}{3}$ の確率で飛ん…

問題: I - イウィ 問題概要 i と w からなる文字列 $s (|s| \leq 300)$ から iwi を削除し残った文字列を連結する操作を繰り返す。 最大何回操作できるか答えよ。 解法概要 $\mathit{dp}_{i, j} := i$ 文字目 (ソースコードでは 0-indexed) から始まる j 文…

問題: H - ナップザック 問題概要 $N (\leq 100)$ 個の物があり，$i$ 番目の物の重さ，価値，色は $ w_i, v_i, c_i$ である。重さ $W$，かつ $C$ 色までナップザックに詰めることができるとき，ナップザックに詰められた物の価値の和の最大値を求めよ。 解法…

問題: D - GCD区間 公式解説: 解説 スライド 問題概要 長さ $n (\leq 10^5)$ の数列 $a_1, a_2 \dots, a_N (1 \leq a_i \leq 10^9)$ がある。この数列に対して，次のクエリが $m (\leq 10^5)$ 回与えられる。それぞれのクエリの答えを出力せよ。 最大公約数…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 $N ( \leq 18)$ 枚のカードがあり，左から $i$ 枚目のカードは表に $A_i (\leq 100)$，裏に$B_i (\leq 100)$ が書いてある。次の操作のみを行い，カードが左から右に…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 次の同じ方法で得られた長さ $2000$ 文字以内の文字列 $ a, b, c$ が与えられる。元の文字列 $s$ の長さとしてありえる最小値を求めよ。 文字列 $s$ の空でない部分文…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 数直線上に $N$ 台のロボットが置かれている。$i$ 番目のロボットの初期位置は $X_i$ で，このロボットは起動させると $X_i+D_i$ まで移動する。移動中，$i$ 番目のロ…

問題: No.1001 注文の多い順列 - yukicoder writer 解説: yukicoder 問題概要 $1$ 以上 $N$ 以下の整数の順列 $p_1, p_2, ... p_N$ であって，以下の条件を満たすものの数を $10^9+7$ で割った余りを求めよ。 すべての $i (1 \leq i \leq N)$ について以下を…

問題: Problem - E - Codeforces 公式解説: Codeforces Round #620 (Div. 2) Editorial - Codeforces 問題概要 $n (3 \leq n \leq 10^5)$ 頂点の無向木が与えられる。次のクエリに $q (1 \leq n \leq 10^5)$ 回答えよ。 頂点 $x$ と頂点 $y$ の間に辺を追加…

問題: F - Modularness 公式解説: 解説 pdf 問題概要 長さ $k$ の数列 $d_0, d_1, \dots, d_{k- 1} $ について，次のクエリを $q$ 回処理せよ。 3つの整数 $ n, x, m $ が与えられる。長さ $n$ の数列 $a_0, a_1, \dots, d_{n- 1}$ を， $a_0 = x$ $a_j = a_…

問題: D - Pairs 公式解説: 解説 pdf 問題概要 $N (2 \leq N \leq 2 \times 10^5)$ 個の整数 $A_1, A_2, \cdots, A_N (-10^9 \leq A_i \leq 10^9)$ が与えられる． ここから2つの整数を選んでペアにして積をとったとき，$K$ 番目に小さい値を求めよ。 解法概…

問題: Problem - E - Codeforces 公式解説: Educational Codeforces Round 80 Editorial - Codeforces 問題概要 整数 $n, \mathit{m} (1 \leq n, \mathit{m} \leq 3 \times 10^5$ と数列 $a_1, a_2, \cdots, a_m (1 \leq a_i \leq n)$ が与えられる． 順列 $…

問題文: C - スペースエクスプローラー高橋君 公式解説: https://img.atcoder.jp/colopl2018-final/editorial.pdf 問題概要 長さ $N \leq 10^5$ の整数列 $a_1, a_2, \cdots, a_N (a_i \leq 10^{12}) $ が与えられる． 各 $i (1 \leq i \leq N)$ について， …

問題: https://codeforces.com/contest/660/problem/F 公式解説: https://codeforces.com/blog/entry/44259 問題概要 えびちゃんのお気に入り問題の一つなので人々に解いてみてほしいhttps://t.co/mflgdhqEVH pic.twitter.com/aVVI23MM3R — えびちゃん (@rsk…

問題文: D - 長方形 公式解説: http://arc051.contest.atcoder.jp/data/arc/051/editorial.pdf 問題概要 長さ $W (\leq 2000)$ の整数列 $ a_1, a_2, \cdots, a_W (a_i \leq 10^5)$ と，長さ $ H (\leq 2000)$ の整数列 $b_1, b_2, \cdots, b_H (b_i \leq 10…

問題文: https://atcoder.jp/contests/abc142/tasks/abc147_f 公式解説: https://img.atcoder.jp/abc147/editorial.pdf 問題概要 長さ $ N (\leq 2 \times 10^5)$ の整数列 $ A_1 = X, A_2 = X+D, \cdots, A_{N-1} = X+(N-2)D, A_{N} = X+(N-1)D $ がある (…

問題: https://codeforces.com/contest/1272/problem/F 公式解説: https://codeforces.com/blog/entry/72132 問題概要 2つの括弧列 $ s,t (\left| s \right|, \left| t \right| \leq 200) $ が与えられる． $ s, t $ の両方を部分文字列としてもつ regular …

問題: https://codeforces.com/contest/1272/problem/E 公式解説: https://codeforces.com/blog/entry/72132 問題概要 長さ $n (\leq 2 \times 10^5) $ の数列 $a_1, a_2, \cdots, a_n (1 \leq a_i \leq n) $ がある． この数列を使って，ある要素から別の要…

問題文: C - Division by Two with Something Writer 解説: https://img.atcoder.jp/agc039/editorial.pdf 問題概要 整数 $ N (\leq 2 \times 10^5)$，$ X (\lt 2^N)$ が与えられる．0以上X 以下のすべての整数 k (leading-zero あり) に対し次の操作を繰り…

問題 https://codeforces.com/contest/1260/problem/E 公式解説 https://codeforces.com/blog/entry/71805 問題概要 $n (n \geq 2)$, $n$ は2のべき乗) 人のボクサーがトーナメントで戦い，優勝者を決めようとしている． 参加するボクサーは数列 $a_0, a_1, …