c問題は比較的簡単ですぐにできた。D問題は解法は思い浮かんだが計算時間的に間に合わない解法であり、しゃくとり法を使わなければ解けない問題だったので解けなかった。
https://atcoder.jp/contests/abc098/tasks
C問題
方針
どの位置が振り向く人が少なくて済むかを求める問題。Nが10の5乗なので全探索していては間に合わない。よって、まず定数でできないか考える。まずi番目の人がリーダーになった時に振り向く人数について考えると、i番目より左側ではEの人数であり、i番目より右側ではWの人数である。よって、1~N番目の人についてそれぞれその人より左側のEの人数と右側のWの数をあらかじめ保持しておけば定数で解くことができる。したがって、Eについての累積和とWについての累積和を求めることで最終的に定数で解くことができる。
D問題
方針
はじめは、累積和を取り、その後xorが偶奇かを判断するため、各A[i]について各2iが割り切れるかどうかを求めておき、全探索をする解法を思いついたが明らかに計算量がN!*20以上になり間に合わない。ここで、左端をl,右端をrとすると,求める組み合わせというのは、lからr番目までのA[i]の和とxorが一緒の数である。この和とxorの性質について考察すると以下のような図になる。
よって、一回でも繰り上げがあって和とxorが変わってしまうと、それ以降ずっと和とxorは変わってしまうので、しゃくとり法の要領で右端と左端を更新しながらカウントしていくことで定数で答えを求めることができる。