Solution:

Let $n$ be the number of women; only the pattern of men's and women's positions matters. If every man stands next to another man, the men form maximal blocks whose sizes, in order, are $2+2+2,$ $2+4,$ $4+2,$ $3+3,$ or $6.$ A pattern with $j$ blocks amounts to choosing $j$ of the $n + 1$ gaps determined by the women, so there are $\binom{n+1}{3}$ patterns for $2+2+2,$ $\binom{n+1}{2}$ for each of the three two-block orders, and $n + 1$ for a single block.

At least four men stand together in the orders $2+4,$ $4+2,$ and $6,$ so $$p = \frac{2\binom{n+1}{2} + (n+1)}{\binom{n+1}{3} + 3\binom{n+1}{2} + (n+1)} = \frac{(n+1)^2}{\frac{(n+1)(n^2 + 8n + 6)}{6}} = \frac{6(n+1)}{n^2 + 8n + 6}.$$

The condition $p \le \frac{1}{100}$ becomes $f(n) = n^2 - 592n - 594 \ge 0.$ Since $f(593) = 593 - 594 = -1 \lt 0$ and $f(594) = 2 \cdot 594 - 594 = 594 \gt 0,$ the least number of women is $594.$