SRM 620 DIV1 Easy - PairGame (××)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13142&rd=15853
・(x,y)のペアを考える。
・このペアは(x+y,y)もしくは（x,x+y）のペアに変換することができる。
・(a,b),(c,d)のペアが与えられたとき、どちらのペアも作ることのできるペア(x,y)のうち
もっともx+yが大きくなるときのx+yの値を求める。
解き方
・全探索は難しそう。
・なにか法則を見つける必要がありそうだが。。
・サンプルをみたとき、(15,4)→(11,4)→(7,4)となるのでなにかありそうだが
うまく見つからなく断念。
→他の人のコードをみてみる。
・サンプルから、(a,b)でa>=bのときは(a-b,b)から遷移しなく、
a<bのときは(a,b-a)からしか遷移しないことがわかる。
・よって、答えである(a,b),(c,d)をそれぞれ遷移させ、共通するもののうち
最大となるペアの和が答えになる。
反省：問題文からもっといろいろ紙に整理してみるのが足りていないと実感。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PairGame {
public: int maxSum(int a, int b, int c, int d) {
set<pair<int,int> > p1,p2;
while(a>0 && b>0){
p1.insert(make_pair(a,b));
if(a>=b)a-=b;
else b-=a;
}
while(c>0 && d>0){
p2.insert(make_pair(c,d));
if(c>=d)c-=d;
else d-=c;
}
int ret=-1;
for(set<pair<int,int> > :: iterator it=p1.begin();it!=p1.end();it++){
if(p2.find(*it)!=p2.end())ret=max(ret,it->first+it->second);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PairGame {
public: int maxSum(int a, int b, int c, int d) {
set<pair<int,int> > p1,p2;
while(a>0 && b>0){
p1.insert(make_pair(a,b));
if(a>=b)a-=b;
else b-=a;
}
while(c>0 && d>0){
p2.insert(make_pair(c,d));
if(c>=d)c-=d;
else d-=c;
}
int ret=-1;
for(set<pair<int,int> > :: iterator it=p1.begin();it!=p1.end();it++){
if(p2.find(*it)!=p2.end())ret=max(ret,it->first+it->second);
}
return ret;
}
};
