Greedy
問題文 https://atcoder.jp/contests/abc180/tasks/abc180_d 問題概要 正整数 $X, Y, A, B$ がある.ここで,次の 2 種類の操作を考える. $X \leftarrow XA$ $X \leftarrow X + B$ $X 制約 $1 \leq X $2 \leq A \leq 10^9$ $1 \leq B \leq 10^9$
問題文 https://atcoder.jp/contests/abc171/tasks/abc171_b 問題概要 相異なる $N$ 個の正整数からなる列 $\{ p_i \}$ が与えられる.ここから $K$ 項を選んで和を取るとき,和として有り得る値の最小値を求めよ. 制約 $1 \leq K \leq N \leq 1{,}000$ $1 …
問題文 https://atcoder.jp/contests/abc169/tasks/abc169_d 問題概要 正整数 $N$ が与えられる.$N$ に対し,以下の一連の操作を繰り返し行うことを考える. 以下の条件を満たす整数 $z$ を選ぶ ある素数 $p$ と正整数 $e$ で $p^e$ と書ける $z \mid N$ で…
問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14171&rd=16688 問題概要 正整数の集合が次の条件を満たすとき,k-smooth であるとする. 任意の 2 要素 $A, B$ ($A \neq B$) について $A \leq kB$ 正整数の集合を表す配列 $a$ と正整…
問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14169 問題概要 正整数の配列が与えられる.この配列に対し,以下の操作を任意回行う. 2 つの要素 $x, y$ を選ぶ $x, y$ を削除する $\mathit{ GCD }( x, y ), \mathit{ LCM }( x, y )$…
問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651 問題概要 $1$ から $M $ で番号付けられた $M $ 個のパーツを使って作られる機械がある.一つの機械は,$1$ から $M $ のパーツを一つずつ使って構成される. パーツは,…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13631&rd=16279 問題概要 個の街があり,その内の幾つかの街に商品を売りに行く.商品の情報は 2 つの配列 で与えられ, 番の商品は,街 で売ることができて,そのときの利益が であるこ…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13603&rd=16277 問題概要 Janusz はホテルを経営している.今年宿泊を予定している客について到着する日と出発する日が分かっていて, 番の客は, に到着して, に出立する. Janusz は,…
問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び, 行列 が与えられる.また, 及び が成り立つ. 二つの整数 について, であるときに限り, と を交換することができる.任意回の操作で作ることができる列の内,辞書式順…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13555&rd=16085 問題概要 直線上に並んだ 個の電灯がある.電灯は端から順に, と番号付けられていて,各電灯はオンまたはオフの二つの状態のいずれかをとる. Leo は,全ての電灯をオフ…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13504&rd=16080 問題概要 枚のカードを使った 2 人ゲームをする。各カードには の範囲の整数値が書かれている。 ゲーム開始前、プレイヤーはそれぞれ 枚ずつのカードを配られ、ゲームに使…
問題文 http://codeforces.com/contest/480/problem/A 問題概要 ある学生は 科目の試験を受ける。 番の科目の試験は、本来ならば試験期間の 日目に実施されるが、教官との交渉により 日目に受験することも認められた。 番の科目の試験を受けたとき、教官は学…
問題文 http://codeforces.com/contest/472/problem/B 問題概要 人が一階でエレベーターを待っていて、 番の人が行きたいフロアは 階である。 エレベーターには 人が同時に乗ることができ、 階から 階へ移動するのに の時間がかかる。また、人の乗り降りにか…
問題文 http://codeforces.com/contest/472/problem/C 問題概要 要素の文字列配列 と、サイズ の順列 が与えられる。 各 について または のいずれかを選んで としたとき、 を辞書式順序に於いて単調増加にすることができるか否か、求めよ。 なお、与えられ…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13237&rd=16009 問題概要 特殊な電気回路について考える。回路の構成は文字列で表される。 まず、単一の素子は一つの回路である。これは、文字列 "X" として表される。 また、二つの回路…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13344&rd=16060 問題概要 サイズが である長方形の穴がある。また、長方形の板を複数枚もっていて、 番目の板のサイズは である。この板たちを使って穴を塞ぎたい。板は回転させて配置し…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13274&rd=16008 問題概要 英小文字からなる文字列 が与えられる。この文字列に対し、異なる二つの文字を選んで取り除く操作を繰り返し適用し、それ以上操作を適用できなくなった時点で終…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13195&rd=15857 問題概要 非負整数からなる列 danceCost と、正整数 K ( ) が与えられる。danceCost から重複せずに K 項を選んだきの総和の最小値を求めよ。
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13192&rd=15855 問題概要 いくつかの飴を持っている。飴には種類があり、i 番目の種類の飴の数は candyCounts[ i ] で与えられる。また、非負整数 i を用いて と表せる大きさの箱を無限個…
問題文 http://code.google.com/codejam/contest/2994486/dashboard#s=p2 問題概要 N 個の街があって、それぞれの街は固有の郵便番号をもっている。また、いくつかの街の間は空路で結ばれていてる。 全ての街を訪れることができるように飛行機を予約したいが…
問題文 http://codeforces.com/contest/426/problem/A 問題概要 容積が s である空のカップと、n 個のマグカップを使ったゲームをする。n 個のマグカップには最初水が入っていて、i 番のマグカップの内容量は である。各プレイヤーは一回ずつ、空でないマグ…
問題文 http://codeforces.com/contest/426/problem/C 問題概要 項数 n の数列 a と整数 k が与えられる。m( a ) を a の連続する部分列の和の最大値とし、a の二つの要素を交換する操作を最大 k 回できるとき、m( a ) の最大値はいくらか。 なお、 である。
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=11281&rd=15850 問題概要 あるゲームに於いて、より多くのアイテムを売ることを考える。ゲーム内での一日には、以下の事象がこの順で起こる。 在庫の内、stale_limit 日以上前に生産され…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13094&rd=15849 問題概要 ある国の通貨体系では、コインは次の condition を満たす。 コインの価値は相異なる 価値 1 のコインが存在する 任意の二種類のコインについて、片方の価値は他…
問題文 http://codeforces.com/contest/401/problem/A 問題概要 それぞれ絶対値が x 以下の整数が一つ書かれたカードが n 枚ある。同様の(絶対値が x 以下の整数が一つ書かれたカード)を複数枚加えて、全てのカードに書かれた値の和を 0 にしたい。最小で…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12994&rd=15842 問題概要 それぞれ色が異なる K 種類のボールがあり、色 i のボールは X[ i ] 個ある。これらのボールをパッケージに分割したい。一つのパッケージには 1 〜 K 個のボール…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12998&rd=15841 問題概要 合計で C 個の飴があり、いくつかの箱に入っている。それぞれの箱に入っている飴の正確な数は分からないが、i 番の箱に入っている飴の数は高々 high[ i ] である…
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12997&rd=15841 問題概要 合計で C 個の飴があり、いくつかの箱に入っている。それぞれの箱に入っている飴の正確な数は分からないが、i 番の箱に入っている飴の数は [ low[ i ], high[ i …
問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12939&rd=15836 概要 要素数が偶数である数の(多重)集合が与えられる。要素数を N として、この集合を N / 2 個のペアに分割する(一つの数は丁度一つのペアに属する)。ここで、負の整…
問題文 http://abc003.contest.atcoder.jp/tasks/abc003_3 概要 値 C を持っているときに値 R を "使う" と、持っている値が ( C + R ) / 2 に変化する。N 個の整数があって、その内 K 個を選んで任意の順番で使う。初期状態で 0 を持っているとして、持って…