2012-11-01から1ヶ月間の記事一覧
問題 日本語なので本文参照(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