roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #341 Div2 D. Rat Kwesh and Cheese

ABCD提出、pretestがギリギリだったBは落ちてしまい3完。1634 -> 1729 (+95)
http://codeforces.com/contest/621/problem/D

問題

0.1以上200.0以下の0.1刻みの値を持つ3変数x, y, zの値が与えられる。 12個の式の中で最大値を取るもののうち、もっとも番号の小さな式を答えよ。

解法

とりあえずlogを取ってみようと思いつく。しかし、pythonのfloatは 200**200 ではオーバーフローとなり処理できない。そこで、もう一度logを取ってみる。そうすると扱える大きさに収まるが、一度目のlogを取った時に負の値や0があった場合REとなってしまう。

これを回避するためx, y, zがすべて1.0以下のときと、そうでないときに場合分けをして考えればよい。
すべて1.0以下の時は一度のlogで扱える大きさに収まる。
また、式の一番右肩の値が1.0以下の時は一度logを取ると0以下、1.0より大きい値は0よい大きくなる。右肩の値が1.0以下の式はあきらかに右肩の値が1.1以上の式より小さいので、1.1以上の値が含まれるときはそれらが肩に乗っているもののみを計算してやればいい。

import math
x, y, z = map(float, raw_input().split())
log = math.log

ans = [
    "x^y^z",
    "x^z^y",
    "(x^y)^z",
    "(x^z)^y",
    "y^x^z",
    "y^z^x",
    "(y^x)^z",
    "(y^z)^x",
    "z^x^y",
    "z^y^x",
    "(z^x)^y",
    "(z^y)^x"
]

a = [-1e9]*12
if x <= 1.0 and y <= 1.0 and z <= 1.0:
    a[0] = y**z*log(x)
    a[1] = z**y*log(x)
    a[2] = z*y*log(x)
    a[4] = x**z*log(y)
    a[5] = z**x*log(y)
    a[6] = x*z*log(y)
    a[8] = x**y*log(z)
    a[9] = y**x*log(z)
    a[10] = x*y*log(z)
else:
    if x > 1.0:
        a[0] = z*log(y) + log(log(x))
        a[1] = y*log(z) + log(log(x))
        a[2] = log(z*y) + log(log(x))
    if y > 1.0:
        a[4] = z*log(x) + log(log(y))
        a[5] = x*log(z) + log(log(y))
        a[6] = log(x*z) + log(log(y))
    if z > 1.0:
        a[8] = y*log(x) + log(log(z))
        a[9] = x*log(y) + log(log(z))
        a[10] = log(x*y) + log(log(z))

a = sorted([[a[i], i] for i in xrange(12)], reverse = True)
mx = a[0][0]
mxi = a[0][1]
for ai, i in a[1:]:
    if abs(mx - ai) < 1e-7:
        mxi = min(mxi, i)

print ans[mxi]

まとめ

Decimal使ったり、C++でlong doubleを使うとシンプルに解けるらしい。
logに負の値が入る場合があったり、出力する文字列を手打ちする必要があったりと引っかかる要素がいくつかあり、本番では460人くらい提出で50人未満しか通ってなかった。

広告を非表示にする