SRM 572

今日は開始前にやたらといろいろな人たちにArenaで声をかけられました。返事しきれない。またOnShuffle氏いたし。

250
難しくて分からない。なんだこれ……。
適当に変なGreedyコードを書いて落とされる。別に解けてないし仕方が無い。
あとで聞いてみるとUnion-Findらしい。知るか。

500
見れば分かると思うが自明に半分全列挙やるだけ。
ただしコード量が多すぎるのでぜんぜん高得点が取れない。320点なのにMedium点数順だと9位。

#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
struct wolf{
	int d[50];
	int M;
	wolf(){
		for(int i=0;i<50;i++)d[i]=0;
		M=0;
	}
};
inline bool operator<(const wolf &a,const wolf &b){
	for(int i=0;i<50;i++){
		if(a.d[i]!=b.d[i])return a.d[i]<b.d[i];
	}
	return false;
}

string fox(int number)
{
  stringstream ss;
  ss << number;
  return ss.str();
}
class EllysBulls{
	public:
	wolf w[100000];
	string getNumber(vector<string>a,vector<int>b){
		if(a[0].size()<6){
			int m=1;
			for(int i=0;i<a[0].size();i++)m*=10;
			int count=0;
			int ans=0;
			for(int i=0;i<m;i++){
				bool ok=true;
				for(int j=0;j<a.size();j++){
					int v=i;
					int B=0;
					for(int k=a[0].size()-1;k>=0;k--){
						if(a[j][k]-'0'==v%10)B++;
						v/=10;
					}
					if(B!=b[j])ok=false;
				}
				if(ok){count++;ans=i;}
			}
			if(count==0)return "Liar";
			else if(count>1)return "Ambiguity";
			else {
				string b= fox(ans);
				while(b.size()<a[0].size())b='0'+b;
				return b;
			}
		}else{
			int m=100000;
			//for(int i=0;i<a[0].size();i++)m*=10;
			for(int i=0;i<m;i++){
			//	bool ok=true;
				w[i].M=i;
				for(int j=0;j<a.size();j++)w[i].d[j]=b[j];
				for(int j=0;j<a.size();j++){
					int v=i;
					
					for(int k=4;k>=0;k--){
						if(a[j][k]-'0'==v%10)w[i].d[j]--;
						v/=10;
					}
					//if(B!=b[j])ok=false;
				}
			//	if(ok){count++;ans=i;}
			}
			std::sort(w,w+m);
			int n=1;
			for(int i=0;i<a[0].size()-5;i++)n*=10;
			int count=0;
			int ans=0;
			for(int i=0;i<n;i++){
				wolf p;
				for(int j=0;j<a.size();j++){
					int v=i;
					for(int k=0;k<a[0].size()-5;k++){
						if(a[j][a[0].size()-1-k]-'0'==v%10)p.d[j]++;
						v/=10;
					}
				}
				int N=upper_bound(w,w+m,p)-lower_bound(w,w+m,p);
				count+=N;
				if(N)ans=w[lower_bound(w,w+m,p)-w].M*n+i;
			}
			if(count==0)return "Liar";
			else if(count>1)return "Ambiguity";
			else{
				string b= fox(ans);
				while(b.size()<a[0].size())b='0'+b;
				return b;
			}
		}
	}
};

1000
hosさん出題らしい。

Challenge Phase
TLEコード見つけて+1したので調子に乗ったら-2してしまいもったいない。あと250は落とされた。

System Test
500とおる。

0 + 321.15 + 0 + 0 = 321.15 (65th)
Rating 1940 -> 2018 (-22)
4月中にレッドになれるかな??