A. Sum of Odd Integers (Educational Codeforces Round 84)

問題

https://codeforces.com/contest/1327/problem/A

問題概要

2つの整数nとkが与えられる。nがk個の相異なる正の奇数で表現可能かどうかを答えよ。

考察

k個の相異なる正の奇数で作れる数のうち最小のものは、初項1公差2の等差数列の和です。nがこの和より小さい場合は、表すのが無理なので答えは"NO"です。

また、この数列の項は全て奇数ですから、数列の和はkが奇数の場合奇数、kが偶数の場合偶数となります。よってnとkの偶奇が一致しない場合も"NO"です。

上記の2つに当てはまらない場合、答えは必ず"YES"です。なぜなら、最初に求めた等差数列の和より大きくて偶奇が一致する整数は隙間なく無限に作ることが可能だからです。 例えばK = 3のとき最小は1+ 3+ 5 = 9で、いずれかの項を2増やすと11が、さらにいずれかの項を2増やすと13が作れるという具合です。

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        if (n < k * (1 + 2 * k - 1) / 2) {
            cout << "NO" << endl;
        } else {
            cout << (n % 2 == k % 2 ? "YES" : "NO") << endl;
        }
    }
}

反省

実戦では、distinctをスルーしてしまい1WA、等差数列の和がintの範囲を超えてしまいオーバーフローでさらに1WAを出してしまいました。問題文はちゃんと読みましょう and 競プロをやる上での基本を忘れないようにしましょう。