水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

PCK 2015 予選:6 - 品質管理

問題

Aizu Online Judge

解法

愚直に処理をすると O(C * N^2) になり間に合わない.ここで,前のコースターとの差分と前のコースターが左右対称になっているかだけがこのコースターが左右対称になっているかどうかを決めると考える.

実装時のテクとして(これもまた先輩にアドバイスを頂いたが),マス目が 0, 1 だけで表されているので,あるマスが置き換わるということはそのマス目に XOR 1 (^ 1) したということと同じである.そうするとコードが短くなっていい感じになる.全体の計算量は O(C + N) になり余裕で間に合う.

解答

Aizu Online Judge

f:id:babcs2035:20180823194053p:plain

gist.github.com