I impressed 100 nobles and the Queen on my first time playing the game and I have maintained a 100% record in all my playthroughs. I just listen to the music and match the button presses with the rhythm. I guess being musical has helped a lot with my timing.