torus711 のアレ

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

TopCoder

TopCoder SRM 684, Division 1, Level 1 : CliqueParty

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14171&rd=16688 問題概要 正整数の集合が次の条件を満たすとき,k-smooth であるとする. 任意の 2 要素 $A, B$ ($A \neq B$) について $A \leq kB$ 正整数の集合を表す配列 $a$ と正整…

GCDLCM2

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14169 問題概要 正整数の配列が与えられる.この配列に対し,以下の操作を任意回行う. 2 つの要素 $x, y$ を選ぶ $x, y$ を削除する $\mathit{ GCD }( x, y ), \mathit{ LCM }( x, y )$…

TopCoder SRM 681, Division 2, Level 2 : ExplodingRobots

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14137&rd=16651 問題概要 平面上に二つのロボットを置く.一つは座標 $( x_1, y_1 )$ に,他方は $( x_1, y_1 )$ に置く. 各ロボットは,$U, D, L, R$ からなる命令列 $\mathit{ instru…

TopCoder SRM 681, Division 2, Level 1 : CoinFlipsDiv2

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14138&rd=16651 問題概要 表裏を区別できる $N$ 枚のコインが一直線上に並んでいる.コインは左から右に $0$ から $N - 1$ で番号付けられている.コインの状態は長さ $N$ の配列 $\math…

TopCoder SRM 681, Division 1, Level 1 : FleetFunding

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651 問題概要 $1$ から $M $ で番号付けられた $M $ 個のパーツを使って作られる機械がある.一つの機械は,$1$ から $M $ のパーツを一つずつ使って構成される. パーツは,…

TopCoder SRM 674, Division 1, Level 1 : VampireTree

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14000&rd=16624 問題概要 数のリスト $\mathit{ num }$ が与えられる.$| \mathit{ num } | = N$ とする. $N$ 頂点の木であって,$i$ 番目の頂点の次数が $\mathit{ num }_i$ であるよ…

TopCoder SRM 671, Division 1, Level 2 : BearDarts

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13951&rd=16551 問題概要 正整数からなる列 $w$ が与えられる.4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき,$ac = bd$ となっているものの総数を求めよ. $4 \l…

TopCoder SRM 671, Division 1, Level 1 : BearCries

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

TopCoder SRM 670, Division 1, Level 2 ( Division 2, Level 3 ) : Treestrat

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13990&rd=16550 問題概要 $N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする.プレイヤーを A, B として,A は赤いトークンを,B は青いトークンを使う. 木の頂点は $0$ から $…

TopCoder SRM 670, Division 1, Level 1 : Bracket107

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550 問題概要 '(' と ')' からなる,括弧がバランスした文字列 $S$ が与えられる.4 つの性質, 長さが $S$ と等しい 括弧がバランスしている $S$ と等しくない $S$ との最長…

TopCoder, Single Round Match 666, Division 1, Level 1 : WalkOverATree

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13955&rd=16515 問題概要 $N$ 頂点の木があって,各頂点は $0$ から $N - 1$ で番号付けられている.木の情報は配列 $\mathit{ parent }$ で与えられ,有効な $i$ について,頂点 $i + 1$…

TopCoder, Single Round Match 666, Division 2, Level 2 : GoodString

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13751&rd=16515 問題概要 文字列に対して,以下の操作を考える 文字列のどこか(先頭,末尾も許容)に,文字列 "ab" を挿入する 空文字列から始めてこの操作を複数回適用することで,文字…

TopCoder, SRM 666, Division 2, Level 1 : DevuAndGame

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13744&rd=16515 問題概要 全ての頂点の出次数が高々 1 であるような,$N$ 頂点の有向グラフが与えられる.このグラフにおいて頂点 0 から辺に沿って移動したとき,出次数 0 の頂点に到達…

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$

TopCoder, Single Round Match 669, Division 2, Level 2 : CombiningSlimes

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13947&rd=16549 問題概要 初めに正整数の多重集合 $a$ がある.$|a| > 1$ である間,以下の操作をする. $a$ から要素を 2 つ取り除き,それらを $x, y$ とする. $a$ に $x + y$ を加え…

TopCoder, Single Round Match 669, Division 2, Level 1 : LiveConcert

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13948&rd=16549 問題概要 $M $ 曲の歌があって,歌 $i$ はアイドル $s_i$ にのみ歌うことができる.コンサートで歌 $i$ を歌うと聴衆の幸福度が $h_i$ 上がる.また,各アイドルはコンサ…

TopCoder, Single Round Match 669, Division 1, Level 1 - SubdividedSlimes

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13946&rd=16549 問題概要 整数 $S$ が与えられる. 最初,$S$ のみを含む多重集合が手元にあり,以下の操作を(それが可能な限りにおいて)好きなだけ行うことができる. 集合の元を一つ…

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 667, Division 2, Level 1 : PointDistance

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13989&rd=16547 問題概要 平面上の 2 点 $A$, $B$ が与えられる.以下の条件を満たす点 $C$ を 1 つ求めよ. $C \neq A$ かつ $C \neq B$ $C$ のそれぞれの座標は $-100$ 以上 $100$ 以下…

TopCoder, Single Round Match 668, Division 2, Level 2 : IsItASquare

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14004&rd=16548 問題概要 平面上の点が 4 個与えられる.これらの点が正方形を成すか? なお,与えられる点は相異なる.

TopCoder, Single Round Match 668, Division 2, Level 1 : VerySecureEncryption

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=14005&rd=16548 問題概要 $N$ 文字からなる文字列 $\mathit{ message }$ に対し,次の操作を考える. 各位置 $i$ について,$\mathit{ message }_i$ の文字が位置 $\mathit{ key }_i$ に…

TopCoder, Single Round Match 668, Division 1, Leevl 1 : PaintTheRoom

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548 問題概要 $R \times C$ のグリッド状の盤面がある.この盤面上で,上下左右に隣接するセルにのみ移動することができる.任意のセルから始めて,任意のセルで終わる移動で…

TopCoder, Single Round Match 664, Division 1, Level 1 : BearPlays

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13916&rd=16513 問題概要 いくつかの石が 2 つの山に分けられて積まれている.片方の山に積まれている石の数は $A$ 個で,他方の山のそれは $B$ 個である. この 2 つの山に対し,次の操…

TopCoder, Single Round Match 656, Division 2, Level 1 : CorruptedMessage

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13748&rd=16416 問題概要 英小文字の内 1 種類の文字からなる文字列 を送ったが,伝送途中で丁度 文字が異なる文字に変わってしまった. と が与えられるので,元の文字列として考えられ…

TopCoder, Single Round Match 656, Division 2, Level 2 : RandomPancakeStackDiv2

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

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 655, Divisino 1, Level 1 : BichromePainting

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13709&rd=16415 問題概要 グリッド状の盤面に色を塗る.盤面上のセルは最初,全て白に塗られている.可能な操作は,与えられた整数 について, の矩形領域を任意に選択して,その内部全体…

TopCoder, Single Round Match 655, Division 2, Level 1 : BichromeBoard

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13719&rd=16415 問題概要 グリッド状の盤面がある.この盤面の各セルを白または黒に塗る.いくつかのセルについては塗る色が決まっているが,色が決まっていないセルもある. 塗り方の情…

TopCoder, Single Round Match 655, Division 2, Level 2 : FoldingPaper2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13721&rd=16415 問題概要 大きさが の長方形の紙がある.この紙を辺に平行かつ,操作後の紙の辺の長さが共に整数となるような線で折りたたむ操作ができる. 面積が となるように折りたた…

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 654, Division 2, Level 1 : SquareScoresDiv2

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

グラフ]TopCoder, Single Round Match 654, Division 2, Level 2 : OneEntrance

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13698&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, Division 1, Level 2 : Singing

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13680&rd=16317 問題概要 Alice と Bob は 2 人で歌を歌おうとしている.曲に出現し得る音階は の整数で(低い方から高い方へ)番号付けされている.Alice に出すことのできる音は区間 内…

