Here's a deterministic solution that does at least as well as hiding the coin randomly (I think?). Take the expected amount of time t it would take to find the coin by random search. Write down all the deterministic coin-hiding algorithms you can think of on a piece of paper as fast as you can, starting with the most obvious. Continue until t time units have elapsed, and then use the last algorithm you thought of.

This does assume we're counting the time it takes your future self to compute your hiding algorithm towards the time it takes him/her to find the coin.