AOJ0114

AOJ

問題:Electro-Fly
mod取ってぐるぐる循環する奴が1周回るのにどれだけかかるかを求める問題。
愚直なループだとTLEするので、x,y,z別に求めてそれの最小公倍数で良い。
O(1)で求める解法ありそうだけどしらん。

#include<iostream>
using namespace std;

template<class t> t gcd(t a, t b){ return b != 0 ? gcd(b, a % b) : a; }
template<class t> t lcm(t a, t b){ return a*b/gcd(a,b); }
int main()
{
	long long a,b,c,m1,m2,m3;
	while( cin >> a >> m1 >> b >> m2 >> c >> m3 , a|b|c|m1|m2|m3 )
	{
		long long x=a%m1,y=b%m2,z=c%m3,c1=1,c2=1,c3=1;
		while( x!=1 ){ x=(x*a)%m1; c1++; }
		while( y!=1 ){ y=(y*b)%m2; c2++; }
		while( z!=1 ){ z=(z*c)%m3; c3++; }
		cout << lcm(c1 , lcm( c2,c3 ) ) << endl;
	}
}

AOJ0109

AOJ

問題:Smart Calculator
四則演算の計算機。
以前貼りつけた文字列を計算するやつが超絶バグっていてやばかった。
構文解析ってどうやってやるの？とかいいながら構文解析 Howto(もう答え）を参考にしながらポチポチした。ほぼ写経。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

#define DEBUG(a) cerr << #a << ":" << a << endl;
using namespace std;

int number( string::iterator& it );
int joujo( string::iterator& it );
int sisoku( string::iterator& it );
int kakko_or_number( string::iterator& it );

int number( string::iterator& it )
{
	int ret = 0;
	while( *it >= '0' && *it <= '9')
	{
		ret *= 10;
		ret += *it - '0';
		++it;
	}
	return ret;
}
int joujo( string::iterator& it )
{
	int ret = kakko_or_number( it );
	while(true)
	{
		if( *it == '*' )ret *= kakko_or_number( ++it );
		else if( *it == '/' )ret /= kakko_or_number( ++it );
		else return ret;
	}
}
int sisoku( string::iterator& it )
{
	int ret = joujo( it );
	while(true)
	{
		if( *it == '+' )ret += joujo( ++it );
		else if( *it == '-' )ret -= joujo( ++it );
		else return ret;
	}
}
int kakko_or_number( string::iterator& it )
{
	if( *it == '(' )
	{
		int ret = sisoku( ++it );
		++it;
		return ret;
	}
	else return number( it );
}
int main()
{
	int n;
	cin >> n;
	while( n-- )
	{
		string s;
		cin>>s;
		string::iterator it = s.begin();
		cout << sisoku( it ) << endl;
	}
}

SRM553Div2

Easy
全通り試す。TLEするかもしれないので一番内側にbreak仕込んどく。

class PlatypusDuckAndBeaver {
public:
  int minimumAnimals(int WF, int DB, int BT) {
    REP(p,1001)REP(b,1001)REP(d,1001){
       long long wf = 2*d + 4*b + 4*p;
       long long db = d + p;
       long long bt = b + p;
       if( wf > WF || bt > BT || db > DB )break;
       if( wf == WF && bt == BT && db == DB )return p+b+d;
    }
  }

Medium
二分探索しなくてもO(1)で求めれるらしい。オーバーフローに注意。

class Suminator {
public:
	long long calc( vector<int> in , long long k )
	{
		REP(i,in.size())
		{
			if( in[i] == -1 )
			{
				in[i] = k;
			}
		}

		stack< long long > stk;
		REP(i,60)
		{
			stk.push(0);
		}

		REP(i,in.size())
		{
			if(in[i] == 0){
				long long a = stk.top();stk.pop();
				long long b = stk.top();stk.pop();
				stk.push( a + b );
			}
			else{
				stk.push(in[i]);
			}
		}

		return stk.top();
	}
	long long findMissing(vector <int> program, int r) {
        long long result=-1;
	
	long long ub = 9223372036854775807LL;
	long long lb = 0LL;


	if( calc(program,0) == r )return 0;

	while( ub-lb > 1 )
	{
		long long md = ( ub - lb ) / 2LL + lb;
		long long res = calc(program,md);
		if( res == r )return md;
		if( res < r )lb = md;
		if( res > r )ub = md;
	}

    return result;
  }

SRM554Div2

TopCoder

Easy
制約が小さいので全通り試す。
交互に置くので、タワーを建設できるかどうかは、使うブロックの数の差が1以下で判定。
テンプレが長くて減点をくらう。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
static const double EPS = 1e-5;
static const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;

class TheBrickTowerEasyDivTwo {
public:
  int find(int rc, int rh, int bc, int bh) {
    int result=0;
	vector<int> cnt(100000,0);
	for( int r=0; r<= rc ; r++ ) 
	for( int b=0; b<= bc ; b++ )
	{
		if( abs(r-b) <= 1 ){
			cnt[ r*rh+b*bh ]++;
		}
	}
	for( int i=1; i<cnt.size(); ++i)
	{
		if( cnt[i] )
		{
			result++;
		}
	}
    return result;
  }
};

Medium
ソートしたら最適解になるのはわかるが、答えが辞書順で最小でないといけない。
入力サイズが最大7なので全通り試しても7!=5040通りなので結局全探索。
辞書順の判定はvectorの比較演算子を使えばOK。
テンプレ減点を防ぐために削るなど。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;

typedef long long ll;

class TheBrickTowerMediumDivTwo {
public:
	int calc( const vector<int>& d , const vector<int>& h ){
		int ret = 0;
		REP(i,d.size()-1){
			ret += max( h[d[i]] , h[d[i+1]] );
		}
		return ret;
	}

  vector <int> find(vector <int> heights) {
    vector <int> result;
	
	map< int , vector< int > > memo;
	vector<int> v;
	REP(i,heights.size())
	{
		v.push_back(i);
	}

	do{
		int k = calc( v, heights );
		if( memo.find(k) == memo.end() )
		{
			memo[k] = v;
		}else
		{
			if ( memo[k] > v ){
				memo[k] = v;
			}
		}
	}while( next_permutation( v.begin(),v.end() ) );

	result = memo.begin()->second;
    return result;
  }
};

Hardだれか教えて。。

AOJ0503

AOJ

問題:Cup
kyuridenamida「がんばって幅優先です」
といわれてがんばった。
きたないけどゆるしてね

#include<iostream>
#include<vector>
#include<queue>
#include<map>

using namespace std;

struct Node
{
	int a,b,c;
	Node():a(0),b(0),c(0){}
	bool operator < ( const Node& other ) const {
		if( a != other.a )return a < other.a;
		if( b != other.b )return b < other.b;
		return c < other.c;
	}
	bool ok() const
	{
		return  !a && !b || !b && !c ;
	}
};

int table[20];

int main()
{
	for( int i=0; i<20; ++i)
	{
		table[i] = 1<<i;
	}
	
	int n,m;
	while( cin >> n >> m , n|m )
	{
		map< Node , int > step;
		Node input;
		int a,b,c;
		cin >> a;
		for( int i=0; i<a; ++i )
		{
			int k;
			cin >> k;
			input.a |= 1<<(k-1);
		}
		
		cin >> b;
		for( int i=0; i<b; ++i )
		{
			int k;
			cin >> k;
			input.b |= 1<<(k-1);
		}
		
		cin >> c;
		for( int i=0; i<c; ++i )
		{
			int k;
			cin >> k;
			input.c |= 1<<(k-1);
		}
		
		queue< Node > q;
		q.push( input );
		if( input.ok() )
		{
			cout << 0 << endl;
			continue;
		}
		
		int ans=0;
		bool found = false;
		while( !found && q.size() )
		{
			Node node;
			//A<->B
			node = q.front();
			if( a|b )
			{
				int x = node.a ^ node.b;
				int k;
				for( k=19; x<table[k]; --k );
				if( node.a > node.b )
				{
					node.a -= table[k];
					node.b += table[k];
				}
				else
				{
					node.a += table[k];
					node.b -= table[k];
				}
				if( node.ok() && step[q.front()] < m)
				{
					found = true;
					ans = step[q.front()] + 1;
				}
				else if( step.find(node) == step.end() && step[q.front()] < m )
				{
					step[node] = step[q.front()] + 1;
					q.push( node );
				}
			}
			
			//B<->C
			node = q.front();
			if( b|c )
			{
				int x = node.b ^ node.c;
				int k;
				for( k=19; x<table[k]; --k );
				if( node.b > node.c )
				{
					node.b -= table[k];
					node.c += table[k];
				}
				else
				{
					node.b += table[k];
					node.c -= table[k];
				}
				if( node.ok() )
				{
					found = true;
					ans = step[q.front()] + 1;
				}
				else if( step.find(node) == step.end() && step[q.front()] < m )
				{
					step[node] = step[q.front()] + 1;
					q.push( node );
				}
			}
			q.pop();
		}
		if( found )
		{
			cout << ans << endl;
		}
		else
		{
			cout << -1 << endl;
		}
	}
	return 0;
}

通信対戦の流れをざっくり3つに分割

未分類

Fulci666氏に習って通信対戦の流れを3つの問題に分割してみた．

1.DNS問題
DNAS認証とはSONY独自の機器認証システムで，よくわからないことをしている．チートなんかも基本ここではじかれる模様．DNAS認証システムは今でも動いているので，問題は無い．
DNAS認証の後，MMBBにログインするためにPS2上でWebブラウザが立ち上がり，ログインページが表示される．
このブラウザでログインし，ゲームスタートボタンを押すとゲームサーバに接続される．

現在はMMBBログインページに接続することができない.接続先を変更させる処理が必要となる.


2.ログイン問題
Webブラウザを終了し，ゲームサーバに接続する.
MMBBにログインした後，ゲームサーバに接続される間に，ゲームアップデート処理がある．
アップデート処理では，アップデートパッチをメモリカードにダウンロードすることが出来る．

Zでは確かパッチは無かった気がするので,アップデート処理は実装しなくて良いかもしれない．
ただ，Webブラウザを終了し，ゲームサーバに接続する処理はどのような通信を行なっているのか，かなり調査しなければならない．


3.ゲームサーバ問題
ゲームサーバに接続したら，まずカプコンゲームID（6文字の英数字）の選択を行う.HNの変更などもここで行える.
その後ロビー選択画面（戦場選択画面）でロビーを選択し，ロビーに入る.
ロビーではロビーチャットや部屋の作成を行う事ができる.
作成した部屋では，ロビーと隔離されたプライベートチャット，部屋内の人と対戦を開始することが出来る.

これらの処理のサーバサイドを全て実装しなければならない.
実際の対戦中は，1Pがサーバになり，2〜4Pは1PのPS2に接続しているよう（憶測）なので，サーバに負荷はあまりかからないかも.

Zのエミュ鯖を構築したい

未分類

ガンダムvsシリーズはご存知だろうか．
最新作はエクストリームバーサス（EXVS）というゲームで，全国のゲームセンターで稼働中，PS3版で通信対戦を楽しむことができる．
新しい作品になるたび大きくゲーム性が変わり，操作方法は同じものの完全に別のゲームになっている．

僕はこのシリーズの2作目にあたるZガンダム エゥーゴvs.ティターンズ(及びバージョンアップ版DX)が大好きで，もう8年ほど遊んでいる．
ZガンダムDXのPS2版にあたるガンダムvs.Zガンダム(以後Z)の通信対戦サービスが昨年6月末に終了し，毎日のように遊んでいた友人や，有名プレイヤー達と対戦する機会を失った．

通信対戦が終了してからは，わざわざ東京のゲームセンターに遊びに行ったりして対戦している．
定期的に対戦会を開いてくれている方が居て，ニコニコ生放送で実況したりなどもしているようだ．

また通信の皆と対戦するため，このゲームのサーバを構築したい．(前置き長すぎ)

Zの通信対戦サービスは，KDDIのマルチマッチングBB(以後MMBB)が運営していた．
有名どころでは，モンスターハンターのオンラインプレイもMMBBである．
MMBBのエミュ鯖を構築している人が居ないか調べていると，構築には至ってないもののかなり調べているFulci666さんのブログを見つけることができた．

Biohazard/Resident Evil Outbreak Server

バイオハザードアウトブレイクというゲームは海外でもオンラインサービスがあったようだが，日本版(MMBB)より先にサービスが終了した．
そこで海外のバイオプレイヤーは，日本版のPS2本体とソフトを用意してMMBBで遊んでいたようだが，MMBBもサービスが終了してしまった.
Fulci666さんはかなり熱心に解析されており，通信で使われているプロトコルやAPIまで突き止めている．
バイオハザードとZガンダムとでは，ロビーの構成やチャットなどもかなり似ているため，彼のブログは非常に役に立つと思われる．

彼のブログを読んだりしながら，Zエミュ鯖構築のためのメモ書きをこのブログに書いて行こうと思う．