SRM442,441のDiv.2Easy,Medium

やっぱり微妙に間違える…

ってか、今までChromeでブログ書いてたけどFFのビジュアルが意外とかっこいいｗｗｗ

442 Easy SimpleWordGame

playerが何個単語を覚えていたか？もとはdictionary

方針

とりあえずplayerの重複分は無視したいのでuniqueで消しといた。けどやらなくてもできる。

#define SORT(c) sort((c).begin(),(c).end())
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(c) (c).begin(),(c).end()
#define SZ(c) (c).size()
typedef vector<string> vs;

class SimpleWordGame {
   public:
   int points(vector <string> player, vector <string> dictionary)
  {
	SORT(player); SORT(dictionary);
	vs::iterator it=unique(ALL(player)); player.erase(it, player.end());
	int res = 0;
	REP(i,SZ(player)) {
		bool flag=false;
		REP(j,SZ(dictionary)) {
			if (player[i]==dictionary[j]) {
				flag = true;
				break;
			}
		}
		if (flag) res+=player[i].length()*player[i].length();
	}
	return res;
  }
};

442 Medium Underprimes

数字を素因数分解をしたときに素因数の数が素数であるものをunderprimeと定めます。
与えられた二数の間のunderprimeの数を答えなさい。

方針

とりあえず素数テーブルをつくっておくのは常識。
まぁ普通に因数分解します。

class Underprimes {
   public:
   int howMany(int A, int B)
  {
	int cnt=0;
	vector<int> prime(100,0);
	prime[0]=-1;prime[1]=-1;
	for (int i=2; i*i<100; i++) {
		if (prime[i]==0) {
			for (int j=i*i; j<100; j+=i) {
					prime[j]=-1;
			}
		}
	}
	for(int i=A; i<=B; i++) {
		int cnt2=0,num=i;
		while (num%2==0) {
			num/=2;
			cnt2++;
		}
		int save=num;
		for (int j=3; j*j<=save; j+=2) {
			while (num%j==0) {
				num/=j;
				cnt2++;
			}
		}
		if (num>1) cnt2++;
		if (prime[cnt2]==0) cnt++;
	}
	return cnt;
  }
};

反省

素数テーブルでつまづいたので、頑張りたい。
素因数分解はあれですね。numがどんどん減っていくのにforループの上限値に設定してたのはドジ。

441 Easy DifferentStrings

AとBの文字列が与えられる。この時(Aの長さ)≦(Bの長さ)と保証する。
さて、ここでAにはBの長さとなるまで前と後ろに好きな文字列を足せるとして、同じ長さにして一番AとBの差異が少なくなるようにしたならば、そのときのAとBで違う文字の数を答えよ。

方針

Aの長さのBの部分文字列を調べてAとの差異の最小を求める。

class DifferentStrings {
   public:
   int minimize(string A, string B)
  {
  	int res=0;
	if (A.length()==B.length()) {
		for (int i=0; i<A.length(); i++) {
			if (A[i]!=B[i]) res++;
		}
		return res;
	}
	res=51;
	for (int i=0; i<B.length()-A.length()+1; i++) {
		int cnt=0;
		string str=B.substr(i,A.length());
		for (int j=0; j<A.length(); j++) {
			if (A[j]!=str[j]) cnt++;
		}
		if (res>cnt) res=cnt;
//		cout<<str<<endl;
	}
	return res;
  }
};

441 Medium PaperAndPaintEasy

紙を1cm区切りにして、まずxfoldで二つ折り、cnt+1個にy方向で折り、そして指定された範囲を塗って広げたときぬられていない部分の数（もしかしたら塗るところ逆かも。）

方針

min(xfold,width-xfold)で塗る範囲を区切ると、二つ折りしているところとしていないところに分けることができる。あとは四則演算。
注意するのはいちいちlong longでキャストしていかないと漏れます。

typedef long long ll;
typedef unsigned long long ull;

class PaperAndPaintEasy {
   public:
   long long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2)
  {
	ll res=0;
	int Min=min(xfold,width-xfold); // 折り返したとき、右側のほうが短ければ反転して考えて良い。
	ll y = y2-y1;
	cnt++;
	if (x1<Min) {
		res += (ll)(min(x2,Min)-x1)*y*cnt*2; // キャストしないとあふれる
		if (x2>=Min) {
			res += (ll)(x2-Min)*y*cnt;
		}
	} else {
		res += (ll)(x2-x1)*y*cnt;
	}
	return (ll)width*height-res;
  }
};