けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 024 A - Fairness (灰色, 300 点)

AtCoder AtCoder300点 AGC-A 操作 収束性に着目する パリティ 周期性に着目する 灰色diff 操作後の結果を求める問題

少し手を動かせば見えてくる！

問題概要

高橋君、中橋君、低橋君は、それぞれ整数 A,B,C を持っている。 以下の操作を K 回行った後の、高橋君の持っている整数から中橋君の持っている整数を引いた値を求めよ。ただし、答えの絶対値が 10^{18}を超える場合は、代わりに Unfair と出力せよ。

  • 3 人は同時に、他の 2 人の持っている整数の和を求める
  • その後、自分の持っている整数を求めた整数で置き換える。

制約

  • 1 \le A, B, C \le 10^{9}
  • 0 \le K \le 10^{18}

考えたこと

K 回シミュレーションを行う解法では O(K) の計算量を要してしまうので間に合わない。そのシミュレーション解法を改善する手段もすぐには見当たらないため、一見手がつかないと感じる問題かもしれません。

このような問題では「まず小さいケースについて、手を動かして様子を観察する」ことが大切だと思われる。入力例 1 を試してみる。

  • 操作前：3 人の整数は (1, 2, 3) で、1 - 2 = -1
  • 1 回操作後：3 人の整数は (5, 4, 3) で、5 - 4 = 1
  • 2 回操作後：3 人の整数は (7, 8, 9) で、7 - 8 = -1
  • 3 回操作後：3 人の整数は (17, 16, 15) で、17 - 16 = 1
  • 4 回操作後：3 人の整数は (31, 32, 33) で、31 - 32 = -1

この様子を観察すると、たしかに 3 人の整数はどんどん大きくなっていくけれど、高橋君と中橋君の整数の差は、

-1, 1, -1, 1, -1, ...

と周期的になっていることが見て取れる。他のケースとして、たとえば (10, 4, 5) などを試してみる。ここでも同様に、

6, -6, 6, -6, 6, ...

と周期的になることが見て取れる。

　

周期性を活用

実際のコンテストでは、この時点で規則性を確信して、次のように考えてコードを提出してよさそう。計算量は O(1)。

  • K が偶数のとき： A - B が答え
  • K が奇数のとき： B - A が答え

ここでは、念のために一般論を確認しておく。一般に 3 人の整数が (A, B, C) であるとき、操作後には (B+C, C+A, A+B) となる。操作前後で高橋君と中橋君の整数の差をとると、

  • A - B から B - A へと変化

したことがわかる。これは「操作を行うと差が -1 倍になること」を意味する。よって、2 回行うと、 (-1) \times (-1) = 1 より、元の数に戻ること、つまり周期 2 で繰り返すことが示されxた。

　

コード

#include <iostream>
using namespace std;

int main() {
    long long A, B, C, K;
    cin >> A >> B >> C >> K;
    if (K % 2 == 0) cout << A - B << endl;
    else cout << B - A << endl;
}