読者です 読者をやめる 読者になる 読者になる

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 に変形するために必要な操作回数の最小値を求…

TopCoder SRM 583, Division 1, Level 2 : TurnOnLamps

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12606&rd=15503 概要 N 頂点からなる木があり、木の各辺には 0 か 1 が割り当てられている。 この木に対して、二頂点を結ぶパス(一意に定まる)上の辺の数字を入れ替える操作ができる。 …

AtCoder Regular Contest #014, C : 魂の還る場所

問題文 http://arc014.contest.atcoder.jp/tasks/arc014_3

TopCoder SRM 582, Division 2, Level 2 : SpaceWarDiv2

解法 http://community.topcoder.com/stat?c=problem_statement&pm=12605&rd=15502 概要 制約以外 Division 1, Level 1 と同一。

Codeforces #186, C : Ilya and Matrix

問題文 http://codeforces.com/contest/313/problem/C 概要 個の整数が与えられ、それを の行列上に配置する。 行列の "美しさ" を次のように定義したとき、美しさが最大になるように配置した場合の美しさを求めよ。 行列に含まれる最大の要素を m とする 行…

TopCoder SRM 579, Division 2, Level 1 : PrimalUnlicensedCreatures

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12524&rd=15499 概要 モンスターを他のモンスターと戦わせる。 自分のモンスターの強さが相手のそれより厳密に高いとき、自分のモンスターが勝つことができる。 相手のモンスターに勝った…

TopCoder SRM 579, Division 1, Level 1 ( Division 2, Level 2 ) : UndoHistory

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499 概要 特殊なテキストエディタを使っていくつかの文字列を入力する。 実際に出力される内容は Results Window の内容である。入力した文字列はバッファに入り、Enter キー…

Codeforces #178, B : Shaass and Bookshelf

問題文 http://codeforces.com/contest/294/problem/B 概要 N 冊の本があり、それぞれについて厚さ( 1 or 2 )と幅の情報が与えられる。 何冊かの本は立てて、残りの本は立てた本の上に寝かす(問題文中の図を参照)。 ただし、寝かした本の幅の合計が立て…

Codeforces #177, Division 2, C : Polo the Penguin and Strings

問題文 http://codeforces.com/contest/289/problem/C 概要 次の条件を満たす文字列のうち、辞書順最小のものを出力せよ。 文字列は、n 文字の英小文字からなる ちょうど k 種類の文字を含む 隣り合う文字同士は全て相異なる そのような文字列が存在しない場…

TopCoder SRM 573, Division 1, Level 1 : TeamContest

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12470&rd=15493 概要 0 から N * 3 - 1 に番号付けされた N * 3 人が三人で一つのチームを組みプログラミングコンテストに参加する。 参加者の強さは配列 strength にて与えられ、チーム…

TopCoder SRM 573, Division 2, Level 2 : TeamContestEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12471&rd=15493 概要 基本的に Div1, Level 1 と同一。 ただしこちらは、チームの強さは強い方二人の強さの合計。

2013 TCO Algorithm - Round 1B, Level 2 : EllysFigurines

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12447 概要 グリッド状の平面にいくつかの人形が置かれている。 一回の操作で、R 個以下の連続する行または C 個以下の連続する列から人形を取り除くことができる。 全ての人形を取り除く…

Codeforces #169, C : Little Girl and Maximum Sum

問題文 http://codeforces.com/contest/276/problem/C 概要 配列 a に対する次のようなクエリがある。 区間 [ l, r ) の総和を計算する ここで q 個のクエリがくるので、クエリを受け付ける前に配列を並び替えてクエリの結果の総和を最大化したい。 そうした…

TopCoder SRM 571, Division 1, Level 1 : FoxAndMp3

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12436 概要 Division 2, Level 2 : FoxAndMp3Easy と制約以外同一。

Codeforces 160, Division 2, B : Roma and Changing Signs

問題文 http://codeforces.com/contest/262/problem/B 概要 n 項からなる単調非減少な数列が与えられる。 この数列の任意の項をちょうど k 回符号反転し、和を最大化したい。 得られる和の最大値を求めよ。

Codeforces 160, Division 2, C : Maxim and Discounts

問題文 http://codeforces.com/contest/262/problem/C 概要 n 個の品物を購入したい。 今この店では割引セールをやっており、m 個あるバスケットのいずれかに 個丁度の商品を入れることで、二個までの商品を無料にすることができる。 ただし、無料にできるの…

Codeforces 159, A : Sockets

問題文 http://codeforces.com/contest/257/problem/A 概要 n 個のテーブルタップがあり、各タップは a_i 個の差込口を持っている。 さらに、m 個のデバイスと k 個のコンセントがある。 最小で幾つのタップを使うことで、全てのデバイスを接続することがで…

TopCoder SRM 563, Division 1, Level 1 : FoxAndHandle

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185 概要 二つの文字列 X, Y を先頭からマージしたものを Z とする。 既にマージされた文字列 S が与えられる。 X は S の部分列、Y は X を並び替えたものであるとする。 X …

TopCoder SRM 545, Div1-L1/Div2-L2 : StrIIRec

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12025&rd=14737 概要 文字列 S の"転倒数"を次のように定める。 i S[j] を満たす i, j の組の数 アルファベットの先頭 n 文字を組み合わせた文字列を考える。 次の二つの条件を満たす辞書…

SRM 561, Division 1, Level 1 : ICPCBalloons

概要 N 色の風船があり、それぞれの数と大きさ(大小二種類)の情報が与えられる。 この風船を使って( ICPC のように)正解者に風船を与えるコンテストを開催する。 風船の割り当ては、次の二つの条件を満たさなければならない。 同一の問題に対しては、色…

SRM 560, Division 2, Level 2 : TomekPhone

概要 トグル式で入力する携帯電話のキーボードを設計した。 キーには自由に文字を割り当てられる。 各キーに割り当てられる文字の数と、ある文章中に出現する文字の数が与えられる。 その文章をタイプするのに必要なタイプ数の最小値を求めよ。 文字を割り当…