夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

445 Div.2 Easy Medium

今日は一時間かけてコレだけ解いた。

ということは445に出場してたらコレだけ解けたということだな。うん。


というわけで解説。

Easy

問題概略はこちら

暗号化したときそれがアルファベット順で一番早くなるような暗号を出力。ルールは同じアルファベットは違う同じアルファベットに変換され、さらに違うアルファベットが変換されるアルファベットは一対一対応。

さて、普通の暗号と思って早とちりしそうであるが、つまりは最初からa,b...と当てはめていって同じやつはそのときのアルファベットを使う的な。

mapとかがんばってつかってやった。

class TheEncryptionDivTwo {
   public:
   string encrypt(string message)
  {
	string res="a";
	map<char, char> trans;
	trans[message[0]] = 'a';
	char tmp = 'a';
	FOR(i,1,message.length()) {
		if (trans.count(message[i])==1) {
			res += trans[message[i]];
		} else {
			tmp++;
			res += tmp;
			trans[message[i]] = tmp;
		}
	}
	return res;
  }
}

Medium

ある人がおうちを立てたい。だけどセキュリティ面が不安だから少なくとも東西南北の同じとおりに少なくとも一個ずつ古い家がなければならない。
古いおうちのx,y座標が与えられるから、新しく家を建てられる場所の数を答えよ。

という問題。
要するにx,y座標それぞれで二個以上同じ数値がある者が答えのx,y座標になり得る。ということと選んだ時に座標が同じでない方の座標の間に答えの座標がなければいけない、という点に留意。
そうすると単純に答えに成りうるx,y座標をリストアップして、それぞれに検証していけばいい。

ちょっと重複しない配列で、しかも使いやすいものを作るのに苦労しました。
今回は

findでその要素がすでにあるかどうか確認
あったらそれは二個以上あるから候補に入れる
uniqueで重複のiteratorを返し、eraseでけして重複をなくす

といった感じです。これに時間取られたorz

class TheNewHouseDivTwo {
   public:
   bool ok(vi x, vi y, int xp, int yp) {
   	bool flag=false;
   	REP(i,SZ(x)) {
   		if (x[i]==xp) {
   			int yy = y[i];
   			FOR(j,i+1,SZ(x)) {
   				if (x[j]==xp) {
   					if ((yy<yp&&y[j]>yp)||(yy>yp&&y[j]<yp)) {
   						flag=true;
   						break;
   					}
   				}
   			}
   		}
   	}
   	if (flag) {
   		flag = false;
   		REP(i,SZ(y)) {
   			if (y[i]==yp) {
   				int xx = x[i];
   				FOR(j,i+1,SZ(y)) {
   					if (y[j]==yp) {
   						if ((xx<xp&&x[j]>xp)||(xx>xp&&x[j]<xp)) {
   							flag=true;
   							break;
   						}
   					}
   				}
   			}
   		}
   	}
   	return flag;
   }
   int count(vector <int> x, vector <int> y)
  {
	vi xres, yres, xm, ym;
	REP(i,SZ(x)) {
		if (find(xm.begin(),xm.end(),x[i])==xm.end()) xm.PB(x[i]);
		else if (find(xm.begin(),xm.end(),x[i])!=xm.end()) xres.PB(x[i]);
	}
	REP(i,SZ(y)) {
		if (find(ym.begin(),ym.end(),y[i])==ym.end()) ym.PB(y[i]);
		else if (find(ym.begin(),ym.end(),y[i])!=ym.end()) yres.PB(y[i]);
	}
	SORT(yres); SORT(xres);
	vi::iterator end_it = unique(ALL(xres)); xres.erase(end_it, xres.end());
	end_it = unique(ALL(yres)); yres.erase(end_it, yres.end());
	int res=0;
	FOR(i,0,SZ(xres)) {
		FOR(j,0,SZ(yres)) {
			if (ok(x,y,xres[i],yres[j])) res++;
		}
	}
	return res;
  }
}

こんなに長いコード初めてw

総評

今回は配列にどちらも苦しませられた。
もっとC++を使いこなせるようにしなければ。JOIとかその場で調べられないと全く解けない…