NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

競技プログラミング (問題解説)

Google Code Jam 2020 Qualification Round - ESAb ATAd

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

Typical DP Contest J - ボール

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

Typical DP Contest I - イウィ

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

Typical DP Contest H - ナップザック

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

AtCoder Regular Contest 023 D - GCD区間

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

キーエンス プログラミング コンテスト 2020 D - Swap and Flip

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

パナソニックプログラミングコンテスト E - Three Substrings

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

AtCoder Beginner Contest 158 F - Removing Robots

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

yukicoder No.1001 注文の多い順列

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

Codeforces Round #620 (Div. 2) E - 1-Trees and Queries

問題: 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$ の間に辺を追加…

AtCoder Beginner Contest 156 F - Modularness

問題: 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_…

AtCoder Beginner Contest 155 D - Pairs

問題: 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$ 番目に小さい値を求めよ。 解法概…

Educational Codeforces Round 80 E. Messenger Simulator

問題: 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)$ が与えられる. 順列 $…

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君

問題文: 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)$ について, …

Educational Codeforces Round 11 F. Bear and Bowling 4

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

AtCoder Regular Contest 051 D - 長方形

問題文: 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…

AtCoder Beginner Contest 147 F - Sum Difference

問題文: 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 $ がある (…

Codeforces Round #605 Div. 3 F. Two Bracket Sequences

問題: 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 …

Codeforces Round #605 Div. 3 E. Nearest Opposite Parity

問題: 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) $ がある. この数列を使って,ある要素から別の要…

AtCoder Grand Contest 039 C - Division by Two with Something

問題文: 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 あり) に対し次の操作を繰り…

Educational Codeforces Round 77 (Rated for Div. 2) E. Tournament

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

ICPC国内予選 2016 D - ダルマ落とし

問題文 問題概要 n$( n \leq 300)$ 個のブロックが重なったダルマ落としがある. i 番目のブロックの重さは $w_i ( w_i \leq 1000)$ である. このブロックを2個ずつ叩き出して (1個だけ叩き出す,3個以上同時に叩き出すことはできない) ,できるだけ多くの…

第二回全国統一プログラミング王決定戦予選 E - Non-triangular Triplets

問題文: E - Non-triangular Triplets Writer 解説: https://img.atcoder.jp/nikkei2019-2-qual/editorial.pdf 問題概要 $ 3N (N \leq 10^5)$ 個の整数 $ K, K+1, \cdots, K+3N-2, K+3N-1 (K \leq 10^9)$ から,$ N$個の三つ組$ (a_1, b_1, c_1), \cdots, (a…

Codeforces Round #598 Div. 3 F. Equalizing Two Strings

問題: https://codeforces.com/contest/1256/problem/F 公式解説: https://codeforces.com/blog/entry/71184 問題概要 長さ $n (\leq 2 \times 10^5) $ の文字列 $s, t $ がある. $s, t $ に対し,ある長さ $\mathit{len} $ を1つ決めて,以下の操作を任意…

yukicoder No.916 Encounter On A Tree

問題文: No.916 Encounter On A Tree - yukicoder 公式解説: https://yukicoder.me/problems/no/916/editorial 問題概要 深さ $d (\leq 20)$ (ただし頂点の深さを 1 とする) の完全二分木の頂点に,1から$2^{d-1}-1 $ までの整数値を書いていく.次の条件を…

Codeforces Round #595 Div. 3 F. Maximum Weight Subset

問題: https://codeforces.com/contest/1249/problem/F 公式解説: https://codeforces.com/blog/entry/70779 問題概要 $n (\leq 200)$ 頂点の木があり,$i$ 番目の頂点の重みは$a_i (\leq 10^5)$ である. この木の頂点の集合で,含まれるすべての頂点対間の…

Codeforces Round #593 Div. 2 D. Alice and the Doll

問題: https://codeforces.com/contest/1236/problem/D 公式解説: https://codeforces.com/blog/entry/70654 問題概要 $n \times m (n, m \leq 10^9)$ のグリッドのうち k マスに障害物が置かれている. 障害物の位置はそれぞれ $(x_i, y_i)$ である. 次の…

Educational Codeforces Round 74 E. Keyboard Purchase

問題: https://codeforces.com/contest/1238/problem/E 問題概要 小文字のアルファベットのうち最初の m 文字のみ (例えば$m = 3$ なら a と b と c のみ) からなり$\left| s \right| \leq 10^5$ を満たす文字列 s が与えられる. ここで,小文字のアルファ…

Codeforces Round #589 Div. 2 E. Another Filling the Grid

問題: https://codeforces.com/contest/1228/problem/E 公式解説: https://codeforces.com/blog/entry/70162 問題概要 $n \times n$ のグリッドの各マスに,1 以上 $k ( \leq {10}^9 )$以下の整数値を書いていく.すべての行の最小値が 1 かつすべての列の最…

AtCoder Beginner Contest 142 F - Pure

問題文: F - Pure Writer 解説: https://img.atcoder.jp/abc142/editorial.pdf 問題概要 $ N (\leq 1000)$ 頂点 $ M (\leq 2000)$ 辺の有向グラフG が与えられる. すべての頂点の入次数が 1 ,出次数が 1 となるような G の部分誘導グラフを 1 つ答えよ.た…