naoya_t@hatenablog

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

SRM716

出た

今回はRoom 1だった。赤い人がいる部屋は好きだ。
> ox- 150.72pts 111/228位 (部屋10位) 1639→1616 (-23)
レーティングが順調に下がっている

Easy (250) ConstructLCS

ab,bc,caを大きい順に並べ替えて(ab', bc', ca' とする)、
ab' が AとBの共通部分。AとBとの共通部分を1111... として、その長さをab'とする。
Cは0だけから成る文字列にすれば、AとC、BとCそれぞれの共通部分は000...で、その長さはそれぞれ ac', bc' とする。
あとは元の順番に並び替えるだけ
→AC

// AC解
// (いろいろ略)
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
typedef pair<int,int> ii;

class ConstructLCS {
    public:
    string construct(int ab, int bc, int ca) {
        vector<ii> p(3);
        p[0]=ii(ab,1|2);
        p[1]=ii(bc,2|4);
        p[2]=ii(ca,4|1);
        sort(all(p)); reverse(all(p));

        vector<char> s0,s1,s2;
        s0.insert(s0.end(), p[1].first, '0');
        s0.insert(s0.end(), p[0].first, '1');

        s1.insert(s1.end(), p[0].first, '1');
        s1.insert(s1.end(), p[2].first, '0');

        s2.insert(s2.end(), max(p[1].first,p[2].first), '0');

        vector<string> ans(8);
        ans[p[0].second & p[1].second] = string(all(s0));
        ans[p[0].second & p[2].second] = string(all(s1));
        ans[p[1].second & p[2].second] = string(all(s2));
        stringstream ss;
        ss << ans[1] << " " << ans[2] << " " << ans[4];
        return ss.str();
    }
};

最初共通substringの長さで解いてて
Cを10000..1 にして、A,Bの0部分の長さを-1したやつね。

Medium (450) JumpDistancesOnTree

方針:
・とりあえずWF(ぉぃ)で距離出し
・距離がDに含まれている辺だけ残してあとは捨てる
・距離dのパスの両端をi,jとして、LCSを取って、どちらかがどちらかの子孫なら子孫の方を、そうでなければ両方を、距離dのときの行き先候補として
・rootから、Dに含まれる距離dごとに、行き先候補の少なくとも1つが到達可能か調べた
→challenge succeeded

LCS取ったときに、どちらかがどちらかの子孫って見たかったんだけど共通祖先がrootかそれ以外かで切ってた。
そこ直して(i<jなら、共通祖先がiかどうかで判定すればいい)、計算自体は合うようになったけれどn=1000ぐらいでTLE出る。|q|の3重ループ(しかも2回)は無理だろ…

で、実際のところ、WFをdijkstraに置き換えただけでは2秒を切れなかった。

ACを出すためにやったこと

・WFはdijkstraに置き換える(あと、2回目はrootからの距離だけ求めればいいので簡略化)
・LCSの計算が結構時間かかってる。→都度計算しない。欲しい情報は「aはbの祖先か」だけなのでLCSでなくていい。単純にp[]を遡って(二次元配列に)true/falseを保持しておけばいい。

以下に提出したWA解と、practice roomでACを取れた解を貼る。

// WA解
// (いろいろ略)
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

const int INF = 999999;

vector<vector<int>> children;

int findlca(int root, int p, int q) {
    if (root == -1) return -1;
    if (root==p || root==q) return root;
    int C = children[root].size();
    vector<int> lca(C,-1);
    int cnt = 0;
    rep(i,C) {
        int li = findlca(children[root][i], p, q);
        lca[i] = li;
        if (li != -1) cnt++;
    }
    if (cnt==2) return root;
    rep(i,C){
        if (lca[i]!=-1) return children[root][i];
    }
    return -1;
}

class JumpDistancesOnTree {
    public:
    string isPossible(vector<int> p, vector<int> S) {
        int n=p.size()+1;
        vector<vector<int>> d(n, vector<int>(n, INF));
        rep(i,n)d[i][i]=0;
        children.resize(n);
        rep(i,n-1) {
            // i+1 -> p[i]
            d[i+1][p[i]] = d[p[i]][i+1] = 1;
            children[p[i]].push_back(i+1);
        }
        rep(i,n)rep(j,n)rep(k,n){
            d[i][k] = min(d[i][k], d[i][j] + d[j][k]);
        }
        set<int> sset(all(S));
        map<int,set<int>> dest;
        repC2(i,j,n){
            // i<j jが下
            if (found(sset, d[i][j])) {
                int lca=findlca(0,i,j);
                if (lca==0) { /// ← if (lca != i) とすべきところ
                    dest[ d[i][j] ].insert(i);
                    dest[ d[i][j] ].insert(j);
                } else {
                    dest[ d[i][j] ].insert(j);
                }
            } else {
                d[i][j]=d[j][i]=INF;
            }
        }

        rep(i,n)rep(j,n)rep(k,n){
            d[i][k] = min(d[i][k], d[i][j] + d[j][k]);
        }
        for (auto dist : sset) {
            if (dist == 0) continue;
            bool ok = false;
            for (auto de : dest[dist]) {
                if (de == 0) continue;
                if (d[0][de] < INF) { ok = true; break; }
            }
            if (!ok) goto impossible;
        }
        return "Possible";
    impossible:
        return "Impossible";
    }
};

以下AC解

// いろいろ略
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

const int INF = 999999;
// void make_adjacent(int nV, vector<pair<ii,int>>& arcs, vector<vector<pair<int,int>>>& adj);
// void dij1(int nV, vector<vector<pair<int,int>>>& adjacent, vector<int>& d, int start); // dijkstra
// void dij(int nV, vector<vector<pair<int,int>>>& adjacent, vector<vector<int>>& d); // dij1をn回回して任意の2ノード間の距離のテーブルを作るやつ

class JumpDistancesOnTree {
    public:
    string isPossible(vector<int> p, vector<int> S) {
        int n=p.size()+1;
        p.insert(p.begin(), -1);

        vector<pair<ii,int>> arcs;
        rep1(i,n-1) {
            arcs.push_back(make_pair(ii(i, p[i]), 1));
        }

        vector<vector<bool>> is_ancestor(n, vector<bool>(n, false));
        rep1(i, n-1){
            for (int j=p[i]; ; ) {
                is_ancestor[i][j] = true;
                if (j == 0) break;
                j = p[j];
            }
        }

        vector<vector<pair<int,int>>> adj;
        make_adjacent(n, arcs, adj);
        vector<vector<int>> d;
        dij(n, adj, d);

        vector<bool> sset_(2001, false);
        for (int dist : S) sset_[dist] = true;
        set<int> sset(ALL(S));

        vector<pair<ii,int>> arcs2;
        arcs2.reserve(arcs.size());
        vector<bitset<2001>> dest_chk(n);

        repC2(i,j,n){
            int dist = d[i][j];

            if (sset_[dist]) {
                if (!is_ancestor[j][i]) {
                    dest_chk[i].set(dist);
                    dest_chk[j].set(dist);
                } else {
                    dest_chk[j].set(dist);
                }
                arcs2.push_back(make_pair(ii(i,j), d[i][j]));
            }
        }

        vector<vector<pair<int,int>>> adj2;
        make_adjacent(n, arcs2, adj2);
        vector<int> d0;
        dij1(n, adj2, d0, 0);

        for (int dist : sset) {
            if (dist == 0) continue;
            bool ok = false;
            rep(de, n) {
                if (!dest_chk[de].test(dist)) continue;
                if (d0[de] < INF) { ok = true; break; }
            }
            if (!ok) goto impossible;
        }

        return "Possible";
    impossible:
        return "Impossible";
    }
};

Hard (900)

開いてない

Challenge Phase

上位の人たちに450のコードまじまじと見られてる
これは撃墜ケースを考えてる時のやつだ

Challenge Succeeded...

System Test

Easyが通って150.72点確保
レーティングは少し落ちてた(1639→1616)