What makes adaptive memory attack difficult for the adversary?
The game is not trivial for the adversary to win because the author is suppressing $ENC\hspace{.02 in}$'s randomness, which makes it so for most PKE systems it will be the case that $\; \operatorname{Prob}\left(ENC_{PK}(m) = ENC_{PK}(m)\right)$

is exponentially small, in which case the probability that either $ENC_{PK}(m_{\hspace{.02 in}0})$

or $ENC_{PK}(m_1)$ matches the challenge ciphertext is also exponentially small.

"state" is the contents of $A$'s memory locations during step 3,
when there's just an $A$ rather than an $A1$ and an $A2$.