AOJ-ICPC 2197

先ほど1問解いてきました。メモ。

Sum of Consecutive Integers | Aizu Online Judge

n=6であれば1+2+3、n=9であれば4+5と2+3+4、というように和がnと一致するようないくつかの連続する整数の組み合わせはいくつあるかを求めよ、という問題。

わたしの解答はこんな感じ。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
 
using namespace std;

bool solve(int n, int i);

int main()
{
    int n;
    while(1){
        cin >> n;
        if(n == 0) break;
        int ans = 0;
        for(int i = 2; i <= n / 2 + 1; i++){
            if(solve(n, i)) ans++;
        }
        cout << ans << endl;
    }
   return 0;
}

bool solve(int n, int i)
{
    int a = n / i;
    for(int j = a - (i / 2) - 1; j < a + 1; j++){
        int sum = 0;
        if(j <= 0) continue;
        for(int k = 0; k < i; k++){
            sum += j + k;
        }
        if(sum == n){
            return true;
        }
    }
    return false;  
}

i個の連続する数で和がnに一致するものがあるのかをチェックするのがsolveです。
n / i の値はだいたい連続する整数の真ん中に来るはずなのでそれを中心に考えてみました。
そこから候補をしぼって実際に和が一致するものがあるかをチェックする、という感じです。
なんか非常に説明しづらい。
途中jが正の数という条件をつけわすれていたのに気づかず3回wrong answerを叩き出しました。本番だったら解答権を失ってます。よくない。
気をつけないといけませんね。

ところで、この解答でのCPU Timeは00.01secでした。
解き終わってから今年の4月ごろ書いた自分の解答を確認してみました。
それがこちら。

#include <cstdio>
#include <iostream>
#include <list>
 
int main()
{
    int n;
    while(1){
        std::cin >> n;
        if(n == 0) break;
        int sum=0, cnt=0;
        for(int i = 1; i <= n/2; i++){
            sum = i;
            for(int j = i+1; j < n; j++){
                sum += j;
                if(sum > n) break;
                if(sum == n){
                    cnt++;
                    break;
                }
            }
        }
        std::cout << cnt << std::endl;
    }
    return 0;
}

非常に単純です。
ある数字からそのあとに続く数を加えていって、その和がnを越えたら別の数字から始めるようにしています。
この解答でのCPU Timeは00.00secでした。
昔の解答の方がわかりやすくて、時間もかからなくて、なんだかとても悔しくなりました。
成長できてない証拠ですね。むしろ退化してる感。

うーん…がんばらねば…。