AtCoder Beginner Contest 081を解きました
D問題とけない
A問題
abc081.contest.atcoder.jp
#include<stdio.h> int main() { int i,res=0; char str[5]; fgets(str,4,stdin); for(i=0;i<4;i++) if(str[i] == '1') res++; printf("%d\n",res); return 0; }
fgetsの挙動がよくわからず、配列の個数を若干多くしたり、fgetsの2番めの引数を4つにしたりしてます。
模範解答だとfor文を使わず、if文を3つ重ねていたと思います。
#include<stdio.h> int main() { int N,res=10000000,y=0,i,A[201]; scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&A[i]); for(i=0;i<N;i++){ y=0; while(A[i] % 2 == 0){ A[i] /= 2; y++; } if(y < res) res = y; } printf("%d\n",res); return 0; }
数列内で素因数2の数が最も小さいものを求める問題に帰着されます。
まあでも実際にすべての数列を割り切れなくなるまで2で割るようにしても同じようなコードになりそうです。
C問題
C: Not so Diverse - AtCoder Beginner Contest 081 | AtCoder
#include<stdio.h> #include<stdlib.h> int func(const void *a,const void *b) { if(*(int*)a < *(int*)b){ return -1; } else if(*(int*)a == *(int*)b){ return 0; } return 1; } int main() { int S[200001],A[200001],i,N,K,t,res=0,k=0; scanf("%d %d",&N,&K); for(i=0;i<N;i++) scanf("%d",&A[i]); for(i=0;i<N+1;i++) S[i] = 0; for(i=0;i<N;i++) S[A[i]]++; qsort(S,N+1,sizeof(int),func); for(i=0;i<N+1;i++) if(S[i]) k++; t = k - K; for(i=0;i<N+1;i++){ if( t <= 0 ) break; if( S[i] != 0){ res += S[i]; t--; }else continue; } printf("%d\n",res); }
まず、どの数字がいくつあるかをカウントします。
個数の小さなものの色を塗り替えて種類を減らす貪欲が最適です。そのために配列をソートして...とすると上のようなコードになります。