C++ の動作確認をしてみた（８８７）

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題E (Increasing LCMs) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 解説のロジックで, 正整数列の構築が出来ることが, 非常に興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 122 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/arc122/editorial/2042
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<LL> o;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        o.insert(a);
    }
    
    // 2. 正整数列の構築.
    stack<LL> st;
    set<LL> cur;
    rep(i, N){
        // 終了条件.
        if(cur.size() == o.size()) break;
        
        // 今回分更新.
        cur = o;
        
        // 条件を満たす要素は？
        for(auto &ai : cur){
            // 最大公約数.
            vl v;
            for(auto &aj : cur) if(ai != aj) v.pb(__gcd(aj, ai));
            
            // 最小公倍数.
            LL lcm = 1;
            for(auto &q : v){
                LL g = __gcd(lcm, q);
                lcm /= g;
                lcm *= q;
            }
            
            // 判定.
            if(lcm < ai){
                st.push(ai);
                o.erase(ai);
                break;
            }
        }
    }
    
    // 3. 出力.
    if(st.size() == N){
        puts("Yes");
        while(!st.empty()){
             LL ans = st.top();
             st.pop();
             printf("%lld%s", ans, !st.empty() ? " " : "\n");
        }
    }else{
        puts("No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc122/editorial/2042

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<LL> o;

rep(i, N){

LL a;

scanf("%lld", &a);

o.insert(a);

}

// 2. 正整数列の構築.

stack<LL> st;

set<LL> cur;

rep(i, N){

// 終了条件.

if(cur.size() == o.size()) break;

// 今回分更新.

cur = o;

// 条件を満たす要素は？

for(auto &ai : cur){

// 最大公約数.

vl v;

for(auto &aj : cur) if(ai != aj) v.pb(__gcd(aj, ai));

// 最小公倍数.

LL lcm = 1;

for(auto &q : v){

LL g = __gcd(lcm, q);

lcm /= g;

lcm *= q;

}

// 判定.

if(lcm < ai){

st.push(ai);

o.erase(ai);

break;

}

// 3. 出力.

if(st.size() == N){

puts("Yes");

while(!st.empty()){

LL ans = st.top();

st.pop();

printf("%lld%s", ans, !st.empty() ? " " : "\n");

}

}else{

puts("No");

}

return 0;

}

[入力例]
3
3 4 6

[出力例]
Yes
3 6 4
※AtCoderテストケースより

[入力例]
3
2 3 6

[出力例]
No
※AtCoderテストケースより

[入力例]
10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

[出力例]
Yes
922513 255595307440611247 156087536381939527 134115264093375553 116282391418772039 81706734998806133 18332844097865861 4638516664311857 3247317977078471 346046618969
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

[入力例]
5
6 8 12 18 28

[出力例]
Yes
6 12 28 18 8

[入力例]
7
8 10 16 22 27 36 50

[出力例]
Yes
10 50 36 27 22 8 16

[入力例]

3 4 6

[出力例]

Yes

3 6 4

※AtCoderテストケースより

[入力例]

2 3 6

[出力例]

※AtCoderテストケースより

[入力例]

922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

[出力例]

Yes

922513 255595307440611247 156087536381939527 134115264093375553 116282391418772039 81706734998806133 18332844097865861 4638516664311857 3247317977078471 346046618969

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

Yes

922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

[入力例]

6 8 12 18 28

[出力例]

Yes

6 12 28 18 8

[入力例]

8 10 16 22 27 36 50

[出力例]

Yes

10 50 36 27 22 8 16

■参照サイト
東京海上日動プログラミングコンテスト2021（AtCoder Regular Contest 122)

C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題E (Increasing LCMs) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題E (Increasing LCMs) を解いてみた.

コメントを残すコメントをキャンセル