Overview

For each song, we determine whether Takahashi sings the last line and count the number of such songs. The provided code simulates this by switching the singer line by line.

Analysis

For every song, Takahashi starts singing first, and they take turns singing one line at a time. Therefore, the singers for each line are as follows:

• Odd-numbered lines: Takahashi
• Even-numbered lines: Aoki

In other words, if \(A_i\) is odd, Takahashi sings the last line of that song.

For example, across three songs with \(3, 4, 1\) lines, Takahashi sings the last line of the songs with \(3\) and \(1\) lines, so the answer is \(2\).

While this can be solved by directly checking whether the number of lines is odd, the provided code toggles the singer line by line. Even with this naive approach, the maximum number of lines to process is at most \(100 \times 1000 = 100000\), which easily runs in time.

However, note that each song must always start with Takahashi singing. Carrying over the state of the singer from the previous song may lead to a wrong answer.

Algorithm

We use a boolean variable takahashi to represent the state of the singer. After processing each line, true indicates that Takahashi sang that line, and false indicates that Aoki sang it.

1. Initialize the variable cnt to store the answer to \(0\).
2. For each song, perform the following:
   1. Read the number of lyrics lines a.
   2. Initialize takahashi to false.
   3. From the \(1\)-st line to the a-th line, flip the state using takahashi = !takahashi.
   4. Finally, if takahashi is true, increment cnt by \(1\).
3. Output cnt.

Because the first inversion sets it to true, it correctly represents Takahashi singing the 1st line. Since the singer alternates every time it flips, the state after flipping a times tells us who sang the last line.

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N} A_i\right)\)
  For each song, the state is toggled as many times as the number of lines in the lyrics.
• Space complexity: \(O(1)\)
  Since we process each song as soon as its number of lines is read, no arrays or additional data structures are needed.

Implementation Notes

• ! is the operator that negates a boolean value. true becomes false, and false becomes true.

• We initialize takahashi to false so that flipping it during the processing of the first line makes it true.

• Flipping the state is performed exactly a times. In the provided code, it loops from line = 1 to line <= a.

• If you directly use the parity (even/odd property), you can check a % 2 == 1 instead of using the inner loop. In that case, the time complexity would be \(O(N)\).

  Source Code

// 問題文から独立に実装: 各曲で 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;
}

---

This editorial was generated by gpt-6-astra-medium.