UVa11296 Counting Solutions to an Integral Equation

概要
非負整数 n が与えられる。x. y, z を非負整数として、x+2y+2z = n となるパターン数を求めよ。
ただし n < 1000001 であり、テストケースは最大で 1500 である。

解答
TLEにならないように一重ループ以内で解きたい。

x+Y=n と書き換えると、Y は偶数である必要性が生じる。よって問題文を以下のように解釈し直す。
「n以下の非負整数xがある。n-x が偶数であるとき、 (n-x)/2 を２つに分けるパターン数を求めよ。」
すると以下のように O(n) で解が求まる。

#include <iostream>

using namespace std;

int main() {
  
  int n;
  while(cin >> n) {
    long long ans = 0;
    int ini = n & 1;
    for(int x=ini; x<=n; x+=2) {
      ans += (n-x)/2+1;
    }
    cout << ans << endl;
  }
  
  return 0;
}