HackerRank 101 Hack June'14 2問目 - Sherlock and Queries

Source

HackerRank 101 Hack June'14 2問目
problem statement(コンテストページ)
problem statement

問題概要

$N$ 要素の正整数からなる配列 $\{A_k\}_{k=1}^N$ と,$M$ 要素の正整数からなる配列 $\{B_k\}_{k=1}^M, \{C_k\}_{k=1}^M$ が与えられるので,以下のプログラムを実行した後の配列 $\{A_k\}_{k=1}^N$ の値を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

  for i = 1 to M do
    for j = 1 to N do
      if j % B[i] == 0 then
        A[j] = A[j] * C[i]
      endif
    end do
  end do

解法

もし $B_i = B_j$ なら,同じ要素のセットに対し,$C_i$ が掛けられた後 $C_j$ が掛けられることになるので,同じ $B_i$ はまとめてしまって,対応する $C_i$ の積を求めておく.
すると,$B_k$ ごとに見てやって,$i$ が $B_k$ の倍数のところに,$C_k$ を掛けていけば良い.
掛ける回数は,高々 $N/1 + N/2 + \cdots + N/N = O(N \log N)$ になって間に合う.

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
#define ull unsigned ll

#define MD 1000000007

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 reader(ll *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 writer(int x, char c){int i,sz=0,m=0;char buf[10];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);}

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int N, M;
int A[110000], B[110000], C[110000];

int main(){
  int i, j, k;

  reader(&N,&M);
  rep(i,N) reader(A+i);
  rep(i,M) reader(B+i);
  rep(i,M) reader(C+i);

  intIntSort(B, C, M);

  k = 0;
  rep(i,M){
    if(k && B[i]==B[k-1]){
      C[k-1] = (ll)C[k-1] * C[i] % MD;
    } else {
      B[k] = B[i];
      C[k] = C[i];
      k++;
    }
  }
  M = k;

  rep(i,M){
    for(j=B[i];j<=N;j+=B[i]) A[j-1] = (ll)A[j-1] * C[i] % MD;
  }

  rep(i,N) writer(A[i], i==N-1?'\n':' ');

  return 0;
}

Current time: 2017年07月21日13時34分06秒
Last modified: 2014年09月23日01時11分45秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_101jun14
トップページに戻る

Logged in as: unknown user (not login)

ログイン: