概要

各曲について、最後の行を歌うのが高橋君かどうかを判定し、その曲数を数えます。提示コードでは、歌う人を1行ごとに切り替えるシミュレーションを行います。

考察

どの曲も、高橋君から歌い始めて、1行ずつ交互に歌います。したがって、歌う人は次のようになります。

• 奇数行目：高橋君
• 偶数行目：青木君

つまり、\(A_i\) が奇数なら、その曲の最後の行は高橋君が歌います。

例えば、行数が \(3, 4, 1\) の3曲では、最後の行を高橋君が歌うのは行数が \(3\) と \(1\) の曲なので、答えは \(2\) です。

奇数かどうかを直接調べる方法でも解けますが、提示コードでは、1行ごとに歌う人を切り替えています。この素朴な方法でも、処理する行数は最大で \(100 \times 1000 = 100000\) 行なので、十分に間に合います。

ただし、各曲は必ず高橋君から歌い始めることに注意が必要です。前の曲の歌い手の状態を引き継ぐと、誤答になる場合があります。

アルゴリズム

歌う人の状態を表す真偽値 takahashi を使います。各行の処理後に、true なら高橋君、false なら青木君がその行を歌ったことを表します。

1. 答えを保存する変数 cnt を \(0\) にする。
2. 各曲について、次の処理を行う。
   1. 歌詞の行数 a を読み込む。
   2. takahashi を false に初期化する。
   3. \(1\) 行目から a 行目まで、takahashi = !takahashi によって状態を反転させる。
   4. 最後に takahashi が true なら、cnt を \(1\) 増やす。
3. cnt を出力する。

最初の反転で true になるため、1行目を高橋君が歌うことを表せます。その後も反転するたびに歌う人が切り替わるので、a 回反転した後の状態から、最後の行を歌った人が分かります。

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N} A_i\right)\)
  各曲について、歌詞の行数だけ状態を反転させます。
• 空間計算量: \(O(1)\)
  各曲の行数を読み込むたびに処理するため、配列などは必要ありません。

実装のポイント

• ! は真偽値を反転する演算子です。true は false に、false は true になります。

• takahashi の初期値を false にするのは、1行目の処理で反転させて true にするためです。

• 状態の反転は、ちょうど a 回行います。提示コードでは line = 1 から line <= a まで繰り返しています。

• 奇数・偶数の性質を直接利用するなら、内側のループの代わりに a % 2 == 1 を判定することもできます。その場合、時間計算量は \(O(N)\) になります。

  ソースコード

// 問題文から独立に実装: 各曲で 1 行ずつ交互に歌う様子をそのまま追う
#include <iostream>
int main() {
    int n; std::cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        int a; std::cin >> a;
        bool takahashi = false;             // who sings the current line
        for (int line = 1; line <= a; ++line) takahashi = !takahashi;
        if (takahashi) cnt++;
    }
    std::cout << cnt << std::endl;
}

---

この解説は gpt-6-astra-medium によって生成されました。