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$ の線分上の題意を満たす点がいくつあるかを計算した.
(以下のコードでは,互いに一次独立という制約を見逃しています)
#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: 2024年03月19日14時03分13秒
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)