JOI '09 本選：４- 散歩
問題
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf
解法
1 ~ (N - 1) 回目にたどり着いた場所を知る必要はない．また，詳しいルートを１回ずつ区別して計算する必要はない．なぜならば，N 回目のルートやたどり着く場所に影響を与えないからであり，各交差点を 1 ~ (N - 1) 回目のルートで何回通ったかが重要になる．
まず，交差点 (1, 1) を当然 (N - 1) 回通る．この後，(1, 1) が「東」ならば (1, 2) を [(N - 1) / 2] ((N - 1) が奇数の時は +1) 回，「南」ならば [(N - 1) / 2] 回通る．同様に (2, 1) を [(N - 1) / 2] 回，「南」ならば [(N - 1) / 2] ((N - 1) が奇数の時は +1) 回通る．整理すると，
(x, y) を T 回通るとき，
- (x, y) が「東」ならば，(x, y + 1) を [T / 2] (T が奇数の時は +1) 回，(x + 1, y) を [T / 2] 回通る．
- (x, y) が「南」ならば，(x, y + 1) を [T / 2] 回，(x + 1, y) を [T / 2] (T が奇数の時は +1) 回通る．
となる．これを全ての交差点について計算し，N 回目の時に各交差点が「東」か「西」のどちらを示しているのかを知ることが出来る．あとはこの状態でシミュレーションして答えを求めればよい．O(HW)．N は時間計算量に関係ない．
解答
