ARC098に参加しました (726位)

ARC098に参加しました。C問題を1回TLEしてD問題が解けず無事死亡しました。 レートは1334→1298ということで、微減ですね。 D問題が解けなかったのは久しぶりなので練習不足を感じます。 最近Kaggleが忙しくて過去問埋めもあまりできていません。

前回の記事

amalog.hateblo.jp

振り返り

C - Attention

振り向かせる人数は「その人より東に立っていて東を向いている人+その人より西に立っていて西を向いている人」で表されます。

予め東向き人数と西向き人数の累積和をとっておけば計算量を節約できます。

n = int(input())
s = input()
ans = float('inf')
E_total = s.count('E')
W_total = s.count('W')
cnt = {'E': 0, 'W': 0}
for i in range(n):
    turn = cnt['W'] + (E_total - cnt['E'])
    if s[i] == 'E':
        turn -= 1
    ans = min(ans, turn)
    cnt[s[i]] += 1
print(ans)

D - Xor Sum 2

何種類か試してみると気づきますが、区間の和とXORが一致するのは「2進数で和をとったときにどこも繰り上がらない(=各ビットに1が高々1回しか立っていない)」ときです。

今回の場合、少なくとも区間の幅が1の時にはSUMとXORが一致します。しゃくとり法で実装すれば良さそう。典型問題だなふむふむ。

とここまで考えておきながら実装で死亡してACできませんでした。なんじゃこりゃ。典型問題なんじゃなかったんかい。

N = int(input())
A = list(map(int, input().split()))
cnt = 0
tmp = 0
r = 0
for l in range(N):
    while r < N and tmp & A[r] == 0:
        tmp ^= A[r]
        r += 1
    cnt += (r-l)
    tmp ^= A[l] 
print(cnt)

補足としては、新しい要素を付けるときも要素を取り除くときも区間のXORと該当する要素のXORを取ればよいという性質は便利ですね。