torus711 のアレ

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

TopCoder

TopCoder, Single Round Match 648, Division 2, Level 1 : KitayutaMart2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13650&rd=16312 問題概要 ある店ではりんごを売っている.このりんごの値段は,買う個数を増やす毎に,1 つ目は ,2 つ目は ,3 つ目は というように値段が上がっていく.一般的に書くと…

TopCoder, Single Round Match 648, Division 2, Level 2 : Fragile2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13648&rd=16312 問題概要 頂点の(連結とは限らない)単純無向グラフが与えられる.グラフは の文字の行列 として与えられる. が 'Y' のとき,2 頂点 を結ぶ辺が存在することを表し,'N'…

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 2, Level 1 : PeacefulLine

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13632&rd=16279 問題概要 何人かの生徒を直線状に並べたい.生徒を並べたとき,隣り合う生徒の年齢が同じ場合,お喋りを初めてしまって迷惑になることが知られている. 今,並べたい生徒…

TopCoder, Single Round Match 647, Division 2, Level 2 : TravellingSalesmanEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13631&rd=16279 問題概要 個の街があり,その内の幾つかの街に商品を売りに行く.商品の情報は 2 つの配列 で与えられ, 番の商品は,街 で売ることができて,そのときの利益が であるこ…

TopCoder, Single Round Match 647, Division 1, Level 1 : BuildingTowersEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13634&rd=16279 問題概要 直線上に 個のビルを建てたい.ビルは,端から順に で番号付けられる.ビルの高さには制約があり,その内の 1 つは 要素の 2 つの配列 で説明される.高さの制約…

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 646, Division 2, Level 1 : TheConsecutiveIntegersDivTwo

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13626&rd=16278 問題概要 整数の集合があり,その要素は配列 により与えられる.この集合に対し,ある 1 つの要素を選んでその値を 1 増やすまたは 1 減らす操作を任意回数できる. 整数 …

TopCoder, Single Round Match 646, Division 2, Level 2 : TheGridDivTwo

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278 問題概要 今,無限に広い 2 次元空間の原点にいる.1 回の移動では 4 近傍(上下左右)のいずれかの方向に距離 1 移動することができる. 平面上のいくつかの座標はブロッ…

TopCoder, Single Round Match 646, Division 1, Level 1 : TheConsecutiveIntegersDivOne

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278 問題概要 整数の集合があり,その要素は配列 により与えられる.この集合に対し,ある 1 つの要素を選んでその値を 1 増やすまたは 1 減らす操作を任意回数できる. 整数 …

TopCoder, Single Round Match 646, Division 1, Level 2 : TheGridDivOne

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13627&rd=16278 問題概要 今,無限に広い 2 次元空間の原点にいる.1 回の移動では 4 近傍(いずれかの座標軸に平行な方向)のいずれかの方向に距離 1 移動することができる. 平面上のい…

TopCoder, Single Round Match 645, Division 2, Level 1 : BacteriesColony

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13604&rd=16277 問題概要 バクテリアの入った容器が一列に並べられている.このバクテリアは,日中に於ける両隣の容器のバクテリアの量によって,夜間に増減する(変化しない場合もある)…

TopCoder, Single Round Match 645, Division 2, Level 2 : ConnectingCars

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13602&rd=16277 問題概要 直線状のレールの上に複数のカートが並んでいる.左から 番目のカートの左端座標は で,その長さは である. このカートを,全て連結された状態にしたい.すなわ…

TopCoder, Single Round Match 645, Division 1, Level 1 : JanuszTheBusinessman

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13603&rd=16277 問題概要 Janusz はホテルを経営している.今年宿泊を予定している客について到着する日と出発する日が分かっていて, 番の客は, に到着して, に出立する. Janusz は,…

TopCoder, Single Round Match 643, Division 2, Level 1 : TheKingsArmyDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13597&rd=16086 問題概要 のグリッド状に兵士が配置されている.各兵士の精神状態は,「幸せ」または「つらみ」のいずれかの状態をとる. 「幸せ」な兵士が 2 人以上隣接しているとき,そ…

TopCoder, Single Round Match 643, Division 1, Level 1 ( Division 2, Level 2 ) : TheKingsFactorization

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13594&rd=16086 問題概要 整数 が与えられる. を素因数分解し,素因数を昇順に列挙した配列を return せよ. ただし,ヒントとして答えの偶数番目(0-based)の要素が全て与えられる.正…

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

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

