naoya_t@hatenablog

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

Single Round Match 745 - Fun and Unrated

12/28(金) 11:00-12:??

Div I/II混合で75分で6問、という謎のSRM(unrated)が生えてたので起きてたら出ようと思っていて、起きてたので(レジぎりぎり間に合ったので)出ることになった。

intervalとそのchainに関する6つの問題。(200-300-500-600-800-1000)


最近SRMに出ていないので(AtCoder埋めばかりやっているので)問題の配点と難易度の相関関係がぱっと分からない。でもまあ1問目から順に。

解いては投げ解いては投げで5問提出して、6問目これマトリョーシカに落とすには多すぎるなあと思って疑似乱数まで実装したあたりで終了。

Challengeは撃墜されるのを指を咥えながら見守る派(3つ落とされた)

結果2完66位(有効参加者147人中)これratedだったらレート削ってたな
Div I/II合わせて147人とか淋しくなったなSRM

なんか振り返る気力も起こらず終了後寝落ち…
(とりあえず提出コードを貼っておいて未来の自分に託す)

Chains0 (200)

使ってないコードが多いから30%減点するぞと脅されてコード削った(こういうの久しぶりだ)

class Chains0 {
    public:
    vector <int> getProperSubset(int x, int y) {
        return vector<int> {x, x+1};
    }
};

→AC

Chains1 (300)

class Chains1 {
    public:
    long long countMaximalChains(int n) {
        long long ans = 1LL;
        return ans << (long long)(n-1);
    }
};

→AC

Chains2 (500)

class Chains2 {
    public:
    int validate(vector <int> x, vector <int> y) {
        int n = x.size();
        int order = 0;
        for (int i=0; i<n-1; ++i) {
            int xi=x[i],yi=y[i],di=yi-xi, xj=x[i+1],yj=y[i+1],dj=yj-xj;
            if ((xj <= xi && yi <= yj) && (dj > di)) {
                order = yj;
                continue;
            } else if (xi==yi) {
                continue;
            }
            return -(1+i+1);
        }
        return order;
    }
};

→Challenge Succeeded

Chains3 (600)

class Chains3 {
    public:
    string validate(vector<int> c) {
        int L = c.size();
        int mn=c[0], mx=c[0], det=-1;
        for (int i=1; i<L; ++i) {
            if (c[i] < mn) {
                if (det == -1 && mn-c[i] > 1) {
                    det = 1+i;
                }
                mn = c[i];
        } else if (mx < c[i]) {
                if (det == -1 && c[i]-mx > 1) {
                    det = 1+i;
                }
                mx = c[i];
            } else {
                return "invalid " + to_string(1+i);
            }
        }
        if (det == -1) {
            return "maximal " + to_string(1+mx);
        } else {
            return "valid " + to_string(det);
        }
    }
};

→Challenge Succeeded
はい(最後(0,mn)の間が埋まっていない場合の判定がおかしいでしょ)

Chains4 (800)

typedef long long ll;

const ll M=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { assert(y%M!=0); return MUL(x, POW(y, M-2)); }

class Chains4 {
    public:
    int count(int n) {
        vector<ll> dp(n+1);
        dp[0] = 1;
        dp[1] = 3;
        for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] // orig
                  + dp[i-1]-1 // <i+>, dot抜き
                  + POW(2, i+1)-2;
            dp[i] %= M;
        }
        return (int)dp[n];
    }
};

→Challenge Succeeded

Chains5 (1000)

(開いた)