naoya_t@hatenablog

いわゆるチラシノウラであります

TCO18 Algorithm Round 1A

4/22(日) 1:00am JST

全完
部屋(Room31)6位
全体では176位
レーティングは1467→1497(黄色復帰まであと+3)

Easy (250) RedDragonInn

式を書くだけ
5'34'' (240.82pt) →AC

class RedDragonInn {
    public:
    int maxGold(int N, int X) {
        return 2*(N*X + N-1) + 1;
    }
};

Medium (500) Resistance

パターンpCs通りをnext_permutationで舐めて、全ミッション辻褄があうやつだけをカウントして件数/Sで割って
27'34'' (298.87pt) →AC

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

#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define ALL(c)  (c).begin(),(c).end()

class Resistance {
    public:
    vector<double> spyProbability(int P, int S, vector<string> missions) {
        int M = missions.size();
        vector<int> b(P, 0);
        rep(i,S) b[P-1-i] = 1;
        vector<double> s(P, 0);

        bool possible = false;
        do {
            bool valid = true;
            rep(i, M){
                if (missions[i][0]=='S') continue;
                bool one = false;
                rep(j,P){
                    if (missions[i][1+j] == '1' && b[j] == 1) {
                        one = true; break;
                    }
                }
                if (!one) { valid = false; }
            }
            if (valid) {
                possible = true;
                rep(j,P) s[j] += b[j];
            }
        } while (next_permutation(ALL(b)));
        if (!possible) {
            return vector<double>();
        }
        double z = 0;
        rep(j,P) z += s[j];
        z /= S;
        rep(j, P) s[j] /= z;
        return s;
    }
};

Hard (1000) Deadfish

DP
負の領域については考えなくてよい
・インクリメント
・自乗した先が更新される場合、そこから更新できるだけ遡って
・降順ソートした先が更新される場合、そこから更新できるだけ遡って
200000で間に合うから多分いけるっしょ
19'13'' (722.37pt) →AC

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

typedef long long ll;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define ALL(c)  (c).begin(),(c).end()

int numsort(int x) {
    if (x < 10) return x;
    vector<int> k;
    while (x) {
        k.push_back(x%10); x /= 10;
    }
    sort(ALL(k));
    int y = 0;
    for(int i=0,c=k.size(),b=1; i<c; ++i,b*=10) {
        y += b*k[i];
    }
    return y;
}

class Deadfish {
    public:
    int shortestCode(int N) {
        int XX = 999999;

        vector<int> dp(XX, 0); rep(i, XX) dp[i] = i;

        dp[0] = 0;
        for (int i=0; i<=N; ++i) {
            int here = dp[i];
            dp[i+1] = min(dp[i+1], here + 1); // i

            if (i < 46340) {
                int i2 = i*i;
                if (i2 < XX && dp[i2] > here+1) {
                    for (int j=i2,c=here+1; j>i; --j,++c) {
                        if (dp[j] > c) dp[j] = c;
                        else break;
                    }
                }
            }
            int is = numsort(i);
            if (is > i && is < XX && dp[is] > here+1) {
                for (int j=is,c=here+1; j>i; --j,++c) {
                    if (dp[j] > c) dp[j] = c;
                    else break;
                }
            }
        }
        return dp[N];
    }
};

1262.06点で部屋7位

Challenge Phase

他の人のコードをいくつか見たけどChallengeはしてない

System Test

黄色の人がHardを1つ落としてて6位に上がった
全体では176位