TopCoder, Single Round Match 642, Division 2, Level 1 : ForgetfulAddition

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13553&rd=16085 問題概要 Alice は,2 つの正整数 からなる数式 をコンピュータに入力しようとしたが,'+' キーが壊れていて数字のみが入力されてしまった.彼女が入力した(数字のみから…

TopCoder, Single Round Match 642, Division 2, Level 2 : LightSwitchingPuzzle

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13555&rd=16085 問題概要 直線上に並んだ 個の電灯がある.電灯は端から順に, と番号付けられていて,各電灯はオンまたはオフの二つの状態のいずれかをとる. Leo は,全ての電灯をオフ…

TopCoder, Single Round Match 642, Division 2, Level 3 : TallShoes

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13523&rd=16085 問題概要 不思議の国の王様は,底の高い靴を履くのが好きである. 不思議の国には 個の町と,それらを結ぶいくつかの道路がある.道路の情報は 3 つの配列 によって表され…

TopCoder, Single Round Match 641, Division 2, Level 1 : BuyingTshirts

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13548&rd=16084 問題概要 Quimey と Pablo は,これから 日間に渡って T シャツを購入する. 日目は,以下のように進行する. Quimey が ,Peblo が の収入を得る Quimey と Peblo はそれ…

TopCoder, Single Round Match 641, Division 2, Level 2 : TrianglesContainOriginEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13547&rd=16084 問題概要 平面上の点集合が与えられる.この点集合から 3 点を選んで,その 3 点を頂点とする三角形を作ることを考える.点 が三角形の内部に含まれるような 3 点の選び方…

TopCoder, Single Round Match 641, Division 2, Level 3 : ShufflingCardsDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13549&rd=16084 問題概要 枚のカードがあり,各カードには の番号が重複無く 1 つずつ書かれている.カードは初期状態では番号の昇順に積まれている. このカードの山に対して以下の手順…

TopCoder, Single Round Match 641, Division 1, Level 1 : TrianglesContainOrigin

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13309&rd=16084 問題概要 平面上の点集合が与えられる.この点集合から 3 点を選んで,その 3 点を頂点とする三角形を作ることを考える.点 が三角形の内部に含まれるような 3 点の選び方…

TopCoder, SRM 638, Division 2, Level 1 : NamingConvention

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13521&rd=16081 問題概要 英小文字と '_' からなる文字列が与えられる。この文字列は、単語の間に '_' を挟むことで単語の切れ目を明示する形式(スネークケース)である。キャメルケース…

TopCoder, SRM 638, Division 2, Level 2 : NarrowPassage2Easy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13520&rd=16081 問題概要 狭い通路に、何匹かの狼がいる。 番目の狼の大きさは である。 通路はとても狭いので、いくつかの狼のペアは互いにすれ違うことができない。 番の狼と 番の狼が…

TopCoder, SRM 638, Division 2, Level 3 : CandleTimerEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13519&rd=16081 問題概要 いくつかのロウソクが、木(ネットワークトポロジー的な意味で)状に配置されている。この木を使って時間を測ることを考える。計測の手順は、まず葉にあたるいく…

TopCoder, SRM 638, Division 1, Level 1 : ShadowSculpture

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081 問題概要 複数の単位立方体からなる立体をつくる。立体を構成する単位立方体は、 の立方体を構成する単位立方体の部分集合である。 作られる立体は、2 つの条件を満たさな…

TopCoder, SRM 637, Division 2, Level 1 : GreaterGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13505&rd=16080 問題概要 枚のカードを使った 2 人ゲームをする。各カードには の整数値が書かれている。 ゲーム開始前、プレイヤーはそれぞれ 枚ずつのカードを配られ、ゲームに使う順番…

TopCoder, SRM 637, Division 2, Level 2 : PathGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13506&rd=16080 問題概要 グリッド状の盤面を使ったゲームをする。盤面の高さは 2 で固定であり、横の長さは正整数で表される。また、盤面上の各セルは黒または白に塗られている。初期状…

TopCoder, SRM 637, Division 2, Level 3 : ConnectingGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13507&rd=16080 問題概要 グリッド状の盤面を使った 2 人ゲームをする。盤面上のセルは、いくつかの Region に分かれている。Region とは、盤面をグリッドグラフと見做したときに互いに連…

TopCoder, SRM 637, Division 1, Level 1 : GreaterGame

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13504&rd=16080 問題概要 枚のカードを使った 2 人ゲームをする。各カードには の範囲の整数値が書かれている。 ゲーム開始前、プレイヤーはそれぞれ 枚ずつのカードを配られ、ゲームに使…

TopCoder, SRM 636, Division 2, Level 1 : GameOfStones

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13480&rd=16079 問題概要 石がいくつかの山に分けて積まれている。山に関する情報は数列 によって与えられ、 番目の山に積まれている石の数は である。 一つの山から別の山へ、2 つの石を…

TopCoder, SRM 636, Division 2, Level 2 : SortishDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13500&rd=16079 問題概要 サイズ の順列について考える。順列 について、有効な 2 つのインデックス について、 である ものの個数を の sortedness と呼ぶ。 サイズ の順列からいくつか…

TopCoder, SRM 636, Division 1, Level 1 : ChocolateDividingEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13497&rd=16079 問題概要 グリッド状の盤面があり、各セルには得点が割り振られている。得点は文字列配列 で表され、盤面の 行目 列目のセルの得点は である。 この盤面を、いずれも空で…

TopCoder, SRM 635, Division 1, Level 1 : SimilarRatingGraph

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13485&rd=16078 問題概要 レーティングラフとは点の列である。 グラフ上の区間とは、点列の連続する部分列である。二つの異なる区間について、平行移動と拡大・縮小のみによって一方から…

TopCoder, SRM 635, Division 2, Level 1 : IdentifyingWood

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13487&rd=16078 問題概要 二つの文字列 が与えられる。 が を部分列として含むか否か、求めよ。

TopCoder, SRM 635, Division 2, Level 2 : QuadraticLaw

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13486&rd=16078 問題概要 ある教師は、授業に 分遅刻したら、授業を 分早く終わらせることにしている。授業が始まる前に授業を終わらせることはできないため、遅刻しすぎることはできない…

TopCoder, SRM 635, Division 2, Level 3 : LonglongestPathTree

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13416&rd=16078 問題概要 頂点からなる重み付きの木が与えられる。辺に関する情報は要素数が の三つの配列 によって与えられ、 番目の辺は を距離 で結んでいる。 この木に対し、一つの辺…

TopCoder SRM 634, Division 2, Level 1 : MountainRanges

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13454&rd=16077 問題概要 数列 が与えられる。 の要素であって、その両隣の要素よりも真に大きいものの数を求めよ。

TopCoder SRM 634, Division 2, Level 2 : ShoppingSurveyDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13458&rd=16077 問題概要 ある店では 種類の商品を販売している。 人の顧客について、それぞれが購入した商品のリストを作成した。なお、各顧客は同じ品物は高々一つしか購入しない。また…

TopCoder SRM 634, Division 1, Level 1 : ShoppingSurveyDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13455&rd=16077 問題概要 ある店では 種類の商品を販売している。 人の顧客について、それぞれが購入した商品のリストを作成した。なお、各顧客は同じ品物は高々一つしか購入しない。また…

TopCoder SRM 628, Division 2, Level 1 : BishopMove

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13280&rd=16009 問題概要 のチェス盤上の位置 にビショップが置かれている。このビショップを位置 に移動させるために必要な手数の最小値を求めよ。到達不可能な場合は -1 で示せ。 ※ビシ…

TopCoder SRM 628, Division 2, Level 2 : BracketExpressions

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13243&rd=16009 問題概要 "(){}[]" に含まれる 6 種類の括弧及び 'X' からなる文字列 が与えられる。'X' を括弧の内任意の一文字に(独立に)置換できるとき、括弧の対応を取ることができ…

TopCoder SRM 628, Division 2, Level 3 : InvariantSets

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13242&rd=16009 問題概要 内の整数からなる集合 と、 上の写像 がある。 は配列 によって表され、 である。 また、 の部分集合 が invariant set であるとは、次の条件を満たすときである…

TopCoder SRM 628, Division 1, Level 1 : DivisorsPower

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13241&rd=16009 問題概要 関数 を の正の約数の個数を求める関数であるとする。また、関数 を と定める。 整数 が与えられる。 となる最小の を求めよ。そのような が存在しない場合は -1…

TopCoder, SRM 628, Division 1, Level 2 : CircuitsConstruction

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13237&rd=16009 問題概要 特殊な電気回路について考える。回路の構成は文字列で表される。 まず、単一の素子は一つの回路である。これは、文字列 "X" として表される。 また、二つの回路…

TopCoder, SRM 629, Division 2, Level 1 : RectangleCoveringEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13363&rd=16060 問題概要 サイズが であるような長方形の穴がある。この穴を、サイズが であるような長方形の板で塞ぐ。板は回転されて使うこともできるが、板の辺は穴の辺に並行または直…

TopCoder, SRM 629, Division 2, Level 2 : CandyMaking

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13340&rd=16060 問題概要 個の容器があり、 番目の容器の容積は である。これらの容器全てを均一な密度の物体で満たしたい。ただし、 番目の容器の内容物の重さは、 に近付けたい。 容器…

TopCoder, SRM 629, Division 1, Level 1 : RectangleCovering

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13344&rd=16060 問題概要 サイズが である長方形の穴がある。また、長方形の板を複数枚もっていて、 番目の板のサイズは である。この板たちを使って穴を塞ぎたい。板は回転させて配置し…