yukicoder No.1209 XOR Into You - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${A}$ と ${B}$ が与えられる. ${1\leq i\leq N-2}$ となる ${i}$ を選んで ${A_{i+1}}$ を ${A_i\oplus A_{i+1}\oplus A_{i+2}}$ に変更する. この操作を何回か行って ${A=B}$ にできるとき, 最小操作回数を求めよ.

${3\leq N\leq 10^5\\ 0\leq A_i,B_i < 2^{30}}$

思考の流れ

隣り合ったものに対して操作を行う場合, 隣り合ったものの差を考えるとうまくいくことがある. 今回の問題で言う「差」は, 排他的論理和である.

${\downarrow}$

${D_i=A_i\oplus A_{i+1}}$ とすると, ${i}$ に対して操作を行うと, 操作後の ${D}$ の値を ${D'}$ として

${D_i'=A_i\oplus (A_i\oplus A_{i+1}\oplus A_{i+2})=A_{i+1}\oplus A_{i+2}=D_{i+1}\\ D_{i+1}'=(A_i\oplus A_{i+1}\oplus A_{i+2})\oplus A_{i+2}=A_i\oplus A_{i+1}=D_i}$