貪欲法
問題 01からなる文字列が与えられる。 文字列に対して次の操作を好きなだけ行える。 文字列の一番右の'1'を含む連続する二文字の部分文字列を 11は10に 10は11か01に 01は10に することができる。 文字列S, Tが与えられたとき、SをTに最低何回の操作で変えら…
問題 hxwのグリッドの各マスをA-Zの文字いずれかで埋める。 隣り合う(辺を共有する)マスであって、同じ文字が書かれたタイルは繋がっているとする。 繋がったタイルの塊は必ず正方形をしていなければならない。 辞書順で最小の埋め方を求めよ。 制約条件 h,…
問題 次の性質をもつ自然数の集合Sをcoolであるとする。 全ての要素は0以上2^60未満 任意の異なるa, b∈Sについて(a & b) > 0 (bitwiseのand) 任意の異なるa, b, c∈Sについて(a & b & c) > 0 Sの部分集合subsetが与えられる。 サイズがNであって、subsetの…
問題 長さnの整数の列aがあり、最初はa[i]はすべて0 これを以下の操作を繰り返してa[i]をb[i]に一致させたい。 必要な操作の回数の最小値を求めよ。 すべての要素を2倍する 一つの要素を選んで+1する 制約条件 n≦50 0≦b[i]≦1000
問題 文字列Sが与えられる。 文字を並べ替えて文字列Tを作る。 Tのそれぞれの文字は、Sの元の場所から距離i以内の場所になければならない。 できる文字列のうち辞書順で最小のものを求めよ。 制約条件 Sの長さ≦50
問題 文字列に対して次の操作が行える。 好きなiを決める。 先頭のi文字はそのままにして、次からのL文字を、アルファベットの小さい順にソートする。 残りの文字は捨てる。 与えられた文字列Sおよび整数Lについて、 この操作を好きなだけSに適用してできる…
問題 n個の都市が双方向に通行可能な道でつながれていて、木をなしている。 ここにどの都市にいるかを検知するシステムを作る。 発信機を好きな都市に置くことができて、 受信機ではそれぞれの発信機からの距離(木における距離)を知ることが出来る。 全て…
問題 容量300の袋にn個の物体をつめる。 i番目の物体の大きさはitem[i]である。一つの袋には大きさの和が300以下になるように好きに物体を詰められる。 全ての物体を詰めるのに必要な袋の枚数の最小値を求めよ。 制約条件 n≦50 100≦item[i]≦300
問題 n個の箱があり、i番目の箱には最小でlow[i]個、最大でhigh[i]個のキャンディーが入っている。 全ての箱に入っているキャンディーの数を合計するとCになることがわかっている。 いま、いくつかの箱を開けて、中に入っているキャンディーの個数の合計を、…
問題 n組の封筒のペア(p[i], q[i])がある。 p[i], q[i]の封筒にはそれぞれ、コインが2枚ずつ入っている。 それぞれのコインは整数で表される種類がある。 n組のペアについて、高々片方の封筒を取っていく。(どちらも取らないことができる) こうして取り終…
問題 R, G, Bどれかの色をしたボールがn個あり、i個目の色はS[i]である。 このボールをテーブルの上に1番目から順に一列に並べていく。 i番目のボールを置くとき、これまで並べたボールの両端または好きな隙間に入れることができる。 新しいボールの左側にあ…
問題 自然数の数列a[i]に対して次の操作を、要素が一つになるまで繰り返す。 好きなi, j(i != jかつa[i]≧a[j])を選び、a[i]のうしろにa[j]を文字列としてくっつけて、新しくできた項をaに追加し、a[i], a[j]を削除する。 n桁の数字が与えられる。 このn桁…
問題 n問のコンテストを作る。i番目の問題の難易度はa[i]になるようにしたい。 持ってる問題はm問あって、i番目の難易度はb[i]. 問題の難易度はコスト0で小さくすることができるが、大きくすることはできない。 コンテストを開催するためには何問新たに問題…
問題 日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_04) 二分ヒープを表す長さnの配列a[i]がある。 二分ヒープを表す長さm(m≧n)の配列b[i]で、b[i]の後ろn個がa[i]になっているものが存在すれば、その最小のmを、なければ-1を…
問題 n個の大きさ、重さが全て同じ箱があって、i番目の箱は自分の上に他の箱をxi個置ける。 一つの箱のすぐ上にはちょうど一つの箱しか置けないとき、 全ての箱をなるべく少ない数の山に分けて積み上げたい。 山の最小個数はいくつか。 制約条件 n≦100
問題 n個のハンバーガーがあり、それぞれ種類がtype[i], 味がtaste[i]である。 この中からエイリアンに食べさせるハンバーガーを選ぶ。 エイリアンの満足度は、食べさせたハンバーガーのうち異なるtypeが何種類あるかをY 食べさせたハンバーガーの味の合計を…
問題 10, 11, 00のドミノが合計でn*m個与えられる。 これらを横向きにn*m個に並べる。 それぞれの列ごとにその列の数の和を求める。 この和の最大値が、最小になるようにしたい。最小値を求めよ。 ドミノは回転させることはできるが、縦に使うことはできない…
問題 ロボットが座標平面の原点にいる。 好きな歩数を動くことができて、i歩目の移動では上下左右のいずれかの方向に、3^iだけ移動する。 ただし途中の移動だけをスキップすることはできない。 ロボットが座標(x, y)で止まることができるかを判定せよ。 制約…
問題 長さnの01からなる文字列が与えられる。 この文字列に大して以下の操作を行うことができる。 任意の1文字の0,1を反転する 先頭からk*m文字の0,1を反転する(ただしkは任意の自然数) 操作を終えたあと、文字列の先頭からn-m文字の部分文字列と、末尾か…
問題 英小文字からなる文字列が与えられる。 文字列に対して、文字x, yを選び、文字列に現れるすべてのxをyに置換することができる。 このときにかかるコストはxが現れている回数である。 この操作を繰り返し行い、文字列を回文になるようにしたい。 かかる…
問題 n問のクイズをやって、ちょうどm問正解した。 このクイズは正解すると1問につき1点で、 k回連続で正解すると、(1点が加えられた後で)現在の得点が倍になる。 (その後、連続正解数のカウントは0に戻る) 得られた得点の最小値を求め、mod 10^9+9で出…
問題 文字列の集合がある。 この中の一つの文字列を取り(これをSとする) Sの先頭2*i(2*i≦|S|)文字を逆順にする操作を好きなだけ行うことができる。 操作を行った後で、二つの文字列が一致したら、 その文字列を消去することができる。 残る文字列の数の最…
問題 t分間にわたってgoogle code jam形式のコンテストを行う。 n問の問題があり、それぞれsmall largeにわかれている。 smallを解くのにかかる時間、largeを解くのにかかる時間が問題ごとに与えられる。 smallを解くと得られる得点、largeを解くと得られる…
問題 n個の建物があり、それぞれの高さはheights[i]である。 この建物を一列に並べるが、隣合う建物同士の距離は、隣合う建物のうち大きいほうの高さでなくてはならない。 列の端から端までの距離が最小になるような並べ方のうち、 辞書順で最小のものを求め…
問題 n階立ての建物があって、i階目にはstudents[i]人の人がいる。 Jediは一人でK人の人を倒すことができる。 x人の人が一つの階にいるとき、x/K(切り上げ)人のJediが必要である。 それぞれのstudentsを、動かさないか、上下の隣り合う階に移すことができる…
問題 '(', ')', '[', ']'からなる文字列が与えられる。 この文字列の連続する部分文字列のうち、 括弧の対応が正しいもので、'['の含まれる個数が最大であるものをどれか一つ出力せよ。 制約条件 文字列の長さ≦10^5
問題 文字列の集合Sが与えられる。 先手はこのうちひとつの文字列を選ぶ。これをxとする。 また、先手はアルファベットに好きな順に優先順位をつける。 後手は、Sのうちx以外の文字列を好きに並べ替える。 並べ替えたあと、xがSのなかで、他のどの文字列より…
問題 a1 = p ai+1 = ai * (-1)^i + q (ただし、p, qは整数)を満たす数列を、ほぼ等差数列と呼ぶ。 与えられた数列b[i]の必ずしも連続しない部分列で、ほぼ等差数列になっているもののうち、最大の長さをもつものの長さを求めよ。 制約条件 n≦4000 0≦b[i]≦1…
問題 日本語なので本文参照(http://wupc2nd.contest.atcoder.jp/tasks/wupc_05) 閉路を高々1つ含む、重みつき無向グラフが与えられる。 このグラフの辺をいくつか切断して、グラフがk個以上の連結成分に分かれるようにしたい。切断する辺の重みの和の最小…
問題 日本語なので本文参照(http://wupc2nd.contest.atcoder.jp/tasks/wupc_04) 制約条件 Ni≦10^9