AOJ 1287 : Stopped Watches

問題リンク：Stopped Watches | Aizu Online Judge

問題概要：
n個の時計の情報が与えられる
ただ、どれが秒針でどれが分針、時針なのかはわからないし
どこを基準に数えているのかも分からない
全ての時計がとりうる時間の間隔のうちもっとも短いものを出力せよ
時計の時針は12分毎に１つ進む

解法：
どれが秒針、分針、時針なのかとどこを基準にかぞえているのかを全て試す
時間を生成した後は全探索で求めたい間隔を探す
時間を求める際に、時針が12分毎に１つ進んだという条件に反していないかどうかチェックする必要がある

コード：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdio>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

struct Time
{
  int h,m,s;
  Time(int h=inf,int m=inf,int s=inf):h(h),m(m),s(s){}
  bool operator < (const Time& a)const
  {
    if(h != a.h)return h < a.h;
    if(m != a.m)return m < a.m;
    return s < a.s;

  }
  bool operator == (const Time& a)const
  {
    return (h == a.h && m == a.m && s == a.s);
  }

};
int n;

vector<Time> compute(int s,int t,int u)
{
  vector<Time> res;
  int watch[3];
  watch[0] = s, watch[1] = t,watch[2] = u;
  sort(watch,watch+3);

  do
    {
      rep(i,60)
	{
	  int hh = watch[0], mm = watch[1], ss = watch[2];
	  ss = (ss+i)%60;
	  mm = (mm+i)%60;
	  hh = (hh+i)%60;
	  if(!((hh%5)*12 <= mm &&  mm < ((hh%5)+1)*12))continue;
	  hh = hh/5;

	  res.push_back(Time(hh,mm,ss));
	}
    }while(next_permutation(watch,watch+3));
  sort(res.begin(),res.end());
  res.erase(unique(res.begin(),res.end()),res.end());
  return res;
}

int calc(Time a,Time b)
{
  return abs((a.h*60*60 + a.m*60 + a.s) - (b.h*60*60 + b.m*60 + b.s));
}

void print(Time t)
{
  int keta = (t.h==0?1:log10(t.h)+1);
  cout << string(2-keta,'0') << t.h;
  cout << ':';
  keta = (t.m==0?1:log10(t.m)+1);
  cout << string(2-keta,'0') << t.m;
  cout << ':';
  keta = (t.s==0?1:log10(t.s)+1);
  cout << string(2-keta,'0') << t.s;
}

int main()
{

  while(scanf("%d",&n),n)
    {
      vector<Time> timer[n];
      map<Time,int> counter;
      rep(i,n)
	{
	  int s,t,u;
	  scanf("%d %d %d",&s,&t,&u);
	  timer[i] = compute(s,t,u);
	}

      int p1,p11,p2,p22;
      int mincost = inf;
      rep(sp,n)
	{
	  rep(i,timer[sp].size())
	    {
	      Time time1 = timer[sp][i];
	      REP(gp,sp+1,n)
		{
		  rep(j,timer[gp].size())
		    {
		      Time time2 = timer[gp][j];
		      Time men = min(time1,time2);
		      Time mex = max(time1,time2);
		      int cost = calc(men,mex);
		      if(cost > mincost)continue;

		      bool common = true;

		      int nv = calc(men,Time(0,0,0));
		      int xv = calc(mex,Time(0,0,0));
		      rep(cur,n)
			{
			  if(cur == sp || cur == gp)continue;
			  bool found = false;
			  rep(next,timer[cur].size())
			    {
			      int v = calc(timer[cur][next],Time(0,0,0));
			      if(nv <= v && v <= xv)
				{
				  found = true;
				  break;
				}
			    }
			  if(!found)
			    {
			      common = false;
			      break;
			    }
			}

		      if(!common)continue;
		      if(cost < mincost)
			{
			  mincost = cost;
			  p1  = sp, p2  = gp;
			  p11 = i,  p22 = j;
			}
		      else if(cost == mincost)
			{
			  int t1 = calc(time1,Time(0,0,0));
			  int t2 = calc(time2,Time(0,0,0));
			  int t3 = calc(timer[p1][p11],Time(0,0,0));
			  int t4 = calc(timer[p2][p22],Time(0,0,0));
			  if(min(t1,t2) < min(t3,t4))
			    {
			      p1  = sp, p2  = gp;
			      p11 = i,  p22 = j;
			    }
			}
		    }
		}
	    }
	}
     

      //cout << "mincost = " << mincost << endl;
      Time men,mex;
      if(calc(timer[p1][p11],Time(0,0,0)) > calc(timer[p2][p22],Time(0,0,0)))
	{
	  men = timer[p2][p22];
	  mex = timer[p1][p11];
	}
      else
	{
	  mex = timer[p2][p22];
	  men = timer[p1][p11];
	}

      print(men); cout << ' '; print(mex); cout << endl;

    }
  return 0;
}