問題 n頂点m辺からなる重みつき無向グラフが与えられる。 これらのうち、i番目の辺(s[i], t[i])を使わないで作った最小全域木の重みを 全てのiについて求めよ。 制約条件 n≦100000 m≦200000 重みは0以上10^6以下の整数

問題 n個の場所が、向きのないゲレンデによってつながっている。 つながっている箇所はroad[i][j], road[j][i]がYになっている。 それぞれの場所には高さがあり、i番目の高さ≧j番目の高さのとき、 iからjに移動することができる。 今、0番目の場所からn-1番…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp13Day3&pid=E） 制約条件 n≦100 m≦5000

問題 座標平面上にn個の点がある。 このn個の点を以下の条件を満たす辺でつなぎたい。 辺はy[i] > y[j]であるときに限りiからjに張ることができる 全ての点は連結である 全ての点の入次数は1以下、出次数は2以下 辺の長さの和が最小になる このとき、辺の長…

問題 hxwマスのグリッドがある。 一番上の列と下の列はループしてつながっていて、 右端と左端もループしてつながっている。 それぞれのマスには上下左右いずれかの向きの矢印が書かれている。 一点からスタートした人は、その矢印に従って移動することを繰…

問題 n個の都市があり、そのうち0番からm - 1番のm個の都市は特別な都市である。 これらの都市をk本の道で以下の条件を満たすように接続したい。 条件を満たす接続方法をmod 10^9 + 7で求めよ。 一つの道路は異なる二つの都市を結ぶ ひとつの二つの都市のペ…

問題 n頂点からなる無向木が与えられる。 頂点iには数字v[i]が書かれている。 この木に対して次の操作を好きなだけ行うことができる。 頂点1を含む部分木を選び、その頂点全ての数字を+1する 頂点1を含む部分木を選び、その頂点全ての数字を-1する 全ての頂…

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

問題 n頂点からなる無向グラフが与えられる。 頂点には重みa[i]がついている。 このグラフの大きさ2*n/3以上のクリークで、 重みの和が最大になるものにおける、重みの和を求めよ。 クリークが存在しないとき、-1を返せ。 制約条件 n≦50 a[i]≦100000

問題 有向グラフが与えられる。 0番の頂点から出発して、 枝の出ている頂点のうち、もっとも番号の小さい頂点に移動することを繰り返す。 この移動で、n-1番の頂点にいけるように、 枝を好きに削除することができる。 削除しなければならない枝の本数の最小…

問題 少女がn人いて、i番目の少女がj番目の少女を愛しているかのグラフが与えられる。 グラフは対称ではない。 このグラフに対して以下の操作を好きなだけ行うことができる。 初期状態で、全ての少女は魔法少女ではなく、護られている少女ではない。 魔法少…

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

問題 木が与えられる。 この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。 塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。 ただし、それぞれのノードに新たに追加できる辺は、 1本目は無料で、2本目以降は1ずつ…

問題 n頂点m辺からなる無向グラフが与えられる。 n頂点からなる完全グラフのうち、m辺をAliceが、 のこりの辺をBobが取る。 Aliceのグラフ中の三角形の数と、 Bobのグラフ中の三角形の数の和を求めよ。 制約条件 n, m≦10^6

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

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

問題 滑り台とは、座標平面上のn個の支点と、m本のパスであって、 パスは、異なる二つの支点をつないだ線分である。 滑り台のパスは交差していてはならない。 今、支点の数nと、支点と支点をつなぐパスm本が与えられる。 このパスのうち、いくつかを取り除い…

問題 日本語なので本文参照（http://arc010.contest.atcoder.jp/tasks/arc010_4） 座標平面上に味方n人と敵m人がいる。 それぞれの座標が与えられる。 味方は、自分から最も近い敵よりも、厳密に近くにいる味方全員に情報を伝えられる。 味方全員に情報を伝…

問題 日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_05） 閉路を高々1つ含む、重みつき無向グラフが与えられる。 このグラフの辺をいくつか切断して、グラフがk個以上の連結成分に分かれるようにしたい。切断する辺の重みの和の最小…

問題 家計図が与えられる。 家計図は、(名前、その人の親）の情報がn個与えられることにより与えられる。 この家計図に対して、次のようなq個のクエリに答えよ。 クエリ： 人v[i]の、ちょうどk代目の子孫のうち、異なる名前の数を答える。 制約条件 n≦10^5 q…

問題 座標平面上に円がいくつかある。 i番目の円の中心は(x[i], y[i])で、半径はr[i]. 円同士が共有点を持つことはない。（ある円がある円の内部にあることはある） AliceとBobが次のようなゲームをする。 Aliceが先手。交互に手番をもつ。 手番のプレイヤー…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575） 制約条件 N, Q≦100000 M≦200000 K≦N

問題 根付き木が与えられる。 それぞれの頂点には重みがついている。 今、この木からちょうどk個の頂点{a1, a2, ..., ak}を選ぶ。 ここで、i != jなる任意の1≦i, j≦kについて、aiがajの先祖であってはならない。 このとき、選んだ頂点の重みの和の最大値を求…

問題 木が与えられる。 この木と同じ頂点数で、葉以外の頂点の子は必ず一つまたは二つで、 なるべく平衡しているような木で、余った葉はなるべく左側から埋められている木を考える。 この木に、与えられた木を対応させる方法は何通りあるか、求めよ。 制約条…

問題 n人の人が平面上にいて、それぞれの座標が与えられる。 これらの人が、合計でm個、次のような目撃証言をした。 「私は、a[i]がb[i]よりも先に銃を撃つのを聞いた」 音の進む速さは有限であるので、 先に銃を撃つ音が聞こえた者が、先に発砲したとは限ら…

問題 n人が参加した大会がある。 大会は2種目の得点の合計が多い人が良い順位になり、 同点の場合は、同点の間でどの順位にもなる可能性がある。 1番目の種目と2番目の種目の得点が順不同で与えられる。 自分はこの中のどれかで、合計がx点以上であることが…

問題 長さnの順列（1〜nの数の並び替え）を、 4回適用した順列P^4が与えられる。 このとき、Pとしてありうる順列は何通りか、求めよ。 制約条件 n≦700くらい

問題 n個の正の整数S[i]が与えられる。 この整数から、部分集合sを、sのどの二つの要素も互いに素であるように選びたい。 sの要素の数の最大値はいくつか、求めよ。 制約条件 S[i]≦100 S[i]は互いに異なる n≦50

問題 二つの異なる数字が書かれたドミノがいくつかある。 このドミノを全て使って、全体がちょうどいくつかの輪になるように並べる。 ドミノが輪になっているとは、 左右に隣合うドミノの、隣り合う側の数字がすべて等しく、 かつ、最初のドミノと最後のドミ…

問題 いくつかのwebサイトのリンクの関係が与えられる。 websiterankとは次のような値である。 最初、全てのサイトの値は1. サイトAからサイトBへリンクがあるとき、サイトBの値にサイトAの値を足す。 ただし、サイトBからサイトAへ直接、または間接的にリン…