Tenka1 Programmer Contest

Updated: 2017-09-30

Source codes

$1 \leq x, y \leq 3500$ に対し、 $1/z = 4/N - 1/x - 1/y$ を充たす $z$ を計算機の割り算で求め、 $N(xy + yz + zx) = 4xyz$ を充たすか確かめる。

最初は代数的にやろうと思っていたけどよくなかった。制約条件を見て、これは全探索しろという問題だと理解するべきだった。 60 分を失ったのは残念だ。

bitwize or なので、 sup を決めて貪欲にとっていけば良い。

sup の候補は以下のようにして求める。説明のため $K = 101010101_2$ とする。この時 $K$ そのものは候補である。他にも $sup = 011111111_2$ も候補である。これだけではなくて、その中間に値する $sup = 101001111_2$ も候補である。

だから、 $K$ と $1 \dots 10 \dots 0$ を and したものから $1$ を引いたものも候補である。

最初の 2 つしか候補でないと思っていたけど、サンプルで気づくことができ、かつ、プログラムの改修も難しくはなかったので AC もらえた。

フェルマー点を思い出したところで時間切れ。

今年は大学受験に出てくるような数学の問題が多かった。昔に戻ったようで、楽しめた。