cafelier@SRM

TCO09 Round2

SRM | 03:03 |

TCO09 Round2 の成績・ソース (要ログイン) : AC/-/AC : 900はやっぱり簡単だ

600開く

• 『50×50個の格子点がR,G,Bの3色に塗り分けられている。ここから、3頂点の色が違う三角形を取り出す。1個だけ(色が違う条件を保ったまま)頂点を変えて面積を大きくできる三角形は何個あるか』

• とりあえず、Rの個数×Gの個数×Bの個数 - デカくできない三角形の個数、かな
  • 問題はデカくできない三角形の個数。
  • RGを固定してBを動かす場合を考えてみよう。
  • 面積が大きくならないと言うことは、RGに平行な線引いてって一番遠いところにのってるのが今のBということで…
  • ううむ。RG固定を全通り試す時点で50^4かかるわけでこれは死ねる

• ううむ

• うむむ

• 3色違う三角形を頂点として、RGBの頂点１個切り替えで移動できる関係を辺とするグラフを考える
• 面積大きい方が下という順序を入れると束っぽいのができて、
• こう、トポロジカル最小なのの個数
• …だめだ何も問題が変わってない

• あきらめた

250開く

• なんか結構みなさん時間かかってる
• 『紙をN×Nに区切って真ん中K×Kを黒くする。白いマスに再帰的にこの操作をs回適用。指定領域[r1,r2]×[c1,c2]の色を全部出せ』
  • N**s がintには収まる程度のサイズ。指定領域は50×50まで

• 各マスごとに再帰で白か黒かやるだけ…
  • s==0 なら白
  • s>=0 なら、N^{s-1} マスごとに盤面を区切って（N^{s-1}で割って）N*Nの基本パターンと見る
    • 見て黒の部分だったら黒
    • 白の部分だったら再帰的にそのゾーンを探索。(N^{s-1}でmod)

• というコードを書こうとしてさんざん苦労した。これはひどい

900開く

• 『左側N頂点右側M頂点の2部グラフが与えられる。それぞれの頂点vに"容量"c[v]が指定されているので、辺集合をうまく選んでそれぞれの頂点にちょうどc[v]本ずつ辺が出てるようにせよ。複数個解がある場合は辞書順で最初のものを出せ』
  • みたいな雰囲気の。

• ええと要するに
  • src---c[v] foreach v-->左--1-->右--c[u] foreach u-->dst
• なグラフの最大フローを求めればよい。
  • Σc[v]=Σc[u]に足りなかったら不可能という答えを返す

• 問題は「辞書順最小」
  • 普通にmaxflow書いたら辞書順最小になるんじゃないかなー？
  • 書いた
  • どう見てもなりません本当にありがとうございました。

• ええと
  • １個目の辺を使わない最大流があれば１個目は使わないこと確定
  • なければ１個目は使うこと確定
  • …確定させたあとで…
  • ２個目の辺を使わない最大流があれば２個目は使わないこと確定
  • なければ２個目は使うこと確定
  • …
• の繰り返しで順番に使う辺決めていくというのでどうだろう。
  • 辞書順最小を求める場合の典型パターンらしいので

• 最大50×50で2500個の辺があって、毎回maxflow流すと…
• 50^5 くらいにならない？だいじょぶ？だんだん使う辺減ってくから平気かな
• 書いた
  • 50×50のケースいくつか試したけれど手元で300ms前後。
  • 行けるんじゃね？出しちゃえ

感想

• 600は難しかったみたいだからいいとして、250はもう少しスピーディに書けてよい問題だった…
• 撃墜フェーズみんなものすごい勢いで撃墜してるんだけど全然ついていけない…
• そして最近ここに書くほどちゃんと物を考えずに解いている気がする全然書くことがない…

TCO09 Round2 600

あとで | 18:03 |

他の方の解法を参考に。

typedef complex<int> CMP;

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }

int ccw(const CMP& a, CMP b, CMP c) {
  b -= a; c -= a;
  if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
  if( outer_prod(b,c) < 0 ) return -1; // clockwise
  if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line
  if( norm(b) < norm(c) )   return -2; // a--b--c on line
  return 0;
}

bool byX( const CMP& a, const CMP& b ) {
  if( a.real() != b.real() )
    return a.real() < b.real();
  return a.imag() < b.imag();
}

vector<CMP> convex_hull( vector<CMP> p )
{
  //#define IS_RIGHT <0   // skip on-line verts
  #define IS_RIGHT ==-1 // take all

  sort(p.begin(), p.end(), &byX);

  vector<CMP> ans;
  for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
    while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
      ans.pop_back();
  if( ans.size() == p.size() )
    return ans;
  for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
    while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
      ans.pop_back();
  ans.pop_back();
  return ans;
}

int area(const CMP& a, const CMP& b, const CMP& c)
{
  return (int) abs( outer_prod(b-a,c-a) );
}

class ExtendableTriangles {
public:
  int getCount(vector <string> grid) 
  {
    vector<CMP> r, g, b;
    for(int y=0; y<grid.size(); ++y)
      for(int x=0; x<grid[0].size(); ++x)
        (grid[y][x]=='R' ? r : grid[y][x]=='G' ? g : b).push_back( CMP(y,x) );

    int cnt = r.size() * g.size() * b.size();

    r = convex_hull(r);
    g = convex_hull(g);
    b = convex_hull(b);

    bool (*ext)[200][200] = (bool(*)[200][200])calloc(200*200*200, 1);
    for(int i=0; i<r.size(); ++i)
      for(int j=0; j<g.size(); ++j)
      {
        int ma = -1;
        for(int k=0; k<b.size(); ++k)
          ma = max(ma, area(r[i], g[j], b[k]));
        for(int k=0; k<b.size(); ++k)
          if( area(r[i], g[j], b[k]) < ma )
            ext[i][j][k] = true;
      }
    for(int j=0; j<g.size(); ++j)
      for(int k=0; k<b.size(); ++k)
      {
        int ma = -1;
        for(int i=0; i<r.size(); ++i)
          ma = max(ma, area(r[i], g[j], b[k]));
        for(int i=0; i<r.size(); ++i)
          if( area(r[i], g[j], b[k]) < ma )
            ext[i][j][k] = true;
      }
    for(int k=0; k<b.size(); ++k)
      for(int i=0; i<r.size(); ++i)
      {
        int ma = -1;
        for(int j=0; j<g.size(); ++j)
          ma = max(ma, area(r[i], g[j], b[k]));
        for(int j=0; j<g.size(); ++j)
          if( area(r[i], g[j], b[k]) < ma )
            ext[i][j][k] = true;
      }
    for(int i=0; i<r.size(); ++i)
      for(int j=0; j<g.size(); ++j)
        for(int k=0; k<b.size(); ++k)
          if( !ext[i][j][k] )
            --cnt;
    free(ext);
    return cnt;
  }
};

凸包かーなるほど。area計算の辺りがけっこうTLEギリギリだった。