B. Same Parity Summands (Codeforces Round #640 Div. 4)

問題

https://codeforces.com/contest/1352/problem/B

問題概要

整数nとkが与えられる。nをk個の非負整数の和として表した時、k個すべてを奇数またはk個すべてを偶数とする方法はあるか答えよ。ある場合は一例を示せ。

考察

まず、nよりkのほうが大きいときは分割できないので構築不可能です。

あとは1 1 1 ... n - (k - 1)としてn - (k - 1)が奇数になるか、2 2 2 ... n - ((k - 1) * 2)としてn - ((k - 1) * 2)が（正の）偶数になるかを満たせば構築可能で、どちらも満たさない場合は構築不可能となります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (n < k) {
            cout << "NO" << endl;
            continue;
        }
        if ((n - (k - 1)) % 2 == 1) {
            cout << "YES" << endl;
            for (int i = 0; i < k - 1; i++) cout << 1 << ' ';
            cout << n - (k - 1) << endl;
            continue;
        }
        if (n - ((k - 1) * 2) > 0 and (n - ((k - 1) * 2)) % 2 == 0) {
            cout << "YES" << endl;
            for (int i = 0; i < k - 1; i++) cout << 2 << ' ';
            cout << n - ((k - 1) * 2) << endl;
            continue;
        }
        cout << "NO" << endl;
    }
}

個人的反省

本番では場合分けを頑張りすぎてグダグダになってしまいました。

実装で場合分けが複雑になりすぎてるときは一旦算数の考察に戻った方がよいです。そして、導き出した条件を素直に実装してみましょう。

ということをしょっちゅう言っているような気がしますがなかなか改善されません・・・。