ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1076 Time Manipulation

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076


・概要
問題文が日本語なので省略。


・解法
・パターン①
包除原理を用います。

この問題は蟻本や他の方々のコードを参考にしながら解きました。

ベン図が奇数個重なってる時はプラス、偶数個重なってる時はマイナスです。
図で表すとこんな感じです↓(作図能力ゼロ)

左の図は、 |A ∪ B| = |A| + |B| − |A ∩ B|
右の図は、 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|

上の図と式からわかるように、プラスしたり、マイナスしたり。。。


・パターン②
最初はなんでこれで通るのかわからなかったのですが、あの偉大なlaycurse先生に教えていただきました。ありがとうございます。 以下は教えていただいた解法。

p[i]はnを割り切るので,n年は必ず使えない.kがp[i]の倍数なら,n-kもp[i]の倍数なので,使えない年数はn/2について対称になっている.なので使える年が1個でもあれば期待値はn/2です.

いやぁー、難しいですね。(ちゃんと理解できてない)


ソースコード

#include<iostream>
#include<cstdio>
using namespace std;

typedef long long ll;

ll sum(ll n){
   return n*(n+1)/2;
}

ll gcd(ll a, ll b){
   if(b==0)return a;
   else return gcd(b, a%b);
}

ll lcm(ll a, ll b){
   return a / gcd(a,b) * b;
} 

int main(){
   int n,m;
   int p[20];
   while(cin >> n >> m){
      if(n==0 && m==0)break;

      ll N = sum(n);
      ll D = n;
      
      for(int i = 0 ; i < m ; i++)cin >> p[i];
      
      //包除原理
      for(ll i = 1 ; i < (1 << m) ; i++){ //ベン図でどの部分を指しているか
	 int num = 0;
	 ll tmp = 1; //最小公倍数
	 for(int j = 0 ; j < m ; j++){
	    if(i & (1 << j)){
	       num++;
	       tmp = lcm(tmp, p[j]);
	    }
	 }

	 if(num%2==1){
	    N -= tmp * sum(n / tmp);
	    D -= n / tmp;
	 }
	 else{
	    N += tmp * sum(n / tmp);
	    D += n / tmp;
	 }
      }
      
      double ans = (D!=0) ? N/(double)D : 0.0;
      printf("%.10f\n",ans);
   }
   return 0;
}

ソースコード

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main(){
   int n,m;
   int p[20];
   while(cin >> n >> m){
      if(n==0 && m==0)break;

      for(int i = 0 ; i < m ; i++)cin >> p[i];
      sort(p,p+m);
      
      double ans = (p[0]==1) ? 0.0 : n/2.0;
      printf("%.10f\n",ans);
   }
   return 0;
}