ARC 105-Bの解答

ARC 105-B MAX-=minの解答を書きます。問題はこちらから。

B - MAX-=min

Difficulty : 275（灰色）

1から n までの番号のついた n 枚のカードがあります。カード i には整数 aiが書かれています。次の操作を行います。

１　カードの最大値を X , 最小値を x とする。
２　X = xなら終了。そうでないなら X のカードを X-xに置き換え、１に戻る。

この制約下だといつか終了することが保証されているそうです。終了後にカードに書かれた唯一の数字は何ですか？という問題。

先に述べますが、模範解答にあるような最大公約数を用いた解法をしておりません。そのため、私の手法だとpythonのような処理の遅い言語だとTLEしてしまうかもしれません。試験後に私がpythonで実装したときはダメでした。

（どうやら、この解法はテストケースは通るだけで最も時間のかかるケースだとC++でも通らないようです。そのため最後に更に高速化した解法、最大公約数の解法に少し触れます。）

愚直な解法となります。ではいきます。

まず、まったく工夫をせずに考えます。

n 個の数字を v(n) の配列に投げ込みます。v(n) の最小値と最大値を取ってきてその差 d を求めます。最大値を d に書き換えれば一通りの操作が完了します。手順をそのままプログラムにした感じです。

これを少しずつ早くします。

まず、操作２において「最大値を ”すべて” 差 d に置き換える」ので、２つ以上存在する数は１つにまとめることができます。

次に、最大値と最小値の取得を高速に行うために、配列をソートすることを考えます。小さい順にソートすれば1つ目が最小値で最後が最大値となります。

数の重複を解消して、勝手にソートしてくれるいい機能ないかなーって探してみると、これがあるんですね。「順序付集合：set」です。setは数を入れると勝手に小さい順に並べてくれます。そして、同じ数を入れた際にはその入力を無視します。

ただ、通常の配列と異なり、要素へのアクセスはイテレータを使う必要があることに注意です。

配列を set に置き換えて実装をしてあげます。以下実装です。

#include <bits/stdc++.h> 
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
   int n;
   cin >> n;
   vector<int> a(n);
   set<int> st;
   rep(i, n) {
       int b;
       cin >> b;
       st.insert(b);
   }
   while (1)
   {
       int mx, mn;
       auto itb = st.begin();
       auto ite = st.end();
       mn = *itb;
       mx = *--ite;
       if (mn == mx) break;
       int def = mx - mn;
       st.insert(def);
       st.erase(mx);
   }
   int ans = *st.begin();
   cout << ans << endl;
   return 0;
}

set を用いた以外はひねりもなく実装しています。

さて、先に述べた高速化と公約数について少し補足します。

まず、高速化です。

私の手法の最大ケースは{2 1 1000000000}となります。1000000000が1になるまで1を引くので、999999999回の処理が必要となります。これでは、間に合いませんね。

そのため、引き算と割り算の関係に立ち返ります。端的に言うと割り算は引き算を繰り返した演算になります（整数範囲）。10 ÷ 3 = 3 ...1ですよね。これって、10-3-3-3 = 3 ...1と同義です。

さて問題に戻ります。問題では最大値から最小値を引いた値を戻して、さらに最大値と最小値を・・・、という感じですね。結局のところ何度も引き算をした端くれを出力しているに過ぎないのです。それって割り算だよね、という話です。こうすれば、何度も引き算をしてなんとか出した結果を一発で出力できます。

その実装を書きます、と言いたいのですが、引き算部分を % に変えただけで面白くないので、pythonの実装を張っておきます（ただしこのコードでも間に合いません、さらに言うとc++でも新しい最大ケースが生じ、それは通らない気がしています）。

n = input()
a = set(map(int,input().split()))
mn = min(a)
mx = max(a)
while(mn != mx):
 d = mx % mn
 if(d != 0): a.add(d)
 a.discard(mx)
 mx = max(a)
 mn = min(a)
print(mn)

端くれが 0 なら捨てちゃいましょう。

さて、最後は模範解答にもあった最大公約数gcdです。本問題はgcd(x,y) = gcd(x, y-x)から、全数字にgcdを使えば一発で答えが求まります。

これはなんでだ？とはじめは思いましたが、上記の引き算と割り算、そしてその余りの関係を考えたら理解できました。これ完全にユークリッドの互除法をそのまま適用しているだけでしたね。

試しに、ユークリッド互除法にて8 と 36 の公約数を求めます。

36 - 8 = 28
28 - 8 = 20
20 - 8 = 12
12 - 8 = 4
8 - 4 = 4

となって、最大公約数は 4 です。-8を複数回やっていますが引き算を割り算にすれば1回で済みます。

何をしているんだ？という人のために図も用意しました。

〇〇〇〇〇〇〇〇｜〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇〇

〇〇〇〇〇〇〇〇

↓

〇〇〇〇〇〇〇〇｜〇〇〇〇〇〇〇〇 | 〇〇〇〇〇〇〇〇 | 〇〇〇〇

〇〇〇〇〇〇〇〇

↓　（長くなるので割ります）

〇〇〇〇

〇〇〇〇 | 〇〇〇〇

↓

〇〇〇〇

〇〇〇〇

同じ個数存在する最も長い丸の集合（最大公約数）は４です。今は2つの数でやりましたが複数あっても同じです。列を3列, 4列に増やすだけです。

（ユークリッドの互除法に関して、いつも長方形の説明を聞いてましたが、今回、列でやるやり方を知りました。こっちのほうがわかりやすいやん。）

結局、長々と書いてしまいました。問題の範囲内のあらゆる状態に対応する場合はgcdを使えば間違いないです。ただ、コンテスト中はどんな解法だろうと通した人が勝ちなので、どうにかできないかと足掻いてみるのも悪くないと思います。

もちろん試験後は綺麗な解答を確認しましょう。今回の私みたいに。