UCF Local Programming Contest 2018


試合リンクC問題の解題構想:
長さnの配列を与え、数値は1-nで、配列の数を一番前または最後の位置に移動し、最後の配列が小さいから大きいまで並べ替えたときの動作の最小回数を求めることができます.
移動を必要としない法則は連続的な上昇サブシーケンスであることを見出したので,最長の連続的な上昇サブシーケンスresを求め,n−resを出力すればよい.
コード:
#include 
#include 

using namespace std;

const int N = 100010;

int n;
int dp[N];

int main()
{
    cin >> n ;
    int res = 0;
    for (int i = 1, x; i <= n; i++){
        scanf("%d",&x);
        dp[x] = dp[x -1] + 1;
        res = max(dp[x],res);
    }

    cout << n - res << endl;

    return 0;
}



D問題の解題構想:
この問題は、最初の公式に基づいて式を出す限り、X*Y=10^zであるため、Xが2,5の倍数の積を得ることができる.
さらにX*W=Nから、2と5因子の組み合わせがいくつあるかを計算すればOKです.
コード:
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

ll ans[100010];

ll mod_exp(ll a,ll b){
    ll res = 1;
    ll exp = a;
    while(b){
        if (b & 1) res = res * exp;
        exp = exp * exp;
        b>>=1;
    }
    return res;
}

int main(){
    ll n;
    scanf("%lld",&n);
    int a = 0, b = 0;
    while(n % 2 == 0 && n != 0){
        a ++;
        n /= 2;
    }
    while(n % 5 == 0 && n != 0){
        b ++;
        n /= 5;
    }
    int m = 0;
    for (int i = 0; i <= a; i ++){
        ll x = mod_exp(2,i);
        for (int j = 0; j <= b; j ++){
            ll y = mod_exp(5,j);
            ans[m++] = x * y;
        }
    }
    sort(ans, ans + m);
    printf("%d
"
, m); for (int i = 0; i < m; i++){ printf("%lld
"
,ans[i]); } return 0; }

H問題の解題構想:
最初は面倒だと思って、循環的だと思っていたが、結局暴力だった.0サイクルから999まででOKと判断し、最小値をとる(0のときは最初は見ていなかった)
コード:
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;

bool a[10];
int b[10000];

int t, m;

bool check(int x){
    if (x == 0 && !a[0]) return false;
    int k = m;
    while(x){
        int l = x % 10;
        if (!a[l]) return false;
        x /= 10;
    }
    return true;
}

int main()
{
    int n;
    memset(a,true, sizeof a);
    scanf("%d",&n);
    for (int i = 0, x; i < n; i++){
        scanf("%d",&x);
        a[x] = false;
    }
    scanf("%d",&m);
    int res = 1000;
    for (int i = 1; i <= 999; i ++){
        if (check(i)){
            res = min(res,abs(m - i));
        }
    }
    printf("%d",res);
    return 0;
}