Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

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以下

コード

続きを読む