OK, so another option for you is to use Trichlor either as tabs or granular. The most common black algaecide is in fact Trichlor granular. The high chlorine level and low pH combine to be potent, BUT you can only use this on a plaster surface as it will destroy vinyl. Unfortunately, your concrete pool is painted so it would likely bleach out the paint, but if your paint is white then it might be OK. You could try a little in an area you don't care about and see if it leaves a mark. Of course, this method may work on the floor, but not for the walls.

Are you positive you have black algae? If you are able to scrape some off and spread it on a piece of paper, it should look dark green and not black. It is possible that you might have some metal staining instead. If you have metal stains, then lowering the pH of the pool would lighten them up. Also, putting some ascorbic acid (Vitamin C) would remove the stain if it were iron (if copper, then only the acid would lighten it).