解をどれか一つ

Codeforces 356(#207 Div1) D. Bags and Coins

問題 n枚の袋があって、i番目の袋の中にはa[i]枚のコインが入っている。コインは全体でs枚である。 ただし、袋の中にはさらに別の袋が入っていることがある。 a[i] = {1, 1, 3}で、全体でコインが3枚ということがある。 (3番目の袋には1番目の袋と2番目の袋…

Codeforces 467(#267 Div2) E. Alex and Complicated Task

問題 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

Codeforces 369(#216 Div2 only) B. Valera and Contest

問題 n人がコンテストをした。全員l以上r以下の整数の得点を取った。 全員の得点の合計はsall点。上位k人の得点の合計はsk点である。 このような条件を満たす全員の得点の取り方をどれか一通り出力せよ。 解が存在することは保証されている。 制約条件 n, l,…

Codeforces 388(#228 Div1) B. Fox and Minimal path

問題 無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。 答えが複数ある場合はどれを出力してもよい。 制約条件 解の存在は保証されている。

Codeforces 394(#231 Div1) C. Dominoes

問題 10, 11, 00のドミノが合計でn*m個与えられる。 これらを横向きにn*m個に並べる。 それぞれの列ごとにその列の数の和を求める。 この和の最大値が、最小になるようにしたい。最小値を求めよ。 ドミノは回転させることはできるが、縦に使うことはできない…

Codeforces 339E Three Swaps

問題 長さがnの数列 1 2 3 4 ... n-1 nがある。 この数列に対して3回以下、以下のような操作を行った。 l, rを選びaの区間[l, r]の順番を反転させる。 結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。 制約条件 n≦1000

Codeforces 339C Xenia and Weights

新環境のテストも兼ねて出てました。がDの誤読で酷いことになった。 問題 1〜10までの重さの錘のうち、使うことができる種類のものが与えられる。 個数に制限はなく、無限に使える。 これをm回天秤に以下のルールで乗せる。 交互に違う皿に置く。 2回連続で…

Codeforces 321C Ciel the Commander

問題 n頂点からなる木が与えられる。 木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。 同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも 小さいアルファベットのラベルを持つ…

Codeforces 217B Blackboard Fibonacci

問題 黒板に二行に数字を書く。 最初、上の行に0, 下の行に1を書いた後で次の操作を繰り返す。 Tの操作 上の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 Bの操作 下の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 これをn回行った…

Codeforces 335B Palindrome

問題 長さnの英小文字からなる文字列が与えられる。 この文字列の(必ずしも連続しない)部分文字列で、長さがちょうど100の回文は存在するか。 存在するならそれをどれか一つ、存在しないなら、部分文字列の回文のうち最も長いものをどれか一つ出力せよ。 …

Codeforces 238B Boring Partition

問題 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}が最小となるようなわけ…

Codeforces 277C (170C) Game

問題 nxmの方眼紙がある。 方眼紙には1x1刻みで縦線と横線が引かれている。 (ふちに線はひかれていないものとする) この用紙を使って二人が次のようなゲームをする。 二人が交互に手番をもつ。 手番のプレイヤーは、格子点と格子点を結ぶ、水平または垂直…

Codeforces 274D (168D) Lovely Matrix

問題 nxm行列がlovelyであるとは、行列の各行がそれぞれ単調非減少数列になっていることを言う。 今、lovelyだった行列の要素をいくつか-1に変え、 列をいくつか入れ替えた行列が与えられる。 元の行列としてありうるものをどれか一つ求め、 元の行列のi番目…

Codeforces 167C (273C) Dima and Horses

問題 それぞれの頂点の次数が3以下の無向グラフが与えられる。 このグラフの頂点を0か1の色に塗り分けて、 すべての頂点について、その頂点につながる同じ色の頂点の数を1つ以下にしたい。 そのような塗り方を具体的に一つ求めよ。 不可能な場合は-1を返せ。…

Codeforces 226D (140D) The table

問題 nxm行列aijが与えられる。 この行列に対して、 どれか一つの列を選びその列の項全ての正負を反転させる どれか一つの行を選びその行の項全ての正負を反転させる 操作を好きなだけ行い、 全ての行について、その行の項の和が0以上 全ての列について、そ…

Codeforces 161D (263D) Cycle in Graph

問題 n頂点m辺からなる無向グラフが与えられる。 また、整数kが与えられる。 グラフは、すべての頂点の次数がk以上である。 このグラフの長さk+1以上の閉路をどれかひとつ出力せよ。 答えが存在することは保証されている。 制約条件 n≦10^5 m≦10^5

Codeforces 161C (263C) Circle of Numbers

問題 円周上に1〜nの数が並んでいる。 隣り合う数同士および、二つ隣の数同士が弧で結ばれている。 今、弧がどの数字とどの数字を結んでいるかが与えられる。 このとき、円周上に元の数字がどのような順で並んでいたかを復元せよ。 答えが複数ある場合はどれ…

Codeforces 231 B. Magic, Wizardry and Wonders

問題 n枚のカードがあり、それぞれには1以上l以下の整数一つが書かれている。 このカードに対して以下の操作を繰り返す。 右端の二枚のカードを取り、書かれている数字をa, bとするとき、 二枚のカードをa - bの数字の書かれたカード一枚に置き換える。 (新…

Codeforces 222 C. Reducing Fractions

問題 分数が次のような形で与えられる。 n個の自然数で分子が与えられる。分子は、それらの数すべての積である。 m個の自然数で分母が与えられる。分母は、それらの数すべての積である。 分数を、通分し、元の形式で出力せよ。 すなわち、 それらの積が分子…

Codeforces 173 D. Deputies

問題 n頂点m辺からなる無向二部グラフが与えられる。 このグラフの頂点をちょうどk色で、それぞれの色が3回ずつ現れるように彩色したい。 そのような彩色は可能であるか、不可能ならNOを、 可能ならYESおよび、解を具体的に一つ出力せよ。 制約条件 n, m≦10^5

Codeforces 149 C. Division into Teams

問題 n人の人がいて、それぞれのスキルはa[i]である。 全員をちょうど二つのチームに振り分けたい。 チーム分けは、 人数の差が1以下 チームの全員のスキルの和の差が、最も高いスキルを持つ人のスキル以下 という条件を満たすように行う。 正しいチームわけ…

Codeforces 148C. Terse princess

問題 n人がいて、それぞれの人は1以上50000以下の整数のお金を持っている。 n人を先頭から見ていったとき、 「直前の人よりもお金を多く持っている人」がa人 「今までの人の持っているお金の合計よりも多くお金を持っている人」がb人いた。 (ただし、後者に…

Codeforces 141 C. Queue

解をどれか一つタグを追加。 ロシアっぽい(?) 問題 列にn人が並んでいる。 それぞれの人の、「自分の前にいて、自分より身長が高い人の数」a[i]が与えられる。 元の列としてありうるものをどれか一つ出力せよ。 制約条件 n≦3000