解をどれか一つ
問題 n枚の袋があって、i番目の袋の中にはa[i]枚のコインが入っている。コインは全体でs枚である。 ただし、袋の中にはさらに別の袋が入っていることがある。 a[i] = {1, 1, 3}で、全体でコインが3枚ということがある。 (3番目の袋には1番目の袋と2番目の袋…
問題 n項からなる数列a[i]が与えられる。a[i]の必ずしも連続しない部分列b[i]で、 長さが4m b[4k + 1] = b[4k + 3] b[4k + 2] = b[4k + 4] が成り立つもののうち、最長のものを一つ出力せよ。 制約条件 n≦5 * 10^5 -10^9≦a[i]≦10^9
問題 n人がコンテストをした。全員l以上r以下の整数の得点を取った。 全員の得点の合計はsall点。上位k人の得点の合計はsk点である。 このような条件を満たす全員の得点の取り方をどれか一通り出力せよ。 解が存在することは保証されている。 制約条件 n, l,…
問題 無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。 答えが複数ある場合はどれを出力してもよい。 制約条件 解の存在は保証されている。
問題 10, 11, 00のドミノが合計でn*m個与えられる。 これらを横向きにn*m個に並べる。 それぞれの列ごとにその列の数の和を求める。 この和の最大値が、最小になるようにしたい。最小値を求めよ。 ドミノは回転させることはできるが、縦に使うことはできない…
問題 長さがnの数列 1 2 3 4 ... n-1 nがある。 この数列に対して3回以下、以下のような操作を行った。 l, rを選びaの区間[l, r]の順番を反転させる。 結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。 制約条件 n≦1000
新環境のテストも兼ねて出てました。がDの誤読で酷いことになった。 問題 1〜10までの重さの錘のうち、使うことができる種類のものが与えられる。 個数に制限はなく、無限に使える。 これをm回天秤に以下のルールで乗せる。 交互に違う皿に置く。 2回連続で…
問題 n頂点からなる木が与えられる。 木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。 同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも 小さいアルファベットのラベルを持つ…
問題 黒板に二行に数字を書く。 最初、上の行に0, 下の行に1を書いた後で次の操作を繰り返す。 Tの操作 上の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 Bの操作 下の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 これをn回行った…
問題 長さnの英小文字からなる文字列が与えられる。 この文字列の(必ずしも連続しない)部分文字列で、長さがちょうど100の回文は存在するか。 存在するならそれをどれか一つ、存在しないなら、部分文字列の回文のうち最も長いものをどれか一つ出力せよ。 …
問題 n個の数列a[i]を互いに素な二つのグループにわける。片方が空であってもよい。 f(i, j)を、i, jが違うグループのときa[i] + a[j] + h, 同じグループのときa[i] + a[j]とする。max{f(i, j) | 1≦i<j≦n} - min{f(i, j) | 1≦i<j≦n}が最小となるようなわけ…
問題 nxmの方眼紙がある。 方眼紙には1x1刻みで縦線と横線が引かれている。 (ふちに線はひかれていないものとする) この用紙を使って二人が次のようなゲームをする。 二人が交互に手番をもつ。 手番のプレイヤーは、格子点と格子点を結ぶ、水平または垂直…
問題 nxm行列がlovelyであるとは、行列の各行がそれぞれ単調非減少数列になっていることを言う。 今、lovelyだった行列の要素をいくつか-1に変え、 列をいくつか入れ替えた行列が与えられる。 元の行列としてありうるものをどれか一つ求め、 元の行列のi番目…
問題 それぞれの頂点の次数が3以下の無向グラフが与えられる。 このグラフの頂点を0か1の色に塗り分けて、 すべての頂点について、その頂点につながる同じ色の頂点の数を1つ以下にしたい。 そのような塗り方を具体的に一つ求めよ。 不可能な場合は-1を返せ。…
問題 nxm行列aijが与えられる。 この行列に対して、 どれか一つの列を選びその列の項全ての正負を反転させる どれか一つの行を選びその行の項全ての正負を反転させる 操作を好きなだけ行い、 全ての行について、その行の項の和が0以上 全ての列について、そ…
問題 n頂点m辺からなる無向グラフが与えられる。 また、整数kが与えられる。 グラフは、すべての頂点の次数がk以上である。 このグラフの長さk+1以上の閉路をどれかひとつ出力せよ。 答えが存在することは保証されている。 制約条件 n≦10^5 m≦10^5
問題 円周上に1〜nの数が並んでいる。 隣り合う数同士および、二つ隣の数同士が弧で結ばれている。 今、弧がどの数字とどの数字を結んでいるかが与えられる。 このとき、円周上に元の数字がどのような順で並んでいたかを復元せよ。 答えが複数ある場合はどれ…
問題 n枚のカードがあり、それぞれには1以上l以下の整数一つが書かれている。 このカードに対して以下の操作を繰り返す。 右端の二枚のカードを取り、書かれている数字をa, bとするとき、 二枚のカードをa - bの数字の書かれたカード一枚に置き換える。 (新…
問題 分数が次のような形で与えられる。 n個の自然数で分子が与えられる。分子は、それらの数すべての積である。 m個の自然数で分母が与えられる。分母は、それらの数すべての積である。 分数を、通分し、元の形式で出力せよ。 すなわち、 それらの積が分子…
問題 n頂点m辺からなる無向二部グラフが与えられる。 このグラフの頂点をちょうどk色で、それぞれの色が3回ずつ現れるように彩色したい。 そのような彩色は可能であるか、不可能ならNOを、 可能ならYESおよび、解を具体的に一つ出力せよ。 制約条件 n, m≦10^5
問題 n人の人がいて、それぞれのスキルはa[i]である。 全員をちょうど二つのチームに振り分けたい。 チーム分けは、 人数の差が1以下 チームの全員のスキルの和の差が、最も高いスキルを持つ人のスキル以下 という条件を満たすように行う。 正しいチームわけ…
問題 n人がいて、それぞれの人は1以上50000以下の整数のお金を持っている。 n人を先頭から見ていったとき、 「直前の人よりもお金を多く持っている人」がa人 「今までの人の持っているお金の合計よりも多くお金を持っている人」がb人いた。 (ただし、後者に…
解をどれか一つタグを追加。 ロシアっぽい(?) 問題 列にn人が並んでいる。 それぞれの人の、「自分の前にいて、自分より身長が高い人の数」a[i]が与えられる。 元の列としてありうるものをどれか一つ出力せよ。 制約条件 n≦3000