AtCoder ABC227
ABC227参加しました。
今回はB,Cだけ。
B - KEYENCE building
解説 - AtCoder Beginner Contest 227
提出 #27220116 - キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)
$ T = 4ab + 3a + 3b$とします。制約よりTは最大で1000までです。ということは、a,bの取りうる最大値は(a,bは対称的なので、どちらも)250です(4 * 250 * 1でぴったり1000)
つまりa,bともに1~250までfor文で二重ループを回せば、この問題でとりうるTの値が網羅できます。あとは、このTのリストに、入力されたSが存在すれば正解、なければ、絶対にありえないSの値となります。
C - ABC conjecture
解説 - AtCoder Beginner Contest 227
提出 #27238418 - キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)
公式解説の間を埋めてみようと思います。
図形的には、高さA, 縦B, 横Cの立方体の体積がN以下になるような(A,B,C)の値を求めるという問題です。ただしA,B,Cはこの順で大きくなります。
Aの取りうる範囲は$1 \le A \le \sqrt[3]{N}$です。
これは、B,Cが仮に$\sqrt[3]{x}$より大きい値をとることがないことから説明できそうでした。
例えばN=27のとき$\sqrt[3]{x} = 3$です。
(3, B, C)のとき、とりうるB,Cは(3,3)以外にありません。
Bの取りうる範囲は$A \le B \le \sqrt{ \frac{N}{A}}$です。
すでに高さAが決まっているので、長さが横B, 高さCの長方形を考えます。
このとき長方形の面積は最大で$ \frac{N}{A} $となるはずです。
(なぜなら、面積$\frac{N}{A}$のとき、高さAをかけることで、問題文の立方体の体積も最大値Nとなるためです。)
加えて$ B \le C$を満たすようにするとなると、Bは最大で$ B \le \sqrt{ \frac{N}{A}}$までしか取れません。
A,Bが決まった以上Cの取りうる範囲は説明不要でしょう。( $A \le B \le \frac{N}{AB}$)
あとはコードの解説。三乗根や平方根が出ると小数点誤差の扱いが面倒です。
つまり、
for(long a = 1 ; (double)a < Math.Pow(N, 1.0 / 3.0) ; ++a){ ...}
みたいなコードを書く必要がありますが、これは元の数式に立ち返ると見通しがよくなります。
$A \le \sqrt[3]{N}$ですが、両辺を3乗すると$A * A * A \le N$となり、数式的には全く同値でも、浮動小数点計算がいらなくなります。
同様に、$B \le \sqrt{ \frac{N}{A}}$ですが、両辺を2乗してAを右辺に持ってくれば$A * B * B \le N$となります。
競プロのコードでよく見る数式変形ですが、覚えておいたほうがよさそうです。
感想
Cは数式を変形して行く問題ですが、どこから手を付けていいのか迷いました。
Nの約数列挙をすればいけるかなと思いましたが、どうもそれではだめ(ABC=Nの場合ならこれでいけそう)。
具体例を考えると(A,B,C)=(1,1,1)~(1,1,N)までは必ず答えに入るから、ここから(1,2,N/2)も答えに入るし、みたいなことを考えていって結局まとまりがつかなくなりました。
真ん中のBって$1 \le B \le \sqrt{N}$だから、あとは$1 \lt A \le B$, $B \le C \le \frac{N}{B}$で範囲決まるよな、とか考えてたら時間がきました。
競プロへの情熱が保てなくなってきた。
