naoya_t@hatenablog

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

TCO17 Algorithm Round 2A

f:id:n4_t:20170521180949p:plain
oo- +0/-0 300.49pt 152nd 1574 -> 1655(+81)
Easyは再提出(75pt)。Mediumが通ってて(225.49pt) ratingを持ち直した…

Easy (250) FoxAndCake2

TopCoder Statistics - Problem Statement
(c:3, s:3) とか (c:3, s:6) のケーキを1つと、(c:偶数, s:偶数) のケーキを作ればいい、みたいに解けるってのは割とすぐに思いついたんだけど
(以下WA解)

// includeとか色々略

int gcd(int m, int n){
    while(m) swap(m, n%=m);
    return n;
}

class FoxAndCake2 {
 public:
    string isPossible(int c, int s) {
        if (c>=5 && s>=5) {
            if ((c==5 && s==6) || (c==6 && s==5)) goto impossible;
            else goto possible;
        }
        else if (gcd(c,s) > 1) goto possible;
        else goto impossible;
    possible:
        return "Possible";
    impossible:
        return "Impossible";
    }
};

これではまずかったことに(Medium提出後に)見直して気づいた。
(7以上の奇数, 6) みたいなやつで落ちる。

時間あるし改めて整理。テストケース書き足し。
1. (c:偶数, s:偶数) の場合、ないし gcd(c,s) != 1 の場合 → possible
2. (c:奇数, s:cとは互いに素な奇数) の場合 → (3, 3), (2以上の偶数, 2以上の偶数) が作れれば、即ち (c≧5, s≧5) ならpossible
3. (c:奇数, s:偶数) の場合 → (3,6), (2以上の偶数, 2以上の偶数) が作れれば、即ち (c≧5, s≧8) なら possible
4. (c:偶数, s:奇数) の場合 → (6,3), (2以上の偶数, 2以上の偶数) が作れれば、即ち (c≧5, s≧8) なら possible

int gcd(int m, int n){
    while(m) swap(m, n%=m);
    return n;
}

class FoxAndCake2 {
 public:
    string isPossible(int c, int s) {
        if (c == 1 || s == 1) goto impossible;

        if (gcd(c,s) > 1) goto possible;

        if (c%2 == 0 && s%2 == 0) goto possible;
        else if (c%2 == 1 && s%2 == 1) {
            if (c >= 5 && s >= 5) goto possible;
        }

        if (c%2==0) swap(c,s);
        // o e
        if (c >= 5 && s >= 8) goto possible;
        else goto impossible;
    possible:
        return "Possible";
    impossible:
        return "Impossible";
    }
};

Medium (500) DistanceZeroAndOne

TopCoder Statistics - Problem Statement
ノード0, ノード1からの距離が与えられていて、それと矛盾しないグラフが描けるかという話。

隣接行列は対称行列で、かつ対角成分は0であるべき、という辺りで弾けるものは弾く。
ノード0からの距離情報をもとに、繋いでもいいエッジを全て拾う。具体的には、ノード0からの距離が等しい、あるいは距離の差が1である2ノードを拾う。当然これを全部繋げる必要はないが、繋がっていても矛盾は起こさない。こうして拾ったエッジを繋いで出来たグラフをG_0とする。
ノード1からの(同様に)G_1とする。
求めたいグラフGにおいて繋いでいいのは、G_0 と G_1 のいずれにおいても繋がっているエッジのみ。
G_0, G_1 の両方で使われているエッジを拾ってGを構成し、こうして出来たGが元の dist0, dist1 を満たすかを調べる。
(ワーシャルフロイド法を回して最初の2行をdist0,dist1と比べるだけ)

// 略
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<string> vs;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;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())

class DistanceZeroAndOne {
    int makerg(vvi& rg, vector<int>& dist) {
        int maxdist = *max_element(all(dist));
        int M = maxdist+1;
        rg.assign(M, vector<int>());
        rep(i, dist.size()) {
            int d = dist[i];
            rg[d].push_back(i);
        }
        rep(i, M) {
            if (rg[i].size() == 0) return -1;
        }
        return M;
    }
    void count(vvi& cnt, vvi& rg) {
        int M = rg.size();
        rep(d, M){
            int u = rg[d].size();
            repC2(i,j,u){
                assert(i!=j);
                int a = rg[d][i], b = rg[d][j];
                assert(a!=b);
                ++cnt[a][b]; ++cnt[b][a];
            }
        }
        rep(d, M-1) {
            int u = rg[d].size(), v = rg[d+1].size();
            rep(i,u) rep(j,v) {
                int a = rg[d][i], b = rg[d+1][j];
                assert(a!=b);
                ++cnt[a][b]; ++cnt[b][a];
            }
        }
    }
 public:
    vector<string> construct(vector<int> dist0, vector<int> dist1) {
        vector<string> ans;

        vvi rg0, rg1;
        int N = dist0.size();
        vvi com(N, vi(N, 0));
        vvc two(N, vc(N, 'N'));
        vvi dd(N, vi(N, 99999)); rep(i,N) dd[i][i] = 0;

        if (dist0[0] != 0 || dist1[1] != 0 || dist0[1] != dist1[0]) {
            goto inconsistent;
        }

        if (makerg(rg0, dist0) == -1) goto inconsistent;
        if (makerg(rg1, dist1) == -1) goto inconsistent;

        count(com, rg0);
        count(com, rg1);

        rep(i,N) rep(j,N) {
            int c = com[i][j];
            if (i==j) assert(c == 0);
            if (i!=j) assert(c == com[j][i]);
            if (c==2) { two[i][j] = 'Y'; dd[i][j] = 1; }
        }

        rep(i,N) rep(j,N) rep(k,N) {
            dd[j][k] = min(dd[j][k], dd[j][i] + dd[i][k]);
        }

        rep(i, N) {
            if (dd[0][i] != dist0[i]) goto inconsistent;
            if (dd[1][i] != dist1[i]) goto inconsistent;
        }

        rep(i, N) ans.push_back(string(all(two[i])));
    inconsistent:
        return ans;
    }
};

ここまで通して残り23分。

Hard (1000) FourLamps

TopCoder Statistics - Problem Statement
開いたけど読まずにEasyに戻った

Challenge phase

部屋で6人ぐらいEasyを落とされてた。(というか落とせなかった…)
誰も人のMediumをいじってない

System test

Easyは(折角再提出したんだし)通ってもらわないと困るんだけど
Mediumが通ってて嬉しい。

  • Easy: 75.00pts (再提出)
  • Medium: 225.49pts (45'13'')
  • Hard: 0.00pts
  • Total: 300.49pts

System test前は部屋7位だったのがみんなMediumをぼろぼろ落とされてて結果部屋2位。全体では152位。ratingも1574から1655まで持ち直した。(+81)