読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

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

SRM584

7/10 20:00JST〜

250-600-900
こういう時って250の早解き勝負らしいです

青と黄色だけの部屋。チャレンジフェーズゆるゆる。

Easy ("Egalitarianism", 250)

  • union-findで全員が同じ島にいることを確認(いなければ-1)
  • メンバー相互間の距離を全部出すやつあるよね(Warshall-Floydのことか!)
  • WFでさくっと通す自信がなくていつものdijkstraコードをコピペ(ごめんなさいごめんなさい)
  • 1人1人を起点にdijkstraして、一番遠い人までの距離を取る。
  • その最大値にdを掛けたのが答え
  • 194.48 (16'10'')
  • passed system test
投稿コード(長いので一部割愛)
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

class UnionFind {
  ...
};

template <typename T> pair<vector<T>,vector<int> >
dijkstra_core(int algo, vector<vector<T> > arclength, int start_v, int goal_v=-1)
{
  int N = arclength.size();
  ... 
  return make_pair(distance, predecessor);
}

class Egalitarianism {
 public:
  int maxDifference(vector<string> isFriend, int d) {
    int n = sz(isFriend);
    UnionFind uf(n);
    for (int i=0; i<n-1; ++i) {
      for (int j=i+1; j<n; ++j) {
        if (isFriend[i][j] == 'Y') uf.unionSet(i, j);
      }
    }
    int r0 = uf.root(0);
    for (int i=1; i<n; ++i) {
      if (uf.root(i) != r0) return -1;
    }

    vector<vector<int> > arc(n,vector<int>(n, infty));
    for (int i=0; i<n-1; ++i) {
      for (int j=i+1; j<n; ++j) {
        if (isFriend[i][j] == 'Y') {
          arc[i][j] = arc[j][i] = 1;
        }
      }
    }

    int m = 0;
    for (int i=0; i<n; ++i) {
      pair<vector<int>,vector<int> > res = dijkstra_core(1, arc, i);
      tr(it, res.first) {
        m = max(m, *it);
      }
    }
    
    return d * m;
  }
};

後でWarshall-Floydで書きなおしたらシンプルになって、Test Caseが通ったのでsystem testにかけてみたら落ちた。ループの順番に注意。

#include <vector>
#include <string>
using namespace std;

#define rep(var,n)  for(int var=0;var<(n);++var)
#define ev(v1,v2,n) for(int v1=0;v1<(n)-1;++v1)for(int v2=v1+1;v2<(n);++v2)

class Egalitarianism {
 public:
  int maxDifference(vector<string> isFriend, int d) {
    int g[50][50];
    int n = isFriend.size();
    int INFTY = 99999; /// 適当な大きさ

    ev(i,j,n) {
      g[i][j] = g[j][i] = (isFriend[i][j] == 'Y') ? 1 : INFTY;
    }
    rep(i,n) g[i][i] = 0; /// これをしないなら、後の max(g[i][j]) 計算時にi≠j判定をすべき

    // rep(i,n)rep(j,n)rep(k,n) /// BAD
    rep(k,n)rep(i,n)rep(j,n) /// GOOD
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    int m = 0;
    ev(i,j,n) {
      m = max(m, g[i][j]);
    }
    return (m >= INFTY) ? -1 : d*m;
  }
};

Medium ("Excavations", 600)

  • foundに含まれていない種類の建造物が建つサイトを分離(グループZとする)
    • foundに含まれるものをグループAとする
  • グループZの建物を地表からの深さ順にソート
  • グループZのどの建物を発掘対象に含めるか。発掘対象の中で一番浅いものの深さdzと、集合{z}が何通りあるかが必要
    • 同じ深さのものがあるので要注意
  • グループA側で、dz より浅いところに埋まった建造物の中から、foundに含まれる種類のものを満遍なく(各種類少なくとも1つずつ)選び出す組み合わせが何通りか
  • というのを、考えられるdz全通りについて算出し合計したのが答え

というコードが時間内に書けずに断念。終了後に書いてみたコードはグループZ側の組み合わせの数の計算が間違っていて、テストケースは全部通るけれどfailed system test。

明日の自分へのメモ

3種類(k=1,2,3とする)の建物があって、それぞれの軒数が [3, 4, 2] (合計9)のとき、その中全種類少なくとも1軒ずつ含まれるように7件選びたい。
このケースでは、9C7=36から「種類a,bのみの3+4=7軒を選んでcが1軒も選ばれない」ケースを引いた35が答えなのだけれど、
種類kまででn軒選ぶ組み合わせの数をa[k][n]とするなら

long long a[3+1][7+1]; // 初期値は a[0][0] = 1 それ以外は 0

みたいな配列を使ったDPで書ける。(実際は偶奇交互にやればいいので a[2][7+1] で足りる)

選んだ軒数(n) 初期(k=0) (k=1) (k=2) k=3)
0 1 +pre*0
1 0 +pre*3C1 +pre*0
2 0 +pre*3C2 +pre*4C1 + pre*0
3 0 +pre*3C3 +pre*4C2 + pre*2C1
4 0 +pre*4C3 +pre*2C2
5 0 +pre*4C4
6 0 ... ...
7 0 ... ...

preというのは a[k-1][i](i=0〜7)各値について加算していく事の略記。

  ll dp(vector<ll>& pc, int take) {  /// pc[] = {3,4,2}, take=7
    int pc_sz = sz(pc);

    vector< vector<ll> > a(2, vector<ll>(take+1, 0LL) );
    a[0][0] = 1LL;

    rep(i, pc_sz) {
      int i0 = i%2, i1 = (i+1)%2;
      rep(j, take+1) a[i1][j] = 0LL;
      rep(j, take) {
        for (int n=1; n<=pc[i]; ++n) { // k=0の時
          if (j+n <= take) a[i1][j+n] += a[i0][j] * C[pc[i]][n]; /// C[n][k] = nCk な配列を事前準備
        }
      }
    }
    return a[pc_sz%2][take];
  }

種類kの建物を1軒も選ばない、という事は許されないので nC0 ではなく 0 を用いる点に注意。
左から右へ進めて、k=3まで行った時に7軒選ばれる組み合わせの数は a[3][7] に入っているはず。