Codeforces Round #341 (Div. 2) D. Rat Kwesh and Cheese

問題文はこちら(Problem - D - Codeforces)

まず\( (x^y)^z = (x^z)^y \)であることから\(a_4, a_8, a_{12}\)が候補から外れる。
単純に与えられた式を計算するとオーバーフローしてしまうため、対数をとって比較していく。ただし、\(x < 1\)のとき\( \mathrm{log} x < 0 \)より\( \mathrm{log} \mathrm{log} x\)は(実数上で)存在しない。よってx, y, zの中に1より小さいものが含まれているかどうかで場合分けをする。

(i) x,y,zが全て1より大きい時

\( \{\mathrm{log} \mathrm{log} a_i\}\)の中で最大のものを探す。ただし、最大値を取るものが複数あるときはindexの最も小さいものを選ぶ。

(ii) x, y, zのいずれかが1よりも大きい時

1よりも小さい数が底ならば、今の場合指数は必ず正であるから最終的な値は1よりも小さくなる。逆に1以上の数が底ならば、最終的な値は1以上になる。従って、底が1よりも大きいもののみを(i)と同じように比較すればよい(底が1より小さいものは適当に-INFとかで埋めておく)。

(iii) x,y,zが全て1以下の時

オーバーフローする心配が無いため、\( \mathrm{log} a_i\) の中で最大のものを探せばよい。

コンテストでは\( \mathrm{log} \mathrm{log} x\)が死にうることに気づかず提出してしまった。

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

bool comp(pair<ld,int> p1, pair<ld,int> p2) {
  if(p1.first != p2.first) return p1.first < p2.first;
  return p1.second > p2.second;
}

int main(){
  double x, y, z;
  cin >> x >> y >> z;
  string ans[] = {"x^y^z", "x^z^y", "(x^y)^z", "y^x^z", "y^z^x", "(y^x)^z", "z^x^y", "z^y^x", "(z^x)^y"};
  vector<pair<ld,int>> val(9);

  if(x > 1.0 || y > 1.0 || z > 1.0) {
    if(x > 1.0) {
      val[0] = make_pair(z * log(y) + log(log(x)), 0);
      val[1] = make_pair(y * log(z) + log(log(x)), 1);
      val[2] = make_pair(log(y * z) + log(log(x)) , 2);
    }else{
      val[0] = make_pair(-INF, 0);
      val[1] = make_pair(-INF, 1);
      val[2] = make_pair(-INF, 2);
    }
    if(y > 1.0) {
      val[3] = make_pair(z * log(x) + log(log(y)), 3);
      val[4] = make_pair(x * log(z) + log(log(y)), 4);
      val[5] = make_pair(log(z * x) + log(log(y)) , 5);
    }else{
      val[3] = make_pair(-INF, 3);
      val[4] = make_pair(-INF, 4);
      val[5] = make_pair(-INF, 5);
    }
    if(z > 1.0) {
      val[6] = make_pair(y * log(x) + log(log(z)), 6);
      val[7] = make_pair(x * log(y) + log(log(z)), 7);
      val[8] = make_pair(log(y * x) + log(log(z)) , 8);
    }else{
      val[6] = make_pair(-INF, 6);
      val[7] = make_pair(-INF, 7);
      val[8] = make_pair(-INF, 8);
    }
  }else{
    val[0] = make_pair(pow(y, z) * log(x), 0);
    val[1] = make_pair(pow(z, y) * log(x), 1);
    val[2] = make_pair(y * z * log(x), 2);
    val[3] = make_pair(pow(x, z) * log(y), 3);
    val[4] = make_pair(pow(z, x) * log(y), 4);
    val[5] = make_pair(x * z * log(y), 5);
    val[6] = make_pair(pow(x, y) * log(z), 6);
    val[7] = make_pair(pow(y, x) * log(z), 7);
    val[8] = make_pair(x * y * log(z), 8);
  }

  sort(ALL(val), comp);
  cout << ans[val[8].second] << endl;
  return 0;
}