torus711 のアレ

主に競技プログラミングの問題について書きます

動的計画法

AtCoder Beginner Contest 187, F : Close Group

問題文 https://atcoder.jp/contests/abc187/tasks/abc187_f 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G = ( V, E )$ がある.このグラフをクリークで被覆するときの最小のクリーク数を求めよ*1. 制約 $1 \leq N \leq 18$ $0 \leq M \leq \frac{ N ( N …

AtCoder Beginner Contest 185, E : Sequence Matching

問題文 https://atcoder.jp/contests/abc185/tasks/abc185_e 問題概要 長さ $N$ の正整数の列 $\{ A_i \}_{ i \in [ 0, N ) }$ と長さ $M $ の正整数の列 $\{ B_i \}_{ i \in [ 0, M ) }$ が与えられる.これらからいくつかの要素を取り除き(,残った要素を…

AtCoder Beginner Contest 184, D : increment of coins

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_d 問題概要 金貨が $A$ 枚,銀貨が $B$ 枚,銅貨が $C$ 枚ある.いずれかの種類のコインが $100$ 枚になるまで以下の試行を繰り返す. コインを一様ランダムに選ぶ 選ばれたコインと同種のコインを …

AtCoder Beginner Contest 183, E : Queen on Grid

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_e 問題概要 高さ $H$ ,幅 $W$ のグリッド状の盤面を考える.セル $( i, j )$ は空白か壁かのいずれかである. この盤面の位置 $( 1, 1 )$ に駒が置かれている.駒は,右,右下,下のいずれかの方向…

AtCoder Regular Contest 107, D : Number of Multisets

問題文 https://atcoder.jp/contests/arc107/tasks/arc107_d 問題概要 正整数 $N, K$ が与えられる.次の条件を満たす,有理数の多重集合 $S$ の総数 $\pmod{ 998{,}244{,}353 }$ で求めよ. $|S| = N$ $\sum_{ x \in S } x = K$ $x \in S$ は $\frac 1 { 2^…

AtCoder Beginner Contest 180, E : Traveling Salesman among Aerial Cities

問題文 https://atcoder.jp/contests/abc180/tasks/abc180_e 問題概要 3 次元空間 $\mathbb R^3$ 上に都市 $1$ から都市 $N$ の $N$ 個の都市がある.都市 $i$ の座標は $( X_i, Y_i, Z_i )$ で与えられる. 都市 $i$ から都市 $j$ に移動するときにかかるコ…

ACL Beginner Contest, D : Flat Subsequence

問題文 https://atcoder.jp/contests/abl/tasks/abl_d 問題概要 数列 $\{ A_i \}$ と正整数 $K$ が与えられる.以下の条件を満たす数列 $B$ の長さとしてあり得る最大値を求めよ. $B$ は $A$ の部分列 (意味のある)任意の $i$ について $| B_i - B_{ i + …

AtCoder Beginner Contest 179, D : Leaping Tak

問題文 https://atcoder.jp/contests/abc179/tasks/abc179_d 問題概要 $X$ 軸上に住むことを考える(原文参照><;).今,$x = 1$ の地点にいて,次の方法で移動することができる. $K$ 個の区間 $[ L_i, R_i ]$ ($0 \leq i \leq K$) が与えられる.この区…

AtCoder Beginner Contest 178, D : Redistribution

問題文 https://atcoder.jp/contests/abc178/tasks/abc178_d 問題概要 正整数 $S$ が与えられる.数列であって,すべての項が $3$ 以上かつ総和が $S$ になるものの個数を $\pmod{ 10^9 + 7 }$ で求めよ. 制約 $1 \leq S \leq 2{,}000$

AtCoder Beginner Contest 178, C : Ubiquity

問題文 https://atcoder.jp/contests/abc178/tasks/abc178_c 問題概要 長さ $N$ の正整数列 $\{ A_i \}$ で,次の条件をすべて満たすものの個数を $\pmod 10^9 + 7$ で求めよ. $0 \leq A_i \leq 9$ $\exists i, A_i = 0$ $\exists i, A_i = 9$ 制約 $1 \leq…

M-SOLUTIONS プロコンオープン 2020, D : Road to Millionaire

問題文 https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_d 問題概要 今,今後 $N$ 日間の株価が分かっていて,$i$ 日目の株価は $A_i$ 円である.$i$ 日目には,以下の行動を(所持金や所持株の範囲内で)何度でも行うことができる. $A…

TopCoder SRM 671, Division 1, Level 1 : BearCries

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14010&rd=16551 問題概要 ';' + 1 つ以上の '_' + ';' という文字列を顔文字であるとする.例えば ";_;" や ";____;" は顔文字であるが,";;" や ";_" は顔文字ではない. ';' と '_' か…

Codeforces 323, Division 1, B ( Division 2, D ) : Once Again...

問題文 http://codeforces.com/contest/583/problem/D 問題概要 $n$ 項の数列を $T$ 回繰り返した,$nT$ 要素の数列 $a$ が与えられる(与えられるのは最初の $n$ 要素のみ).$a$ の単調非減少な部分列の内,最長のものの長さを求めよ. $1 \leq n \leq 100…

