PKU 3385 Genealogy
http://poj.org/problem?id=3385
ある宇宙人が家系図を持っている。
この宇宙人にはp人以下の親しかいないはずなのに、その家系図にはpよりも多い部分がある。
矛盾しないように間に親を挟む時、最小で何人挟めばよいかを答えろというような問題。
何人の親をはさむと、直接の先祖を何人持つことが出来るかを考えました。
変なことやって1WA。
あと入力が多いのか1TLE。
int pa[100001]; int memo[100001]; int n,d; main(){ scanf("%d%d",&n,&d); for(int i=d+1;i<=n;++i){ if((i-1-d)%(d-1)==0)memo[i]=memo[i-1]+1; else memo[i]=memo[i-1]; } rep(i,n){ int t; scanf("%d",&t); ++pa[t]; } int ans=0; rep(i,n+1)ans+=memo[pa[i]]; cout<<ans<<endl; }