Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-05-28

[][] Codeforces Round #120 : E. Counter Attack 01:18 はてなブックマーク -  Codeforces Round #120 : E. Counter Attack - 練習帳

問題文

 問題文

概要

  • 無向グラフが与えられている。
  • このグラフの補グラフを連結成分に分解せよ。
    • グラフG=(V, E)の補グラフG'とは、節がGと同じで、枝は(v, w)∉E(v, w∈V)となるグラフのことである。つまり、もとのグラフの枝の有無を反転させたグラフのこと。
  • 条件:節:n ≦ 5*10**5、枝:m ≦ 10**6

コード

続きを読む

2012-05-20

[][] Codeforces Round #119 : C. Weak Memory 18:56 はてなブックマーク -  Codeforces Round #119 : C. Weak Memory - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている(節:n個、枝:m本)
  • グラフのうちk個の節に印がついている
  • スタート地点とゴール地点が与えられている
  • 次の条件を満たす正数qのうち、最小の値を求めよ。条件を満たすqがない場合には-1と答えよ。
    • 条件:「スタートからゴール地点への経路のうち、次の条件を満たすものが存在する。スタート地点からqステップ以内に印つきの節がある、さらにその印つきの節からqステップ以内に印つきの節がある...これを繰り返してゴール地点までたどり着ける。」
  • 制限
    • n ≦ 10**5, m ≦ 2*10**5, k ≦ n, 実行時間2秒以内

コード

続きを読む

2012-05-14

[][] Codeforces Round #118 : D. Visit of the Great 23:57 はてなブックマーク -  Codeforces Round #118 : D. Visit of the Great - 練習帳

問題文

 問題文

概要

  • クエリとして整数の四つ組(k, l, r, p)が与えられている(pは素数)
  • 各クエリに対して、LCM(k**(2**l)+1, k**(2**(l+1))+1, ..., k**(2**r)+1)をpで割ったあまりを答えよ
  • 制限
    • クエリの数は10**5個以下
    • 1 ≦ k ≦ 10**6, 0 ≦ l ≦ r ≦ 10**18; 2 ≦ p ≦ 10**9

コード

続きを読む

2012-05-06

[][] ABBYY Cup 2.0 - Hard : B. Greedy Merchants 15:32 はてなブックマーク -  ABBYY Cup 2.0 - Hard : B. Greedy Merchants - 練習帳

問題文

 問題文

概要

  • 無向連結グラフが与えられている。
  • クエリとして、スタート地点とゴール地点のペアが与えられる。
  • 各クエリに対して、「もしその枝がグラフから除かれたら、スタートからゴールまで辿り着けなくなる」という枝の本数を答えよ。
  • 制限
    • グラフの節の数:n ≦ 10**5, グラフの枝の数:m ≦ 10** 5, クエリの数:k ≦ 10**5

コード

続きを読む