問題の概要

\(N\) 曲の唱歌を歌う。\(i\) 曲目の歌詞は \(A_i\) 行あり、高橋君が奇数行目、青木君が偶数行目を歌う。最後の行（\(A_i\) 行目）を高橋君が歌う曲の数を求める。

解法

\(1\) 行目を高橋君が歌い、以降 \(1\) 行ずつ交互に歌うので、行番号 \(k\) を歌うのは \(k\) が奇数なら高橋君、偶数なら青木君である。したがって最後の行（\(A_i\) 行目）を高橋君が歌うことと \(A_i\) が奇数であることは同値である。

よって、\(A_i\) が奇数であるような \(i\) の個数を数えればよい。

正しさの証明

補題: 行番号 \(k\)（\(1 \leq k \leq A_i\)）を歌うのは、\(k\) が奇数のとき高橋君、\(k\) が偶数のとき青木君である。

証明: \(k\) についての帰納法で示す。\(k = 1\) のとき高橋君が歌う（問題文より）。\(k \geq 2\) のとき、\(k - 1\) 行目を歌った人と交互に歌うので、\(k - 1\) が奇数（高橋君）なら \(k\) は偶数で青木君、\(k - 1\) が偶数（青木君）なら \(k\) は奇数で高橋君。いずれも補題の主張と一致する。

定理: このアルゴリズムは「最後の行を高橋君が歌う曲の数」を正しく出力する。

証明: 補題より、\(i\) 曲目の最後の行である \(A_i\) 行目を高橋君が歌うことと \(A_i\) が奇数であることは同値。アルゴリズムは \(A_i\) が奇数である \(i\) の個数を正確に数えるので、求める答えと一致する。

計算量

• 時間計算量: \(O(N)\)（各 \(A_i\) を一度だけ調べる）
• 空間計算量: 入力全体を一括で読み込む Python 実装では \(O(N)\)、C++ 実装では各 \(A_i\) を逐次読み込んでその場で判定するため \(O(1)\) の補助空間（出力用カウンタのみ）

実装上の注意

• 引き分け（同数など）の扱いは存在しない。数え上げのみを行う。
• \(A_i\) は \(1\) 以上なので「\(0\) 行の曲」といった例外は考慮不要である。