概要

各曲の歌詞の行数が奇数かどうかを調べ、奇数である曲の数を数えます。

考察

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

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

したがって、\(i\) 曲目の最後の行である \(A_i\) 行目を高橋君が歌う条件は、\(A_i\) が奇数であることです。

例えば、\(A_i = 3\) なら「高橋君 → 青木君 → 高橋君」となり、最後は高橋君です。一方、\(A_i = 4\) なら最後は青木君になります。

1 行ずつ歌う人をシミュレーションしても、この制約では十分間に合います。ただし、最後の行を歌う人は行数の偶奇だけで分かるため、すべての行を確認する必要はありません。

また、曲が変わるたびに高橋君から歌い始めることに注意してください。前の曲から交互に歌う順番を引き継ぐと、誤った答えになる場合があります。

アルゴリズム

1. 曲数 \(N\) と、各曲の歌詞の行数 \(A_1, A_2, \ldots, A_N\) を読み取ります。
2. 各 \(A_i\) について、\(2\) で割った余りが \(1\) かどうかを調べます。
3. 余りが \(1\) である曲の数を数え、出力します。

例えば、行数が \([3, 4, 1, 6, 5]\) の場合、奇数は \(3, 1, 5\) の \(3\) 個なので、答えは \(3\) です。

計算量

• 時間計算量: \(O(N)\)
  各曲の行数を一度ずつ調べます。
• 空間計算量: \(O(N)\)
  提示コードでは、読み取った入力を data に保存します。集計そのものに必要な追加領域は \(O(1)\) です。

実装のポイント

• int(data[i]) % 2 == 1 で、行数が奇数かどうかを判定します。% は割り算の余りを求める演算子です。

• data[0] は曲数 \(N\) なので、行数が格納されている data[1] から data[n] までを調べます。Python の range は終端を含まないため、range(1, n + 1) とします。

• sum(1 for ... if ...) は、条件を満たすたびに \(1\) を加算し、該当する曲の数を求めています。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    count = sum(1 for i in range(1, n + 1) if int(data[i]) % 2 == 1)
    print(count)

main()

---

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