torus711 のアレ

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

Greedy

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

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

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 645, Division 1, Level 1 : JanuszTheBusinessman

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

Good Bye 2014, B : New Year Permutation

問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び, 行列 が与えられる.また, 及び が成り立つ. 二つの整数 について, であるときに限り, と を交換することができる.任意回の操作で作ることができる列の内,辞書式順…

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

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

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

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

Codeforces #274, Division 1, A ( Division 2, C ) : Exams

問題文 http://codeforces.com/contest/480/problem/A 問題概要 ある学生は 科目の試験を受ける。 番の科目の試験は、本来ならば試験期間の 日目に実施されるが、教官との交渉により 日目に受験することも認められた。 番の科目の試験を受けたとき、教官は学…

Codeforces #270, B : Design Tutorial: Learn from Life

問題文 http://codeforces.com/contest/472/problem/B 問題概要 人が一階でエレベーターを待っていて、 番の人が行きたいフロアは 階である。 エレベーターには 人が同時に乗ることができ、 階から 階へ移動するのに の時間がかかる。また、人の乗り降りにか…

Codeforces #270, C : Design Tutorial: Make It Nondeterministic

問題文 http://codeforces.com/contest/472/problem/C 問題概要 要素の文字列配列 と、サイズ の順列 が与えられる。 各 について または のいずれかを選んで としたとき、 を辞書式順序に於いて単調増加にすることができるか否か、求めよ。 なお、与えられ…

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

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

TopCoder, SRM 627, Division 1, Level 1 : HappyLetterDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13274&rd=16008 問題概要 英小文字からなる文字列 が与えられる。この文字列に対し、異なる二つの文字を選んで取り除く操作を繰り返し適用し、それ以上操作を適用できなくなった時点で終…

TopCoder, SRM 624, Division 2, Level 1 : CostOfDancing

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13195&rd=15857 問題概要 非負整数からなる列 danceCost と、正整数 K ( ) が与えられる。danceCost から重複せずに K 項を選んだきの総和の最小値を求めよ。

TopCoder, SRM 622, Division 2, Level 2 : BoxesDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13192&rd=15855 問題概要 いくつかの飴を持っている。飴には種類があり、i 番目の種類の飴の数は candyCounts[ i ] で与えられる。また、非負整数 i を用いて と表せる大きさの箱を無限個…

Google Code Jam 2014, Round 1B, C : The Bored Traveling Salesman

問題文 http://code.google.com/codejam/contest/2994486/dashboard#s=p2 問題概要 N 個の街があって、それぞれの街は固有の郵便番号をもっている。また、いくつかの街の間は空路で結ばれていてる。 全ての街を訪れることができるように飛行機を予約したいが…

Codeforces #243, Division 2, A : Sereja and Mugs

問題文 http://codeforces.com/contest/426/problem/A 問題概要 容積が s である空のカップと、n 個のマグカップを使ったゲームをする。n 個のマグカップには最初水が入っていて、i 番のマグカップの内容量は である。各プレイヤーは一回ずつ、空でないマグ…

Codeforces #243, Division 1, A ( Division 2, C ) : Sereja and Swaps

問題文 http://codeforces.com/contest/426/problem/C 問題概要 項数 n の数列 a と整数 k が与えられる。m( a ) を a の連続する部分列の和の最大値とし、a の二つの要素を交換する操作を最大 k 回できるとき、m( a ) の最大値はいくらか。 なお、 である。

TopCoder, SRM 617, Division 2, Level 2 : SlimeXSlimonadeTycoon

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=11281&rd=15850 問題概要 あるゲームに於いて、より多くのアイテムを売ることを考える。ゲーム内での一日には、以下の事象がこの順で起こる。 在庫の内、stale_limit 日以上前に生産され…

TopCoder SRM 616, Division 2, Level 2 : ColorfulCoinsEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13094&rd=15849 問題概要 ある国の通貨体系では、コインは次の condition を満たす。 コインの価値は相異なる 価値 1 のコインが存在する 任意の二種類のコインについて、片方の価値は他…

Codeforces #235, A : Vanya and Cards

問題文 http://codeforces.com/contest/401/problem/A 問題概要 それぞれ絶対値が x 以下の整数が一つ書かれたカードが n 枚ある。同様の(絶対値が x 以下の整数が一つ書かれたカード)を複数枚加えて、全てのカードに書かれた値の和を 0 にしたい。最小で…

TopCoder SRM 609, Division 1, Level 2 : PackingBallsDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12994&rd=15842 問題概要 それぞれ色が異なる K 種類のボールがあり、色 i のボールは X[ i ] 個ある。これらのボールをパッケージに分割したい。一つのパッケージには 1 〜 K 個のボール…

TopCoder SRM 608, Division 2, Level 2 : MysticAndCandiesEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12998&rd=15841 問題概要 合計で C 個の飴があり、いくつかの箱に入っている。それぞれの箱に入っている飴の正確な数は分からないが、i 番の箱に入っている飴の数は高々 high[ i ] である…

TopCoder SRM 608, Divisin 1, Level 1 : MysticAndCandies

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12997&rd=15841 問題概要 合計で C 個の飴があり、いくつかの箱に入っている。それぞれの箱に入っている飴の正確な数は分からないが、i 番の箱に入っている飴の数は [ low[ i ], high[ i …

TopCoder SRM 603, Division 2, Level 2 : SplitIntoPairs

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12939&rd=15836 概要 要素数が偶数である数の(多重)集合が与えられる。要素数を N として、この集合を N / 2 個のペアに分割する(一つの数は丁度一つのペアに属する)。ここで、負の整…

AtCoder Beginner Contest #003, C : AtCoderプログラミング講座

問題文 http://abc003.contest.atcoder.jp/tasks/abc003_3 概要 値 C を持っているときに値 R を "使う" と、持っている値が ( C + R ) / 2 に変化する。N 個の整数があって、その内 K 個を選んで任意の順番で使う。初期状態で 0 を持っているとして、持って…

TopCoder SRM 599, Division 2, Level 1 : MiniatureDachshund

概要 体重が weight である犬がいる。 N 個の蜜柑があって、i 番の蜜柑の重さは mikan[ i ] である。 犬が一つの蜜柑を食べると、体重が蜜柑の重さ分だけ増加する。 体重 5,000 以下を保ったまま食べられる蜜柑の最大数を求めよ。

TopCoder SRM 598, Divisin 1, Level 1 : BinPacking

概要 N 個の品物があり、i 番の品物の重さは item[ i ] である。 また、全ての品物の重さは 100 以上 300 以下である。 これらの品物をキャパシティ 300 の箱に入れる。 最小でいくつの箱があれば全ての品物を箱に入れることができるか求めよ。

TopCoder SRM 597, Division 1, Level 1 ( Division 2, Level 2 ) : LittleElephantAndString

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12854&rd=15709 概要 長さが等しい二つの文字列 A, B が与えられる。 A に対して、ある文字を先頭に移動する操作のみが許容される。 A を B に変形するために必要な操作回数の最小値を求…