読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 499 DIV2

Programming Algorithm TopCoder

Rating: 894→859(灰)
下がりました。はい。まあ当然ですね…
500と950落とされた。まあたしかによくよく考えれば分かる事だったんだけど、一応全部解けた気でいたから、ショック…

234.89 Points

250: SimpleGuess

234.89 Points

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class SimpleGuess {
public:
	int getMaximum(vector <int> hints) {
		sort(hints.begin(), hints.end());
		int maximum = 0;
		for(int i = 0; i < hints.size(); i++){
			for(int j = i + 1; j < hints.size(); j++){
				if(!((hints[i] + hints[j]) % 2) && !((hints[j] - hints[j]) % 2)){
					int X = (hints[i] + hints[j]) / 2, Y = (hints[j] - hints[i]) / 2;
					maximum = max(maximum, X * Y);
				}
			}
		}
		return maximum;
	}
};

ベタな解法。当初ソートし忘れたりしていて、それで少し時間くった。

500: ColorfulRabbits

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

class ColorfulRabbits {
public:
	int getMinimum(vector <int> replies) {
		map<int, int> ma;
		for(int i = 0; i < replies.size(); i++){
			ma[replies[i]]++;
		}
		
		int res = 0;
		for(map<int, int>::iterator it = ma.begin(); it != ma.end(); it++){
			int a = (*it).first, b = (*it).second;
			res += (a + 1) * (int)ceil((double)b / (a + 1));
		}
		return res;
	}
};

上は修正後のソース。
さっきよく見たらちゃんと一般化して考えられてなかった。ダメじゃん…。
大筋ではあってない事もなかったのに、勿体ない。

950: PalindromeGame

うまくいってると思ったのにうまくいかなかった。カード単体が回文になってるケースはたしかに考慮してなかったけど…
デバッグできた。イテレータ構文にイマイチ慣れきれてないのとか、複合要因でした。

// System Test Passed
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class PalindromeGame {
public:
	int getMaximum(vector <string> front, vector <int> back) {
		vector<pair<int, string> > v(front.size());
		for(int i = 0; i < front.size(); i++){
			v[i] = make_pair(back[i], front[i]);
		}
		sort(v.begin(), v.end(), greater<pair<int, string> >());

		int total = 0;
		int f = 0;
		while(!v.empty()){
			int fd = 0;
			vector<pair<int, string> >::iterator beg = v.begin();
			string t = (*beg).second;
			reverse(t.begin(), t.end());
			for(vector<pair<int, string> >::iterator it = v.begin() + 1; it != v.end(); it++){
				if((*it).second == t){
					total += (*beg).first + (*it).first;
					v.erase(it);
					fd = 1;
					break;
				}
			}
			if(!fd && !f){
				if(t == (*beg).second){
					total += (*beg).first;
					f = 1;
				}
			}
			v.erase(beg);
		}
		return total;
	}
};