C++
 Computer >> コンピューター >  >> プログラミング >> C++

最初のn個の自然数を2つの集合に分割したときの合計の最小差を求めるC++プログラム

数 n が与えられたとき、最初の n 個の自然数（1 から n までの整数）を考えます。これらを2つの集合 A と B に分割します。ただし、各要素は必ずどちらか一方の集合にのみ属するものとします。このとき、集合 A の要素の合計と集合 B の要素の合計の絶対差が最小になるように分割し、その最小の差を求めます。

問題例

例として、n = 5 の場合を考えてみましょう。

A = {1, 3, 4}、B = {2, 5} と分割すると、それぞれの合計は 8 と 7 となり、差は 1 になります。これより小さい差は実現できないため、答えは 1 となります。

解き方のポイント

まず、最初の n 個の自然数の総和は次の公式で求められます。

S = n × (n + 1) / 2

この総和 S を2つの集合にできるだけ均等に分けることを考えると、次のことが分かります。

  • S が偶数の場合： S をちょうど半分ずつに分けられるため、最小差は 0
  • S が奇数の場合： 半分に分けたとき必ず 1 の差が残るため、最小差は 1

したがって、答えは「総和 S を 2 で割った余り」、すなわち次の式だけで O(1) で求められます。

return (n * (n + 1) / 2) % 2;

C++による実装例

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

int solve(int n) {
    return (n * (n + 1) / 2) % 2;
}

int main() {
    int n = 5;
    cout << solve(n) << endl;
}

入力

5

出力

1
  1. Pythonで2つのリストの要素間の最小差を求めるプログラム

    2つのリスト間の最小差とは2つのリスト L1 と L2 が与えられたとき、L1 のある要素と L2 のある要素を組み合わせたときに生じる「差」の中で、最も小さいもの（絶対値が最小となる差）を求める問題です。例えば、入力が L1 = [2, 7, 4]、L2 = [16, 10, 11] の場合、出力は 3 になります。これは、10 − 7 = 3 という差が最も小さいためです。解法のアプローチ：ソート＋双方向ポインタこの問題は、両方のリストをソートしてから、2つのポインタを使って効率的に比較していくことで解けます。手順は以下の通りです。リスト L1 をソートし、リスト L2 もソートするans

  2. Pythonでシフト後の2つの数表間の最小差を求める方法

    ```html 問題の概要 2つの数 p と q が与えられたとき、それぞれの数が持つ無限に続く倍数の表（九九の表）を考えます。これらの表をそれぞれ r と s（ただし r, s >= 0）だけシフトした場合、2つのシフト済み表の項同士における最小の差を求めるのが本記事のテーマです。 例として、p = 7、q = 17、r = 6、s = 3 の場合の出力は 0 になります。 7の表：[7, 14, 21, 28, 35, 42, 49, ...] 17の表：[17, 34, 51, 68, 85, 102, 119, ...] 7の表を6シフトした表：[13, 20, 27, 34,