問題 座標平面上に白い点がn個、黒い点がm個与えられる。 これらの点から異なる4点を選び、checkerな四角形を作ることができるならば、NOを、 作ることができないならばYESを答えよ。 ただし、checkerな四角形とは、白い点、黒い点、白い点、黒い点を順に結…

問題 それぞれに1つの数字が書かれたn枚のカードがあり、i番目のカードの数字はdigits[i]で表される。 1枚目のカードをまずテーブルに置き、2枚目以降のカードを次のようにおく。 今までに置いたカード全部よりも右側に置く。 今までに置いたカード全部より…

問題 n枚のカードが一列に並んでいる。 カードにはlevel, damageが設定されており、i番目のカードのlevelはlevel[i], ダメージはdamage[i]である。 このカードに対して次の操作のどちらかを行う。 1. 先頭のカードを末尾へ移動する。 2. 先頭のカードの右に…

問題 二人のプレイヤーがn個の山を使って次のようなゲームをする。 手番のプレイヤーは、山をひとつ選ぶ。 この山の石の数をXとする。Xより小さいXの約数Yを選び、この山の石の数をYに変える。 操作のできなくなったプレイヤーの負け 最初の山のうち[A, B]の…

問題 r個の赤の球、g個の緑の球、b個の青の球がある。 この球を以下の手順を繰り返して並べる。 赤があれば赤の球を並べる。 緑があれば緑の球を並べる。 青があれば青の球を並べる。 （最初に戻る） r + g + b = nであり、k番目に並べた球は赤い球だったこ…

問題 w x hのチェス番がある。 好きなマスにナイトを置いて、自由に動かす。 同じマスを何回通ってもよい。このとき、ナイトが一度以上行けたマスの数は最大でいくつになるか、求めよ。 制約条件 w, h≦45000

問題 xor b[i] = nとなるような数列b[i]は何通りあるか求めよ。 （ただし、b[i]はそれぞれ0≦b[i]≦cards[i]を満たす整数） 制約条件 cardsの要素の数≦50 n≦10^9 b[i]≦10^9

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0237） 二等辺三角形が座標平面上にn個ある。 触れると、底辺から、長さdの光の長方形が出る。 光の長方形に触れた（共有点をもった）別の三角形は、連鎖的に同様に光…

問題 日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_08） 制約条件 駅の数≦100000 電車の台数≦200

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

問題 n x nの行列がある。 それぞれの成分はスイッチで、ONかOFFの状態をとる。 1秒ごとに、ONに隣接するOFFのスイッチはONになる。 最初、(x, y)のスイッチだけがONのとき、オンになっているスイッチがc個以上になるには何秒かかるか、求めよ。 制約条件 n≦…

問題 n個のコインの山があり、それぞれa[i]枚のコインが積まれている。 この山を使って二人が次のようなゲームをする。 交互に手番をもつ。手番に操作のできなくなったプレイヤーが負け。 手番のプレイヤーは山をひとつ選ぶ。この山のコインの数をxとする。 …

問題 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_07） 次のようなクエリm個に答える。 高さhのだるまを、一番上に重ねる。 高さyの場所をハンマーで叩く。 このとき、ハンマーがあたらないならmiss, 複数のだるまに当たるならstop…

問題 日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_06） 制約条件 N, M≦100 L≦100

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

問題 日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_04） 制約条件 Ni≦10^9

問題 平面上に黒い点がn個、白い点がm個与えられる。 これらの点は、どの3点も同一直線上にはない。 黒い点、白い点、黒い点、白い点と、色違いの点を交互に結んで出来る、 凸な四角形が一つでも存在するならば"NO"を、存在しないならば"YES"を出力せよ。 制…

問題 日本語なので本文参照（http://www.utpc.jp/2011/） N頂点からなる木が与えられる。 i番目の頂点には数字x[i]が書かれている。 この木に対して次のようなQ個のクエリに答えよ。 クエリ：頂点v[i]からw[i]へのパス上に書かれている数字のうち、l[i]番目…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508） RMQに、値の変更および、[l, r]の部分を巡回シフトさせるクエリが飛んでくる。 制約条件 n≦2 * 10^5 q≦2 * 10^5

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

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

年齢制限のため、今年が僕の最後のICPCでした。 東京大学、チームwakabaで参加しました。 結果は4位でした。 元々僕は、プロコンの界隈にICPCから入ったので、 ICPCは原点であり、ICPCで世界大会に行くことが最終目標でもありました。 その最終目標こそ達成…

問題 日本語なので本文参照（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の先祖であってはならない。 このとき、選んだ頂点の重みの和の最大値を求…

ソースコード 何故通らない。 ll n; int m, a[20]; map<ll, int> dp; int rec(ll n){ if(dp.count(n)) return dp[n]; if(n == 1) return dp[n] = 0; dp[n] = inf; rep(i, m) if(n % a[i] == 0){ dp[n] = min(dp[n], rec(n / a[i]) + 1); } return dp[n]; } int main()</ll,>…

問題 全ての要素がA以上B以下の整数であるような集合のうち、 要素を小さい順に並べた列と、要素を辞書順に並べた列が一致するものの個数を、 mod Pで求めよ。 制約条件 A, B, P ≦10^9 B - A ≦ 100000

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

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

問題 英小文字からなる文字列sが与えられる。 この文字列に対して、以下のようなクエリをm個実行する。 入力l, rを受け取る。 sのl文字目からr文字目を、その部分が回文になるように並び替える。 回文が複数個できる場合は、辞書順で最小になるように並び替…