VKPC - 解けなかったG,H,J

後で解いた。

G

(嘘解法らしい。反例データがあるっぽい。)

"実はコンテスト中に自分が想定していたあれで強引に解けるらしい。"

ジャッジデータがおかしかったそうです。もう一度VKPCで提出したら誤差judgeになっていたのか1WA/40個くらいだけしていて、もうちょっと値を大きくしてみたら通った。AC具合によって調節しようとしていたのにこうなったのは悲しい・・・。コンテスト中1つもACしないからおかしいと思ったんだけどね。

・想定解は行列の累乗を用いた解法らしい(←これ1択)

・自分はDPで誤差がなくなるまでがんばる方針でやった。適当にtを誤魔化す。(チャレンジされると落ちます)

#include <iostream>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)

#define MAX (5000)
int m[50];
int v[50][4];
double memo[51][51][MAX];
int n;
double dfs(int pos,int prev,int t){
	if(memo[pos][prev][t] != -1.0) return memo[pos][prev][t];
	if(pos == n) return 1.0;
	if(t == 0) return 0;
	double ans = 0;
	int prob = m[pos];
	for(int i = 0 ; i < m[pos] ; i++){ if(v[pos][i] == prev) prob--; }
	
	for(int i = 0 ; i < m[pos] ; i++){
		if(v[pos][i] != prev){
			ans += dfs(v[pos][i],pos,t-1) * 1.0 / prob;
		}
	}
	return memo[pos][prev][t] = ans;
}
int main(){
	int t;
	cin >> n >> t;
	t = min(t,MAX-1);
	rep(i,51)rep(j,51)rep(k,MAX) memo[i][j][k] = -1.0;
	rep(i,n){
		cin >> m[i];
		rep(j,m[i]){
			cin >> v[i][j];
		}
	}
	printf("%.7f\n",dfs(0,53,t));
}

H

id:japlj先生に解き方を教えてもらった。

逆元を使うっぽい。

Ax+B = 0 (mod C)を変形して

x = -B * (1/A) (mod C)になり、(1/A)を拡張ユークリッドの互助法で求めると解けるらしい。

逆元はAとCが互いに素だから必ず存在し、それはmod Cの範囲では1つに定まるから最小のビットもクソもないらしい。ほえー。

※逆元の求め方

『Ax+Cy = 1 (mod C)』ならば、Cy = 0 (mod C)となるので、

上の式は『Ax = 1 (mod C)』となります。

そこで、

『x = 1/A (mod C)』

と変形すると、(mod C)において、x=1/A ( Aの逆元 ) であることが示せます。

『Ax+Cy = 1 (mod C)』が成り立つようなx,yは拡張ユークリッドの互助法を使うことによって求めることができます。(出てきたyは結局使いませんが)

逆元があると、Modにおける割り算ができるので、うれしいです(元々足し算・引き算・掛け算はできる)

[extgcd()はspaghetti sourceより。]

#include <iostream>
#include <algorithm>
#define bitcount(n) (__builtin_popcount(n))
using namespace std;
typedef long long Int;

Int extgcd(Int a, Int b, Int &x, Int &y) {
  Int g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

// X_n = -B*(1/A) (mod C)
int main(){
	Int a,b,c,X;
	cin >> a >> b >> c >> X;
	Int x,y;
	extgcd(a,c,x,y);
	Int gen = (x%c+c)%c;
	Int mb = (-b%c+c)%c;
	Int zero = gen*mb%c;
	int ans = 999;
	for(int i = 0 ; i < 150000 ; i++){
		ans = min(bitcount(zero^X),ans);
		X = (X*a+b)%c;
	}
	cout << ans << endl;
}

J

幾何部分が全く分からなかったので助けを乞う(小学生並みの数学力)

なんとか解けたけどやっぱりこれ一番難しいよ・・・。(幾何部分)

#include <iostream>
#include <map>
#include <vector>
#include <complex>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
struct P{
	double x,y,z;
	P(double x_,double y_,double z_){
		x = x_;
		y = y_;
		z = z_;
	}
	P operator-(P b){
		P a = *this;
		a.x -= b.x;
		a.y -= b.y;
		a.z -= b.z;
		return a;
	}
	P(){}
};

#define GET(a) (cin >> a.x >> a.y >> a.z)

double in(P a,P b){
	return a.x * b.x + a.y * b.y + a.z * b.z;
}
P fix(P v)
{
	double r = sqrt(in(v, v));
	v.x /= r;
	v.y /= r;
	v.z /= r;
	return v;
}

P out(P a , P b)
{
	P r;
	r.x = a.y*b.z - a.z*b.y;
	r.y = a.z*b.x - a.x*b.z;
	r.z = a.x*b.y - a.y*b.x;
	return r;
}

map< vector<int> , int > done;
int n;
P A[15],B[15],C[15],H[15];
int dfs(vector<int> v){
	//rep(i,v.size()) cout << v[i] << " "; cout << endl;
	if(done.find(v) != done.end()) return done[v];
	if(v.size()<=1) return 0;
	int ans = 1000;
	rep(i,n){
		vector<int> to[2];
		bool f = true;
		rep(j,v.size()){
			double o[3] = {0};
			if(i == v[j]) continue;
			o[0] = in( (A[v[j]]-A[i]) , H[i] );
			o[1] = in( (B[v[j]]-A[i]) , H[i] );
			o[2] = in( (C[v[j]]-A[i]) , H[i] );
			//	if(o[0] == 0 && o[1] == 0 && o[2] == 0) f = false;
			bool ff = true;
			int z = -1;
			rep(k,3){
				if(fabs(o[k]) == 0)continue;
				if(z == -1) z = o[k] < 0;
				else if(z != (o[k]<0) ) ff = false;
			}
			if(z==-1) continue;
			f &= ff;
			to[z].push_back(v[j]);
		}
		if(to[0].size() == v.size() || to[1].size() == v.size())continue;
		if(f) ans = min(ans,max(dfs(to[0]),dfs(to[1]))+1);
	}
	return done[v] = ans == 1000 ? 0 : ans;
}
int main(){
	while(cin >> n && n){
		rep(i,n){
			P a,b,c;
			GET(a);
			GET(b);
			GET(c);
			P h = fix(out((b-a),(c-a)));
			A[i] = a;
			B[i] = b;
			C[i] = c;
			H[i] = h;
		}
		vector<int> o;
		rep(i,n)o.push_back(i);
		done.clear();
		cout << dfs(o) << endl;
	}
}