SRM444Medium,443Easy,Medium

Mediumがどうしても後一歩のところで届かない…

がんばる。

444 Medium

数を四つの数の積で表したとき、その四つの数がすべて1以外の自然数であるときその数のレベルを1足す。
これを四つの数にも再帰的にやっていったときのレベルを求める問題。

方針

最初、long longの因数分解なんて出来ない！！！…とおもって諦めたのですが、実際これができて、因数分解の素因数の個数を4で何回割れるかが答えになります。

class NumericalPerfectionLevel {
   public:
   int isprime(long long n) {
   	if (n<2) return 0;
   	if (n==2) return 1;
   	for (long long i=2;i*i<=n;i++) {
   		if (n%i==0) return 0;
   	}
   	return 1;
   }
   int getLevel(long long N)
  {
	//long double res = (long double)N;
	if (isprime(N)) return 0;
	int cnt=0;
	/*while (res>=2.0) {
		res=sqrt(sqrt(res));
		if (res>=2.0) cnt++;
	}*/
	for (long long i=2; i*i<=N; i++) {
		while (N%i==0) {
			N/=i;
			cnt++;
		}
	}
	if (N!=1) cnt++;
	int ans=0;
	while (cnt/4>0) {
		cnt/=4;
		ans++;
	}
	return ans;
  }
};

反省

もっとしっかり最初から素因数分解のやり方を検討していれば自力で行けた気がします。

443 Easy

サッカーのリーグ戦の表から、各チームの勝ち点を求める問題。

方針

単純なループ

class SoccerLeagues {
   public:
   vector <int> points(vector <string> matches)
  {
	vi points(sz(matches),0);
	for (int i=0; i<sz(points); i++) {
		for (int j=0; j<matches[i].length(); j++) {
			if (matches[i][j]=='D') points[i]+=1;
			if (matches[i][j]=='W') points[i]+=3;
		}
		for (int j=0; j<sz(matches); j++) {
			if (matches[j][i]=='D') points[i]+=1;
			if (matches[j][i]=='L') points[i]+=3;
		}
	}
	return points;
  }
};

注意・反省？

サンプルから勝敗表の見方を読み取る。
中のループをまとめられた気がする・・・

443 Medium

ある点からある点に行きたい。その時通らなければいけない円周の数の最小数を求めよ。

方針

ルートはどんなに曲がってもいいので、二点と各円の内包関係を調べて、二点を含む円の数が答えになる。
ただし（ここで引っかかった）、二点が同じ円内にあるときは円周を通る必要がないので、一つの点のみを含む円だけ考える。

class CirclesCountry {
   public:
   int xx(int x) {return x*x;}
   bool incircle(int x, int y, int r, int x1, int y1) {
   	int xy = xx(x1-x)+xx(y1-y);
   	if (xx(r)<xy) return false;
   	return true;
   }
   int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2)
  {
	int cnt=0;
	REP(i,sz(X)) {
		if (incircle(X[i],Y[i],R[i],x1,y1)&&!incircle(X[i],Y[i],R[i],x2,y2)) cnt++;
		else if (!incircle(X[i],Y[i],R[i],x1,y1)&&incircle(X[i],Y[i],R[i],x2,y2)) cnt++;
	}
	return cnt;
  }
};