概要

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

考察

どの曲も高橋君から始めて、\(1\) 行ずつ交互に歌うため、担当する行は次のようになります。

• 高橋君：\(1, 3, 5, \ldots\) 行目（奇数行）
• 青木君：\(2, 4, 6, \ldots\) 行目（偶数行）

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

例えば、歌詞の行数が \(3, 4, 7\) の場合、\(3\) 行と \(7\) 行の曲では高橋君が最後を歌い、\(4\) 行の曲では青木君が最後を歌います。よって答えは \(2\) です。

素朴には、各曲について \(1\) 行ずつ歌う人を切り替えるシミュレーションでも解けます。この制約では十分間に合いますが、行数の偶奇だけを調べれば、シミュレーションは不要です。

なお、曲が変わるたびに高橋君から歌い始める点に注意してください。前の曲の続きとして歌う人を切り替えると、誤った答えになることがあります。

アルゴリズム

1. 曲数 \(N\) と、各曲の行数を格納した配列 \(A\) を読み込みます。
2. 各行数 \(A_i\) について、\(2\) で割った余りが \(1\) かどうかを調べます。
3. 余りが \(1\) である曲の数を数え、出力します。

この判定は「最後の行を高橋君が歌う」という条件と一致するため、数えた値が求める答えです。

計算量

• 時間計算量: \(O(N)\) — 各曲の行数を一度ずつ調べます。
• 空間計算量: \(O(N)\) — 入力された行数をリストに保存します。集計に使う追加領域は \(O(1)\) です。

実装のポイント

• Python では x % 2 == 1 で、x が奇数かどうかを判定できます。

• sum(1 for x in a if x % 2 == 1) は、奇数の要素ごとに \(1\) を加算することで、その個数を求めています。

• 条件に当てはまる曲がない場合も、sum によって正しく \(0\) が得られます。

  ソースコード

# 問題文から独立に実装: 行数が奇数なら最後の行は高橋君
n = int(input())
a = list(map(int, input().split()))
print(sum(1 for x in a if x % 2 == 1))

---

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