競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 158B

ARC158B

3文字動かすのは大変なので,1文字だけ動かす. あるいは,2文字しかないverで解く.

2文字ver
\(b\) を固定したときの \(f(a) := \frac{a+b}{ab}\) の min, max を考える. \(f(a) = \frac{1}{b} + \frac{1}{a}\) であるから, \(a\) 自体が min, max のとき \(f(a)\) が min, max (順序は一致するとは限らない).

 

3文字ver
\(b,c\) を固定したときの \(f(a) := \frac{a+b+c}{abc} = \frac{a+(b+c)}{a(bc)}\) の min, max を考える. これは, \(b+c, bc\) を一塊と思えば, 2文字ver に一致する.
よって,\(f(a)\) の min, max を実現する \(a\) としての候補は 少ないと分かる. \(X\)を \(ms(A)\) の max 上から 3つ と \(ms(A)\) の min 下から 3つ の multiset としての和とする. 先に \(b,c\) を固定した上で \(a\) を探しているから, \(a\) の候補は, \(X\) のどれか. ここで, \(ms(A)\) は vector \(A\) を multiset とみなしたもの.
同様に, \(b,c\) も \(X\) からとれる. \(a,b,c\) の候補が少ないと分かったので,あとは全探索. \({}_{6}C_{3}\) 通り試せばよい.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"