Codeforces Round 218(Div.2 Only) A K-Periodic Array
問題
長さnの、各要素がすべて1か2の配列aが与えられます。(nはkで割り切れます)
K-Periodic Arrayとは、aをK個ごとに区切った時に同じ配列の繰り返しになる配列のことです。
[1,2,1,2,1,2]は2-periodic、
[1,2,1,1,2,1]は3-periodicです。
配列aがk-periodicになるために配列の各要素を入れ替えるとしたら、変える要素の個数は最少でいくらになるでしょう。
制約
1≦k≦n≦100
n%k==0
a[i]==1 || a[i]==2 for 0≦i<n
解法
k-periodicとは、
a[i]==a[k+i]==a[k*2+i]==...(0≦i<k)
という状態の配列だといえます。
ということで、元の配列をk個のグループに分けて各グループの中の1,2の個数を調べて、
少ない方を多い方に変える、というのが最少変更になります。
プログラム
#include<iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #define _USE_MATH_DEFINES #include <math.h> #include<string> #include<vector> #include<cmath> #include<stack> #include<queue> #include<sstream> #include<algorithm> #include<map> #include<complex> #include<ctime> #include<set> using namespace std; #define li long long int #define rep(i,to) for(li i=0;i<((li)(to));i++) #define repp(i,start,to) for(li i=(li)(start);i<((li)(to));i++) #define pb push_back #define sz(v) ((li)(v).size()) #define bgn(v) ((v).begin()) #define eend(v) ((v).end()) #define allof(v) (v).begin(), (v).end() #define dodp(v,n) memset(v,(li)n,sizeof(v)) #define bit(n) (1ll<<(li)(n)) #define mp(a,b) make_pair(a,b) #define rin rep(i,n) #define EPS 1e-10 #define ETOL 1e-8 #define MOD 100000000 #define F first #define S second #define p2(a,b) cout<<a<<"\t"<<b<<endl #define p3(a,b,c) cout<<a<<"\t"<<b<<"\t"<<c<<endl li a[1000]; li a1[1000], a2[1000]; int main(){ li n,k; cin>>n>>k; rin{cin>>a[i];} rep(i,k){ a1[i]=a2[i]=0; } rep(i,n/k){ rep(j,k){ if(a[i*k+j]==1)a1[j]++; else a2[j]++; } } li res=0; rep(i,k){ res+=min(a1[i], a2[i]); } cout<<res<<endl; return 0; }