TopCoder, Single Round Match 667, Division 1, Level 1 : OrderOfOperations

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13987&rd=16547 問題概要 問題設定は Division 2, Level 2 と同一だが制約が異なる. $1 \leq N \leq 50$ $1 \leq M \leq 20$

AtCoder Biginner Contets 029, D - 1

問題文 http://abc029.contest.atcoder.jp/tasks/abc029_d 問題概要 正整数 $N$ が与えられる.$N$ 以下の正整数全てを 10 進数で表したとき,出現する 1 の個数を求めよ. $N

TopCoder, Single Round Match 667, Division 2, Level 2 : OrderOfOperationsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13988&rd=16547 問題概要 特殊なコンピュータがあり,コンピュータにはサイズ $M $ のメモリが積まれている. このコンピュータ上で $N$ 個の命令を実行したい.各命令は,コンピュータ上…

TopCoder, Single Round Match 656, Division 1, Level 1 : RandomPancakeStack

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416 問題概要 枚のパンケーキがあって, 番のパンケーキの大きさは ,美味しさは である. このパンケーキ群を,以下の手順で積み上げる ランダムに 1 枚のパンケーキを選び,…

TopCoder, Single Round Match 654, Division 1, Level 1 : SquareScores

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318 問題概要 文字列 について,その文字列の得点を次のように定める インデックスの対 であって,部分文字列 がただ一種類の文字から成るようなものの個数 今,文字列 が与え…

TopCoder, Single Round Match 653, Division 1, Level 1 : CountryGroupHard

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13688&rd=16317 問題概要 何人かの人が一列に並んでいる.人々は,出身が同じ人同士は連続した位置に座っていることが分かっている.それぞれの人に対し,「同じ出身の人は何人いるか」と…

TopCoder, Single Round Match 653, Divisino 2, Level 3 : SingingEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13685&rd=16317 問題概要 Alice と Bob はある歌を歌おうとしている.今,歌に表れる音階を の整数で表す(値が音の高さを表す).また,歌おうとしている曲は配列 で表される. Alice と…

TopCoder, Single Round Match 650, Division 2, Level 2 : TaroFillingAStringDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13668&rd=16314 問題概要 'A', 'B', '?' からなる文字列 が与えられる.この文字列中の '?' を 'A' まては 'B' に(独立に)置き換えることを考える. 文字列の "ugliness"(醜さ)を,文…

TopCoder, Single Round Match 649, Division 2, Level 2 : CartInSupermarketEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13659&rd=16313 問題概要 一列に連結された 個のショッピングカートがある.次の 2 種類の操作を繰り返し適用して,全てのカートをできるだけ早く消し去りたい. それぞれの列を,より短…

TopCoder, Single Round Match 649, Division 1, Level 1 : Decipherability

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13656&rd=16313 問題概要 文字列 と正整数 が与えられる. から 文字を削除して得られる文字列が与えられたとき,削除された文字の位置を一意に特定できるか否か,求めよ.

TopCoder, Single Round Match 648, Division 2, Level 3 : ABC

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13645&rd=16312 問題概要 二つの正整数 が与えられる.次の条件を満たす文字列 を 1 つ求めよ.存在しない場合は空文字列で示せ. は 文字からなり, である. 整数の順序対 であって, …

TopCoder, Single Round Match 648, Division 1, Level 1 : AB

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13642&rd=16312 問題概要 二つの正整数 が与えられる.次の条件を満たす文字列 を 1 つ求めよ.存在しない場合は空文字列で示せ. は 文字からなり, を構成する各文字は 'A' または 'B' …

TopCoder, Single Round Match 647, Division 1, Level 2 : CtuRobots

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13595&rd=16279 問題概要 何体かのロボットが売られていて, 番のロボットの価格は ,燃料タンクの容量は である.購入時に燃料タンクは満タンの状態になっている.これらのロボットの内…

TopCoder, Single Round Match 642, Division 1, Level 1 : WaitingForBus

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13540&rd=16085 問題概要 Joseph の住む町のバスターミナルは確率的に営業される. バスターミナルの開業前,バスターミナルには 台のバスが待機していて,各バスは で番号付けられる.ま…

Codeforces #274, Division 1, C ( Division 2, E ) : Riding in a Lift

問題文 http://codeforces.com/contest/480/problem/C 問題概要 階ある建物のエレベーターで遊ぶ。プレイヤーは最初 階にいて、 階に行くことはできない。また、 階から 階に移動するとき、 かつ でなければならない。このルールを守って 回移動するとき、移…

Codeforces #272, Division 1, C ( Division 2, E ) : Dreamoon and Strings

問題文 http://codeforces.com/contest/477/problem/C 問題概要 二つの文字列 が与えられる。 から 文字を消去したとき、 が に重複しない部分文字列として表れる個数の最大値を全ての について求めよ。

Codeforces #271, D : Flowers

問題文 http://codeforces.com/contest/474/problem/D 問題概要 'W', 'R' からなる文字列であって、出現する全ての 'W' を互いに交差しない、連続した長さ の区間に分割できるものについて考える。 以下の形式のクエリを 件処理せよ。 二つの整数 が与えられ…