らての精進日記

修行をします

aoj0057:The Number of Area

解法

既に{\displaystyle k}本の線を最善の配置で引いているとして、{\displaystyle k+1}本目を引くことを考える。紙とペンを使ったりすると既に引いてある{\displaystyle k}本の直線すべてと交わるようにするといいことが分かる(ただし、三本以上の直線が同一の点で交わらないようにする)。このとき、領域は{\displaystyle k+1}か所増える。

さらにいうと、求める値は初項が{\displaystyle 2}で階差数列が{\displaystyle A_n=n+1}である数列であるので、総和の公式とかいろいろ使えば{\displaystyle O(1)}で計算できる。

コード

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        cout<<2+(n-1)*(2+n)/2<<endl;
    }
    return 0;
}