AtCoder Beginner Contest 118

C - Monsters Battle Royale

https://atcoder.jp/contests/abc118/tasks/abc118_c

方針

の最大公約数 が答えになりますが、コンテスト中には気付けませんでした。結局全く同じことを遠回しにしただけですが、以下のように考えました：

1. のうち最小のものを とする。
2. について、 で割った余りに置き換える。
3. 以上 1, 2 を なる が 1 つだけになるまで繰り返す。

最後に残った が答えになります。

ソースコード

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

int main(){
    int N;  cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++)  cin >> A[i];

    int m = 0;
    while(true){
        sort(A.begin(), A.end()); 
        m = lower_bound(A.begin(), A.end(), 1) - A.begin(); // 上記の 1. 
        if(m==N-1) break; // m == N-1 のとき、正の A[i] が 1 つだけ。

        for(int i=m+1; i<N; i++) A[i] = A[i]%A[m]; // 上記の 2. 
    }
    cout << A[m] << endl;
}

D - Match Matching

https://atcoder.jp/contests/abc118/tasks/abc118_d

方針

問題文で与えられている、整数 を作るのに必要なマッチ棒の数を とします。

マッチ棒をちょうど 本使って作れる整数の最大値、とします。これは64ビット整数に収まらないことがあるので string 型にしておきます。マッチ棒 本で作れる整数がないときは空文字列 "" にします。求めたいものは です。

まず 各 について を求めることが出来ます。 次に が分かっているときに を求めることを考えます。
(1) の桁数 < の桁数 + 1 のとき
の適切な位置に を挿入したものを とします。挿入の際は を上位桁から見ていき、 文字目が 以下になったときに、 文字目の前に を挿入します。

たとえば 9954332 に 4 を挿入すると、99544332 となり、974421 に 5 を挿入すると、 9754421 となります。

なお、 本のマッチ棒で作る整数は一桁なので、文字列としてみた時に降順に並んでいます。降順な文字列から出発してこの挿入を繰り返すので、 は必ず降順な文字列になっています。

(2) の桁数 = の桁数 + 1 のとき
(1)の方法で得られる整数と を比較し、大きい方を とします。

(3) の桁数 > の桁数 + 1 のとき
このときは を更新する必要はありません。

ソースコード

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

// 一桁の数 i を作るのに必要なマッチ棒の数を nMatch[i] として持っておく
const int nMatch[10] = {0,2,5,5,4,5,6,3,7,6};

string append(string s, string t){
    // s は必ず降順の文字列なので、
    // s[i] <= t となる s[i] の直前に t を挿入する
    int n = s.length();
    for(int i=0; i<n; i++){
        if(s[i] <= t[0]){
            s.insert(i,t);
            break;
        }
        // s の最後の文字の手前にも t を挿入できないときは、
        // s の一番後ろに付け足す。
        if(i==n-1) s += t;
    }
    return s;
}

int main(){
    int N, M;
    vector<int> A;
    cin >> N >> M;
    A = vector<int>(M,0);
    for(int i=0; i<M; i++) cin >> A[i];

    vector<string> dp(N+1,"");
    // 1 桁の数字 A[j] を作る場合に関して dp[i] を求めておく
    for(int i=0; i<M; i++){
        int n = nMatch[A[i]];
        if(n > N) continue;
        if(dp[n] == "" || dp[n] < to_string(A[i])) 
            dp[n] = to_string(A[i]);
    }

    for(int i=1; i<=N; i++){
        if(dp[i]=="") continue;
        for(int j=0; j<M; j++){
            // dp[i] に A[j] を追加すると、マッチ棒は合わせて nxt 本になる
            int nxt = i + nMatch[A[j]];
            if(nxt > N) continue;
            if(dp[nxt].length() < dp[i].length() + 1){  // (1)の場合
                dp[nxt] = append(dp[i], to_string(A[j]));
            }else if(dp[nxt].length() == dp[i].length() + 1){  // (2)の場合
                string tmp = append(dp[i], to_string(A[j]));
                if(dp[nxt] < tmp) dp[nxt] = tmp;
            }
        }
    }
    cout << dp[N] << endl;
}