kmjp's blog

競技プログラミング参加記です

FII Code Round #2 : E. Stargazing

考え方はすぐわかるけど、割と面倒な問題。
https://csacademy.com/contest/fii-code-2019-round-2/task/stargazing/

問題

N日間空を見たところ、うちQ日について、星が見えたか見えなかったかの情報が与えられる。
星は、s日目から開始してn日毎にk回見える場合、その状態を(s,n,k)とする。
情報に合致する(s,n,k)は何通りか。

解法

まず星が見える日の差の最大公約数が求まると、nはその約数でなければならないことがわかる。
また、見える最初の日と最後の日の間にある、見えなかった日から、上記約数のうち候補から外れるものがわかる。

あとはこうして絞った約数に対し、開始日と終了日がどの区間の値を取れるか求め、掛け合わせればよい。

ll N,Q;
vector A,B,L,M,R;

int NG[7070];
ll ML[7070],MR[7070];
ll mo=1000000007;

void solve() {
int i,j,k,l,r,x,y; string s;

cin>>N>>Q;
FOR(i,Q) {
ll v;
cin>>x>>v;
if(x) A.push_back(v);
else B.push_back(v);
}

sort(ALL(A));
sort(ALL(B));
FORR(b,B) {
if(bA.back()) R.push_back(b);
}

ll f=0,g=0;
FORR(a,A) {
if(f==0) f=a;
else g=__gcd(g,a-f);
}
vector D;
map rev;
for(ll a=1;a*a<=g;a++) if(g%a==0) {
D.push_back(a);
if(a*a!=g) D.push_back(g/a);
}
sort(ALL(D));
FOR(i,D.size()) {
rev[D[i]]=i;
ML[i]=1;
MR[i]=N;
}
FORR(m,M) NG[rev[__gcd(g,m-f)]]=1;
FORR(l,L) ML[rev[__gcd(g,f-l)]]=l+1;
reverse(ALL(R));
FORR(r,R) MR[rev[__gcd(g,r-f)]]=r-1;

ll ret=0;
FOR(i,D.size()) {
for(j=i+1;j

まとめ

TL0.5sって珍しいな。
CSAって割とここ厳しいよね。