Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-07-01

[][] Google Code Jam Round3 Problem D small 01:36 はてなブックマーク -  Google Code Jam Round3 Problem D small  - 練習帳

問題文

 問題文

概要

  • 文字列sが与えられている.長さnで次の条件を満たす文字列が存在するような数nのうち,最小のものを答えよ.
  • 条件:文字列が,文字列sの「2-gram」及び「2-gramの一部分をleet変換して出来るすべての候補」を全て含む.
    • 文字列のN-グラムとは,長さNの部分列の事.例えば「abca」なら「ab」「bc」「ca」
    • leet変換とは特定のアルファベットを形の似ている数字や記号に変換する事.例えば「google」→「g00gle」など.この問題では,"o" → "0", "i" → "1", "e" → "3", "a" → "4", "s" → "5", "t" → "7", "b" → "8" "g" → "9"のleet変換のみ考える.
  • 制限:sの長さは1000以下

コード

続きを読む

2012-06-24

[][] TopCoder TCO Round 2C Level2 (500) ThreePoints 20:09 はてなブックマーク -  TopCoder TCO Round 2C Level2 (500) ThreePoints - 練習帳

問題文

 問題文

概要

  • 2次元平面上にn点が与えられている。
    • どの2点をとってもx座標は等しくない。また、どの2点をとってもy座標は等しくない。
  • 次の条件を満たす3点の組(A, B, C)の個数を答えよ:条件「A[x] < B[x] < C[x]かつA[y] < C[y] < B[y]、ここでP[x], P[y]はそれぞれ点Pのx, y座標を表す」
  • 制限:n ≦ 300000, 点のx, y座標は0以上10**9未満の整数値

コード

続きを読む

2012-06-04

[][] TopCoder SRM 543 Div.1 Level2 (500) EllysRivers 00:01 はてなブックマーク -  TopCoder SRM 543 Div.1 Level2 (500) EllysRivers - 練習帳

問題文

 問題文

概要

  • 複数の川が平行に並んでいて、川と川の間には直線の道路がある。川の幅は川ごとに異なる。
    • つまり2次元座標を適当に置くと、川はy軸に平行な帯状領域で、道路はy軸に平行な直線と思える。以降この座標系を用いる
  • 川と道路を移動する事で、左下のスタート地点(0, 0)から右上のゴール地点(W, L)まで移動したい。そのために要する最短時間を求めよ。
  • 川内では自由な方向に移動できるが、道路は細いためy軸方向のみ移動できる。
    • 道路を移動する速度はすべての道路で共通だが、川内を移動する速度は川ごとに異なる。
  • 川から道路への移動と道路から川への移動はy座標が整数の点でのみ行える。
    • スタート、ゴール地点は共に道路上の点
  • 制限:
    • 川の数(以下ではNと書く)は50以下、川と道路での移動速度は10**6以下、それぞれの川の幅は10**6以下でL, Wは整数で10**6以下

コード

続きを読む

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秒以内

コード

続きを読む