Yandex.Algorithm 2014 Round 2 E問題 - Points

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 2
問題文

問題概要

$2$ 次元の $3$ つのベクトル $A=(A_x,A_y), B=(B_x,B_y), A=(C_x,C_y)$ が与えられる.
正整数 $N$ が与えられるので,
  $p = \alpha A + \beta B + \gamma C, \;\; 0 \leq \alpha, \beta, \gamma < N$,$\alpha, \beta \gamma$ は整数
と言う形で表されるベクトル $p$ はいくつ存在するかを求める問題.

解法

傾きが $A, B, C$ の順番に高くなるようにソートしておく.
$j B = i A + k C$ となるような最小の $i, j, k > 0$ を尺取法により計算する.
これは,左辺のベクトルの方が短ければ $j$ を $1$ 増やし,右辺のベクトルのほうが短ければ,傾きが $B$ に近づく方を $i,k$ から選びそちらを $1$ つ増やす,というのを両辺が一致するまで行えば良い.
後は,それぞれの $0 \leq m, n < N$ に対して,$mA + nC$ と $(m+i)A + (n+k)C$ の線分上の題意を満たす点がいくつあるかを計算した.
(以下のコードでは,互いに一次独立という制約を見逃しています)

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}
int LCM(int a,int b){return a/GCD(a,b)*b;}

int N, A[2], B[2], C[2];

int is_same_line(int a[], int b[]){
  int i, j;

  i = GCD(a[0], a[1]);
  j = GCD(b[0], b[1]);

  if(a[0]/i != b[0]/j) return 0;
  if(a[1]/i != b[1]/j) return 0;
  return 1;
}

ll solve_line(int k, int val[]){
  int i, j;
  ll res = 0;

  rep(i,2000001){
    rep(j,k){
      if(i%val[j]==0 && i/val[j]<N){ res++; break; }
    }
  }

  return res;
}

double dist(double dx, double dy){
  return dx*dx + dy*dy;
}

int main(){
  int i, j, k;
  int x1, y1, x2, y2;
  int ii, jj, kk;
  ll res, tmp;
  int val[4];
  double da, db, dc;

  reader(&N);
  reader(A, A+1);
  reader(B, B+1);
  reader(C, C+1);

  if(is_same_line(A,B) && is_same_line(A,C)){
    val[0] = A[0];
    val[1] = B[0];
    val[2] = C[0];
    res = solve_line(3, val);
  } else if(is_same_line(A,B)){
    val[0] = A[0];
    val[1] = B[0];
    res = solve_line(2, val) * N;
  } else if(is_same_line(A,C)){
    val[0] = A[0];
    val[1] = C[0];
    res = solve_line(2, val) * N;
  } else if(is_same_line(B,C)){
    val[0] = B[0];
    val[1] = C[0];
    res = solve_line(2, val) * N;
  } else {
    da = A[0] / (double) A[1];
    db = B[0] / (double) B[1];
    dc = C[0] / (double) C[1];

    rep(i,3){
      if(da > db) swap(da, db), swap(A[0], B[0]), swap(A[1], B[1]);
      if(db > dc) swap(db, dc), swap(B[0], C[0]), swap(B[1], C[1]);
    }

    x1 = y1 = 0;
    x2 = B[0]; y2 = B[1];
    i = 0; j = 1; k = 0;
    while(x1 != x2 || y1 != y2){
      if(i >= N || j >= N || k >= N) break;
      if(dist(x1,y1) < dist(x2,y2)){
        if(y1 && x1/(double)y1 > db){
          i++;
          x1 += A[0];
          y1 += A[1];
        } else {
          k++;
          x1 += C[0];
          y1 += C[1];
        }
      } else {
        j++;
        x2 += B[0];
        y2 += B[1];
      }
    }

    if(i==0) i++;
    if(j==0) j++;
    if(k==0) k++;
    res = 0;
    rep(ii,N) rep(kk,N){
      tmp = N - min((N-1)/j, min((N-ii-1)/i, (N-kk-1)/k));
      if(i+ii<N && k+kk<N && j<N) tmp = j;
      res += tmp;
    }
  }

  writer(res, '\n');

  return 0;
}

Current time: 2017年09月25日07時43分55秒
Last modified: 2014年08月06日01時30分47秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round2
トップページに戻る

Logged in as: unknown user (not login)

ログイン: