cafelier@SRM

SRM441

あとで | 15:15 |

ちょっとRogueの潜りすぎで忙しくて参加できなかったのであとで解いてみる

250

• 『各点のout_degreeが1の有向グラフが与えられる。できるだけ少ないつなぎ替えで1つのループにしてね』
• 連結成分の個数数えるだけ。
  • 1つならもうループになってる。
  • k>1個なら、それぞれの連結成分はループになってるので、各々1個選んで行き先を隣の連結成分になるようにぐるっとずらせば1つのわっかになるはず
• できた

class PerfectPermutation { public:
  int reorder(vector <int> P) 
  {
    vector<bool> used(P.size(), false);

    int nLoop = 0;
    for(int i=0; i<P.size(); ++i)
      if( !used[i] ) {
        ++nLoop;

        for(int p=i; !used[p]; p=P[p])
          used[p] = true;
      }
    return nLoop==1 ? 0 : nLoop;
  }
};

500

• 『250と似たような感じだけど無向グラフ。out_degreeも任意。あとつなぎ替えはswapのみ。何回のswapで全体を連結にできるか。』
  • 1回のswapで2つの連結成分をくっつけて1つにできるので、解があるとすれば連結成分の個数-1。
  • 連結成分 {a-b} と連結成分 {c-d} をswapして a-c と b-d みたいなことをしてもくっつかない
  • 要は、swapする辺のどちらかは「取り除いても連結性が損なわれない辺」にしないとくっつかない
  • そういう辺の数を数えて 連結成分の個数-1 以上ならOK。未満なら解なしなので-1を返す。
• できた。submit。run test。死亡。
  • ???
  • うおー、孤立点は絶対くっつけないので孤立点があったら無条件で-1しないとダメだ。
  • resubmit。通った。
  • これ、本番ぜったいひっかかってたなあ。あぶねー。wataさんのように15連続acceptとはいかないけれど、"500をsubmitしたときはaccept"連続記録は保ちたいところなのでセーフセーフ。

• 通ったんだけど、「取り除いても連結性が損なわれない辺」を数えるのに、「一個一個取り除いてみてunion-findで連結性を数えて変化してないことを確認」してました。
• naoya_tさんのコード見たら、そうか、n要素の連結成分からは残りn-1本になるまで辺を除けるに決まってるんだから引き算一発で求まるじゃん。うわー僕のひどすぎる。やりなおし。

class StrangeCountry { public:
  int transform(vector <string> g) 
  {
    int nConn=g.size(), nEdge=0;

    vector<int> uf(g.size(), -1); // union-find
    for(int x=0; x<g.size(); ++x)
    {
      if( g[x].find('Y')==-1 )
        return -1; // orphan

      for(int y=x+1; y<g.size(); ++y)
        if( g[x][y]=='Y' ) {
          ++nEdge;
          int rx=x; while( uf[rx]>=0 ) rx=uf[rx];
          int ry=y; while( uf[ry]>=0 ) ry=uf[ry];
          if( rx != ry ) uf[rx]=ry, --nConn;
        }
    }

    int redundant = nEdge - (g.size() - nConn);
    return redundant>=nConn-1 ? nConn-1 : -1;
  }
};

1000

• まだ見てない