TopCoder, Single Round Match 653, Division 2, Level 1 : CountryGroup

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

TopCoder, Single Round Match 653, Division 2, Level 2 : RockPaperScissorsMagicEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13686&rd=16317 問題概要 Alice と Bob が複数回に渡ってじゃんけんをする.各ラウンドで,相手に勝利したプレイヤーが 1 ポイントを得る. 今,各ラウンドで Bob が出す手は分かっている…

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 652, Divisino 2, Level 1 : ValueOfString

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13678&rd=16316 問題概要 英小文字からなる文字列 が与えられる.また, 番目(1-based)のアルファベットに値 を割り当てる.各文字の値を などと表記する. 更に, の値を次のように定…

TopCoder, Single Round Match 652, Division 2, Level 2 : ThePermutationGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13679&rd=16316[ 問題概要 整数 が与えられる. の順列をランダムに 1 つ選び とする.また,関数 を次のように定義する. ; どの順列が として選ばれていても となる の内,最小のものを…

TopCoder, Single Round Match 652, Division 1, Level 1 : ThePermutationGame

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13229&rd=16316 問題概要 Division 2, Level 2 とほぼ同一.ただし,こちらは答えを として, を求める.

TopCoder, Single Round Match 650, Division 2, Level 3 : TheKingsRoadsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314 問題概要 正整数 と,頂点数・辺数が共に の無向グラフが与えられる.辺の情報は 2 つの配列 で与えられ,各 に対し,2 頂点 を結ぶ辺が存在する. このグラフから辺を 1 …

TopCoder, Single Round Match 650, Division 2, Level 1 : TaroJiroDividing

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13672&rd=16314 問題概要 2 つの正整数 のそれぞれに対し,次の操作を行う. 操作対象になった値を と書くことにすると, を紙に書き下す が奇数ならば,操作を終了する を で置き換える …

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 650, Division 1, Level 1 : TaroFillingAStringDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13669&rd=16314 問題概要 'A', 'B' の 2 種類の文字からなる, 文字の文字列を考える.今,文字列の長さ及びいくつかの位置の文字は決まっていて,各 に対して, 文字目の文字は である.…

TopCoder, Single Round Match 649, Division 2, Level 1 : DecipherabilityEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13658&rd=16313 問題概要 2 つの文字列 が与えられる. から 1 文字を削除することで, を作ることができるか?

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 2, Level 3 : XorSequenceEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313 問題概要 Division 1, Level 2 とほぼ同一. が直接与えられ, である点が異なる.

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

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

TopCoder, Sinle Round Match 649, Division 1, Level 2 : XorSequence

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13249&rd=16313 問題概要 整数列 と正整数 が与えられる.ここで, は 2 の冪乗であり, の要素は全て 未満である. 今,一つの整数 を選んで, の各要素を とのビットごとの排他的論理和…

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

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