2014-01-31 - HIR180's diary

■ SRM 605 18:21

あさめなので本番は出られませんでした

Easy

guesses[0]+answer[0],guesses[0]-answer[0]を調べるだけ

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
class EllysNumberGuessing
{
public:
int getNumber(vector <int> guesses, vector <int> answers)
{
	srand((unsigned int)time(NULL));
	int res=0;
	int val;
	int x=guesses[0]+answers[0];
	if(!(1<=x && x<=1000000000)) goto a;
	for(int i=1;iif(abs(x-guesses[i])!=answers[i]) goto a;
	}
	res++; val=x;
	a:;
	x=guesses[0]-answers[0];
	if(!(1<=x && x<=1000000000)) goto b;
	for(int i=1;iif(abs(x-guesses[i])!=answers[i]) goto b;
	}
	res++; val=x;
	b:;
	if(!res) return -2;
	if(res==2) return -1;
	return val;
}
};

Med

各種類の数列内で過半数である要素を列挙することを考える。

数列の計算方法より、過半数になる場合は以下の3通りのいずれかである。

1.周期1

2.周期2

3.途中から周期1

1,2は最初にO(1)で判定でき、3は最後まで計算した値を見ておけば良い。

あとはさっきと全く同じことをすれば良い。setじゃなくてvectorでもって二分探索したほうが

Time Limit的にいいと思います。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
class EllysPairing
{
public:
int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add)
{
	set<int>cand;
	for(int i=0;i1LL*first[i];
		if(((prev*mult[i]+add[i])&(M-1))==prev)
		{
			cand.insert(prev);
			continue;
		}
		else if(((((prev*mult[i]+add[i])&(M-1))*mult[i]+add[i])&(M-1))==prev)
		{
			cand.insert(prev);cand.insert(((prev*mult[i]+add[i])&(M-1)));
			continue;
		}
		for(int j=0;j1;j++)
		{
			prev=((prev*mult[i]+add[i])&(M-1));
		}
		if(((prev*mult[i]+add[i])&(M-1))==prev||count[i]<=3) cand.insert(prev);
	}
	printf("%d\n",(int)cand.size()); 
	mapint>num;
	int z=0;
	for(int i=0;i1LL*first[i];  z+=count[i];
		if(cand.find(prev)!=cand.end()) num[prev]++;
		for(int j=0;j1;j++)
		{
			prev=(prev*mult[i]+add[i])&(M-1);
			if(cand.find(prev)!=cand.end()) num[prev]++;
		}
	}
		for(mapint>::iterator it=num.begin();it!=num.end();++it)
		{
			if(it->s>=(z+1)/2) return z-it->s;
		}
	return z/2;

}
};