　$s(n) = \lfloor\sqrt n\rfloor, p(n) = n - s(n)^2$ とすると
$$ \left\lfloor\sqrt n + 0.5\right\rfloor = \left\lfloor\sqrt n\right\rfloor \iff p(n) \le s(n)$$
である．また，$n\gt0$ のとき $n-1, n-2\left\lfloor \sqrt{n}\right\rfloor + 1$ はともに $n$ より小さいから，$0 \in S$ である．\
　ここで，座標平面上の点の集合 $T$ を $T = \\{(p(n),s(n)) \mid n\in S\\}$ で定めると，問題の条件は，以下のように書き換えられる．
- $(9,35)\in T.$
- 任意の $(a,b)\in T$ に対し，$a\le b.$
- $(0,0)$ でない任意の $(a,b)\in T$ に対し，$\\#(T\cap\\{(a-1,b),(a,b-1)\\}) = 1.$
- $(9,35)$ でない任意の $(a,b)\in T$ に対し，$\\#(T\cap\\{(a+1,b),(a,b+1)\\}) = 1.$

従って，$T$ の要素を適当に並び替えることで，$(0,0)$ から $(9,35)$ まで直線 $y = x-1$ 上の点を通ることなく隣り合う格子点を通って最短経路で行く経路が得られる．逆に，このような経路に対して条件を満たす $T$ が一つ対応するので，このような経路の数を求めればよい．これは，いわゆる「鏡像法」によって，
$${}\_{44}\mathrm{C}\_{9} - {}\_{44}\mathrm{C}\_{8} = \frac{27 \times 44!}{9! \times 36!} = \bf{531697881}$$
と計算できる．
公式解説
https://onlinemathcontest.com/contests/omce006/editorial/6903
　以下の条件を全て満たす非負整数の集合 $S$ はいくつありますか．
* $\max S = 1234. $
* 任意の $n \in S$ に対し $\left\lfloor\sqrt n + 0.5\right\rfloor = \left\lfloor\sqrt n\right\rfloor$ および$$\\#(S \cap \left\\{n - 1,\\, n - 2 \left\lfloor\sqrt n\right\rfloor + 1\right\\}) = 1$$が成り立ち，さらに $n \lt 1234$ ならば$$\\#(S \cap \left\\{n + 1,\\, n + 2 \left\lfloor\sqrt n\right\rfloor + 1\right\\}) = 1$$も成り立つ．

　ただし，$\max S$ で $S$ に含まれる最大の要素を表し，$\\#X$ で集合 $X$ の要素数を表します．