torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Greedy

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

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