【解題まとめ】NWERC 2019(Codeforces Gym 102500)

58247 ワード

私が解決した:E(1 WA)、F、I、A.
見てない:H.
傍観する:C、G、D.
見たけどできなかった:K、B、J.
E Expeditious Cubing
簡単な問題.
C Canvas Line
難しくない貪欲に見えますが、略.
F Firetrucks Are Red
題意:n n n個の点があり、各点に数セットがある.2つの点の数セットが空でない交差がある場合、2つの点はその数を重みとして、1つのエッジを結ぶことができます.生成ツリーを求めます.
列挙数は、同じ数の点をつなぎ合わせるだけでよく、連通性を維持するために使用し、コレクションを調べます.

#include 
using namespace std;
unordered_map<int, int> mp;
int tot, lst[200005];
int to[200005], nxt[200005], at[200005] = {0}, cnt = 0;
int ans[200005][3];
int fa[200005], siz[200005];
int Find(int x){
    return (x == fa[x] ? x: (fa[x] = Find(fa[x])));
}
int Union(int u, int v){
    u = Find(u), v = Find(v);
    if (u == v) return 0;
    if (siz[u] > siz[v]) fa[v] = u, siz[u] += siz[v];
    else fa[u] = v, siz[v] += siz[u];
    return 1;
}
int main(){
    int n;
    scanf("%d", &n);
    tot = 0;
    for (int i = 1; i <= n; ++i){
        int t, num;
        scanf("%d", &t);
        for (int j = 1; j <= t; ++j){
            scanf("%d", &num);
            if (!mp.count(num)) {
                mp[num] = ++tot;
                lst[tot] = num;
            }
            int id = mp[num];
            to[++cnt] = i, nxt[cnt] = at[id], at[id] = cnt;
        }
    }
    for (int i = 1; i <= n; ++i)
        fa[i] = i, siz[i] = 1;
    
    int res = 0;
    for (int i = 1; i <= tot; ++i){
        if (!at[i]) continue;
        int rep = to[at[i]];
        for (int j = at[i]; j; j = nxt[j]){
            if (Union(to[j], rep)){
                ans[++res][0] = to[j], 
                ans[res][1] = rep, 
                ans[res][2] = lst[i];
            }
        }
    }
    if (res < n - 1) {
        printf("impossible
");
    }else {
        for (int i = 1; i <= res; ++i){
            printf("%d %d %d
", ans[i][0], ans[i][1], ans[i][2]);
        }
    }
    return 0;
}

I Inverted Deck
題意:シーケンスを指定し、シーケンスが下がらないように連続サブシーケンスを反転できるかどうかを尋ねる.
まず同じ数を1つに縮めて、シーケンスに隣接する同じ数がないようにします.シーケンスをa a aとし、最初からa i≦a i+1 a_を満たさないi\le a_{i+1}ai≦ai+1のi i iはt t tである.反転の左端はa t a_でなければならないことがわかります.t atは、前でも後でもだめです.
そしてa t a_を見つけますt at後のa a aの最小値をa p a_とするp ap.[t,p][t,p][t,p][t,p]の区間を反転するしかない.成功すれば解があるが,そうでなければ解がない.
時間的複雑度はO(n)O(n)O(n)であった.

#include 
using namespace std;
int n;
int a[1000005], b[1000005], tmp[1000005];
int st[1000005][2];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int nn = 0;
    for (int i = 1, j; i <= n; i = j){
        j = i;
        while (j <= n && a[i] == a[j])
            ++j;
        b[++nn] = a[i];
        st[nn][0] = i, st[nn][1] = j - 1;
    }

    int t = 1;
    while (t < nn && b[t + 1] >= b[t])
        ++t;
    if (t == nn){
        // no need
        printf("1 1
");
        return 0;
    }

    int mini = 2000000000, p = t;
    for (int i = t; i <= nn; ++i){
        if (b[i] <= mini) mini = b[i], p = i;
    }

    // [t, p]
    for (int i = 1; i <= t - 1; ++i)
        tmp[i] = b[i];
    for (int i = p + 1; i <= nn; ++i)
        tmp[i] = b[i];
    for (int i = t, j = p; i <= p; ++i, --j)
        tmp[i] = b[j];

    bool flag = true;
    for (int i = 1; i < nn; ++i){
        if (tmp[i] > tmp[i + 1]){
            flag = false;
            break;
        }
    }

    if (!flag){
        printf("impossible
");
    }else {
        printf("%d %d
", st[t][0], st[p][1]);
    }
    return 0;
}

A Average Rank
标题:n n n人がいて、w w w試合.試合ごとに1点を取る人がいます.試合が終わるたびに順位があり、ある人に対してx xの個人点数が彼より高い場合、彼の順位はx+1 x+1 x+1です.問w w試合終了後、各人の試合は順位、すなわち各試合の順位の和をw w wで割った.
明らかに、私たちの目標はまず一人一人の順位の和を求めることです.
私たちはまずランキングを維持する方法を考えます.ランキングを維持するために、各スコアに対してtagを維持することができます.1人のランキングは、その点数のtagです.一人が1点加算した場合、その元の点数をt t tとすると、tag[t]に1を加算するだけでよい.
このような定義の順位は、元の定義よりも常に1少ないことがわかりますが、これは重要ではありません.
このように、更新順位はO(1)O(1)O(1)の時間さえあれば、私たちは試合が終わるたびに、一人一人に自分の点数のtagを加えて答えを更新することができます.全時間複雑度はO(nw)O(nw)O(nw)であった.
しかし、このような時間は複雑すぎます.各スコアに対してtot_tagをさらに維持することを考慮し、試合開始からある時点までのtagの累積を示す.では、私たちはすべての試合が終わった後、一人一人に自分の点数のtot_tagを加えれば答えを得ることができます.
問題は、tot_tagをどのように維持するかです.私たちはlazy tagのやり方に倣って、tot_tagを使う時だけ更新します.では、各スコアに最後の更新時間を記録する必要があります.例えば、i i i番目のフィールドにスコアj j jを用いると、前i−1 i−1のフィールドまでのtot_tagを先に精算することができる.
第i iフィールドに精算しないのは、第iフィールド情報が更新されていない可能性があるからである.
人の点数が1点上がる影響をなくすために、上げる前の点数をt t tとすると、tot_tag[t]を加えてtot_tag[t+1]を減算します.
最後の時間複雑度は線形である.

#include 
using namespace std;
typedef long long ll;
int n, w;
int lst[1000005] = {0}, tag[1000005] = {0};
ll ans[300005] = {0}, tot_tag[1000005] = {0};
int pos[300005]; 
int st[1000005], top;
bool vis[1000005] = {0};
void update(int cur, int curtime){
    if (!vis[cur]){
        vis[cur] = true, st[++top] = cur;
        tot_tag[cur] += 1ll * (curtime - 1 - lst[cur]) * tag[cur];
        lst[cur] = curtime - 1;
    }
}
int main(){
    scanf("%d%d", &n, &w);

    for (int i = 1; i <= w; ++i){
        int k, id;
        scanf("%d", &k);
        top = 0;
        for (int j = 1; j <= k; ++j){
            scanf("%d", &id);
            int cur = pos[id];
            
            update(cur, i);
            update(cur + 1, i);
            ans[id] += tot_tag[cur];
            ans[id] -= tot_tag[cur + 1];
            
            ++tag[cur];
            ++pos[id];
        }

        for (int j = 1; j <= top; ++j){
            vis[st[j]] = false;
        }
    }

    for (int i = 1; i <= n; ++i){
        acctag[pos[i]] += 1ll * (w - lst[pos[i]]) * tag[pos[i]];
        lst[pos[i]] = w;

        ans[i] += acctag[pos[i]];
        double ave = (double)ans[i] / (double)w;
        ave += 1.0;
        // rank: base-0
        printf("%.20lf
", ave);
    }

    return 0;
}

G Gnoll Hypothesis
标题:モンスタープールにn n n匹のモンスターがいて、それぞれのモンスターの生成確率はp i p_i pi.ランダムにk k k匹を選択するたびに、生成しないモンスターの本来の生成確率は次の生成可能なモンスターに後ろに移ります(最後のモンスターが生成しない場合、確率は最初のモンスターが生成可能なものに移ります).各モンスターの生成確率の期待を求めます.
それぞれの位置のモンスターに対して、所望の線形特性を利用して、その前のモンスターの所望の寄与を計算すればよい.モンスターi i iに対して,位置i−d−d−i−dのモンスターの寄与はp i−d⋅(n−d−1 k−1)(n k)p_である.{i-d}\cdot\frac{\binom{n - d - 1}{k-1}}{\binom{n}{k}} pi−d⋅(kn)(k−1n−d−1)
素朴な作りはO(n 2)O(n^2)O(n 2)です.貢献そのものが一つのボリュームなのでFFTでもできます.
H Height Profile
題意:与えられたn+1 n+1 n+1個の点(i,h i)、0≦i≦n(i,h_i)、0le ile n(i,hi)、0≦i≦n、i i i番号点とi+1 i+1 i+1号点の間に直線セグメントで接続する.k k k回の問い合わせでは、1つの傾きg gが与えられるたびに、線分上の2つの点が連線傾きを少なくともg g満たすかどうかを尋ね、ある場合は、実行可能な2つの点間の水平距離の最大値を求める.
k k kは小さいので、毎回質問に答えることを考えます.
回答のたびに、少なくとも1つの点の横座標が整数であることがわかります.そうしないと、線分を上下に移動し、傾きを変えずに水平距離を増やすことができます.そこで、左端点または右端点を列挙し、別の端点で答えを更新したい.
列挙右端点を例にとると、隣接点間線分が連続しているため、現在横座標j j jに列挙されている場合、i対h i−i g h_i−ighi−igを並べ替え、i i i i iを小さい値から大きい値まで列挙して解く.このようにして解決した時間的複雑度はO(kn logn)O(knlogn)O(knlogn)であった.

#include 
using namespace std;
int n, k, h[100005], hh[100005];
pair<int, int> p[100005];
char g[1005];
void init(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; ++i)
        scanf("%d", &h[i]);
}
void solve(){
    while (k--){
        scanf("%s", g);
        int l = strlen(g);
        g[l - 2] = g[l - 1], g[--l] = '\0';
        int gg = atoi(g);
        
        for (int i = 0; i <= n; ++i){
            p[i].first = hh[i] = h[i] - i * gg, 
            p[i].second = i;
        }
        sort(p, p + n + 1);

        //        
        int mini = p[0].second;
        double ans = -1;
        for (int i = 1; i <= n; ++i){
        	//   ，          
            int cur = p[i].second;
            if (mini > cur) {
                mini = cur;
                continue;
            }
            double offset = 0;
            // mini      
            if (mini > 0){
                offset = max(offset, (double)(hh[cur] - hh[mini]) / 
                    fabs(hh[mini] - hh[mini - 1]));
            }
            //          
            if (p[i].second < n){
                offset = max(offset, (double)(hh[cur] - hh[mini]) / 
                    fabs(hh[cur + 1] - hh[cur]));
            }
            ans = max(ans, cur - mini + min(1.0, offset));
        }

        if (ans < 0) printf("-1
");
        else printf("%.20lf
", ans);
    }
}
int main(){
    init();
    solve();
    return 0;
}

D Disposable Switches
補充待ち..
J Jackdaws and Crows
補充待ち..
K Kitesurfing
補充待ち..
B Balanced Cut
補充待ち..

SQLにおける条件・ループ文の適用整理

[Vue.js]computed(算出プロパティ) の基本