Ultima Weapon is actually fairly easy. You have to fight him five times, I think. Between each battle you can heal yourself, but Ultima Weapon can't. Like Doomgaze from FF6.