Yandex.Algorithm 2014 Round 2 F問題 - Permutation Cube

Source

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

問題概要

整数 $1$ から $N$ の置換 $X,Y,Z$ が与えられる．
次のいずれかの移動1～2.ができる．

  1. コスト $1$ を支払って，好きな場所 $(i,j,k)$ に移動する．$(1 \leq i,j,k \leq N)$
  2. 現在 $(i,j,k)$ にいるのならば，コスト $0$ で $(X_i,Y_j,Z_k)$ に移動する

最初はどこにもおらず，移動方法1でどこかに移動しなければいけない．
$N^3$ 個の点 $(i,j,k), \;\; 1 \leq i,j,k \leq N$ 全てに訪れるための最小コストを求める問題．

解法

$X, Y, Z$ をそれぞれ循環置換の積で書きなおす．
それぞれ長さ $l_x, l_y, l_z$ の巡回置換に対応するセル（場所）の部分を考える．
そのようなセルの数は $l_x l_y l_z$ 個で，一度そのような場所に行くと，コスト $0$ の移動で，${\rm LCM}(l_x, l_y, l_z)$ 個のセルを訪れることができる．
よって，そのような循環置換に対応するセルを全て訪れるにはコスト $l_x l_y l_z / {\rm LCM}(l_x, l_y, l_z)$ かかるので，これの和を求める．
それぞれの置換について，長さが同じ循環置換はまとめて処理すると，長さが異なる循環置換は高々 $O(\sqrt{N})$ 個なので，時間計算量 $O(N^{1.5} \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

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 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);}

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


int N;

int mem[50000], vis[50000];
int len[50000], num[50000], sz;
int X[50000], nX[50000], Xs;
int Y[50000], nY[50000], Ys;
int Z[50000], nZ[50000], Zs;

void read_perm(void){
  int i, j, k;
  
  rep(i,N) reader(mem+i), mem[i]--;
  rep(i,N) vis[i] = 0;
  
  sz = 0;
  rep(i,N) if(vis[i]==0){
    len[sz] = 0;
    k = i;
    while(vis[k]==0){
      vis[k] = 1;
      len[sz]++;
      k = mem[k];
    }
    sz++;
  }

  sort(len, len+sz);
  k = 0;
  rep(i,sz){
    if(k && len[k-1] == len[i]){ num[k-1]++; continue; }
    len[k] = len[i];
    num[k] = 1;
    k++;
  }
  sz = k;
}

int main(){
  int i, j, k;
  ll res = 0, mul, lcm, mul2, lcm2;

  reader(&N);

  read_perm();
  Xs = sz; rep(i,sz) X[i] = len[i], nX[i] = num[i];
  read_perm();
  Ys = sz; rep(i,sz) Y[i] = len[i], nY[i] = num[i];
  read_perm();
  Zs = sz; rep(i,sz) Z[i] = len[i], nZ[i] = num[i];

  rep(i,Xs) rep(j,Ys){
    mul = X[i] * (ll)Y[j];
    lcm = LCM(X[i], Y[j]);
    rep(k,Zs){
      mul2 = mul * Z[k];
      lcm2 = LCM(lcm, Z[k]);
      res += mul2 / lcm2 * nX[i] * nY[j] * nZ[k];
    }
  }

  writer(res, '\n');

  return 0;
}

Current time: 2024年04月19日20時43分31秒
Last modified: 2014年08月06日01時14分14秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round2
トップページに戻る

Logged in as: unknown user (not login)

ログイン：