Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC098-C 「Attention」 (300)

方向音痴なので(?)混乱しがち。

問題リンク

概要

 N人の人が東西方向に一直線に並んでおり、文字列 Sについて西から i番目の人は S_iの方角を向いている。

ここで N人のうち誰か1人をリーダーとして認める。このとき、リーダー以外の全員はリーダーのいる方角を向かせる必要がある。 このとき、向きを変える人数の最小値を求めよ。

制約

  •  2 \leq N \leq 3 \times 10^5
  •  |S| = N
  •  SはEとWからなる。

解説

「そんな適当にリーダー決めて大丈夫なのか」という問題はさておき、実際に i番目の人をリーダーにしたときに何人が振り向くか考えてみよう。

まずリーダーより西にいる人。この人たちは最終的に東を向かなくてはならないため現在西を向いている人が全員振り向くことになる。 同様にリーダーより東にいる人については、現在東を向いている人が全員振り向くことになる。

これを各 iについて愚直に数え上げていると計算量が O(N^2)で間に合わない。そこで、累積和によってこれを高速化する。

具体的には、「 c_i = 西から i人目のうち西を向いている人の数 = i文字目までにいくつEがあるか」を保持する数列 c_iを作る。すると、 i人目をリーダーにしたときに振り向く人数は

  • リーダーより西にいて西を向いている人が c_{i - 1}
  • リーダーより東にいて東を向いている人が N - i - (c_N - c_i)

より、この和となる。後者は少し複雑なので、数直線に区間を書いたりすると分かりやすいだろう。

これなら累積和を求めるのに O(N)、解を求めるのに O(N)で余裕で間に合う。

実装例

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int cnt[N + 1];
    // i文字目までにWがいくつあるか(1-indexed)

    // 累積和テーブルを埋めていく
    cnt[0] = 0;
    for (int i = 0; i < N; ++i) {
        cnt[i + 1] = cnt[i];
        if (S[i] == 'W') ++cnt[i + 1];
    }

    int ans = N;
    for (int i = 1; i <= N; ++i) {
        // 自分より西にいて西を向いている人が
        //  cnt[i-1]人
        // 自分より東にいて東を向いている人が
        //  (N-i)-(cnt[N]-cnt[i])人
        ans = min(ans, cnt[i - 1] + (N - i) - (cnt[N] - cnt[i]));
    }
    cout << ans << endl;
    return 0;
}

上は解説のためにも丁寧にコメントが付いているが、本番で実装するときも変数や関数の定義を書くことは非常に大切である。というのも、定義を書いておけば実装の際にいちいち思い出さなくて済むし、使うときも定義に基づいて考えることがしやすいからだ。

感想

  • 累積和はindexで闇を見がちなので慣れよう。
  • 方向音痴なので東西より左右とか前後にしてほしかった。
    • 実装中もそこそこ脳内でバグらせていた。