SRM 練習日記 - 不定期プログラミング覚え書き

なんかビックリするほど一発でAC取れなくて凹む。
SRMサーチからグラフ系統のMedium問題の正答率が高めなものを解いてみる

SRM 453.5 Medium PlanarGraphShop

問題

単純な平面グラフについて、頂点数^3+枝数^2をその平面グラフのポイントとする。
引数にNを与えるので、最小何この平面グラフのポイント総和でNが表現できるかを示せ

考えたこと

えー、平面グラフの枝数と頂点数の関係とか忘れましたし。
wikipediaを見ると、３以上の頂点数ならば任意の平面グラフの枝数<=3*頂点数-6
なんて書いてある。
でもこの声質って枝数=3*頂点数-6の平面グラフが必ず存在することを言えないと使えないよな……
……
…………
普通に紙に書いたら存在することは確定的に明らかだった。
そうすると、平面グラフから生成可能な得点の集合が取れるので、
それらをどれだけ少なく用いてNを作れるか？という、DPでありがちな問題に帰着する。

適当に書いた。出した。TLE(´・ω・｀)
上述の集合をbool型配列とかにしてるのが悪かったらしい。
3乗とか2乗とかで得点を計算しているためか、上記集合サイズは集合内最大値よりも十分小さくなる、ということだと思われる。

コード

  int bestCount(int N) {
    int result;
    memset( ok , false, sizeof(ok));
    ok[1]=true;
    ok[8]=true;
    ok[9]=true;
    cout << "test" << endl;
    for( int i = 3; i*i*i <= N; i++ ){
      for( int j = 0 ; j <= 3*i-6 ; j++ ){
        if( i*i*i+j*j <= N) ok[i*i*i+j*j]=true;
      }
    }
    vector<int> oks;
    for( int i = 0 ; i <= N ; i++ ){
      if(ok[i]) oks.push_back(i);
    }
    int size = oks.size();
    int ans[50001];
    fill( ans, ans+50001, INT_MAX/2);
    ans[0] = 0;
      for( int i = 0 ; i <= N ; i++ ){
        for( int j= 0 ; j < size; j++ ){
          if( oks[j]+i > N ) break;
          ans[i+oks[j]]=min( ans[i+oks[j]], ans[i]+1);
        }
      }
    return ans[N];
  }

Member SRM 474 Medium TreeCount

もしかするとどこかで解いたことあるかも知れない…と思いつつ一発ACできなかった(´・ω・｀)

問題

グラフが与えられる。
ここから、以下の部分グラフを構成したい

部分グラフは木である
部分グラフにおいて、0番目の頂点から任意の頂点vまでの距離は、元のグラフの最短路に等しい

このような部分グラフは何通り作れるか？

考えたこと

まずはワーシャルフロイドで最短路求めて、
0からじゅんじゅんに距離の小さい頂点を付け加えるときに、何通りのパターンがあるか調べれば良いんでないの？
そう思ってグリグリ書いたけれど、以外にたくさんミスった。
ワーシャルフロイドでは同じ頂点の間は重み0の枝で貼るべきとか忘れてた。

コード

  int count(vector <string> graph) {
    int dist[51][51];
    int size = graph.size();
    memset( dist, 0 ,sizeof(dist));
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < size ;j++ ){
        dist[i][j] = graph[i][j]-'0';
        if( dist[i][j] == 0 ) dist[i][j]=INT_MAX/2;
        if( i == j ) dist[i][j] = 0;
      }
    }
    for( int k = 0 ; k < size; k++ ){
      for( int i = 0 ; i < size; i++ ){
        for( int j = 0 ; j < size; j++ ){
          dist[i][j] = min( dist[i][j], dist[i][k]+dist[k][j] );
        }
      }
    }
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < size; j++ ) cout << dist[i][j] << ", ";
      cout << endl;
    }
    vector< pair<int,int> > vec;
    for( int i = 0 ; i < size; i++ ) vec.push_back( make_pair( dist[0][i], i ));
    sort( vec.begin(), vec.end() );
    long long result = 1;
    for( int i = 1 ; i < size; i++ ){
      int nextdist = vec[i].first;
      int nextind = vec[i].second;
      int cnt=0;
      for( int j = 0 ; j < i; j++ ){
        if( graph[vec[j].second][nextind]!='0' && vec[j].first+graph[vec[j].second][nextind]-'0' == nextdist ){
          cout << vec[j].second <<"-" << vec[i].second << "available" << endl;
          cnt++;
        }
      }
      cout << nextind <<" "<< cnt << endl;
      result*= cnt;
      result %= 1000000007;
    }
    return result;
  }

SRM 436 Medium DoNotTurn

問題

縦横長さNのボードで、始点が0,0、終点がN-1,N-1の迷路のようなものを考える考える。
X0,Y0,A,B,C,D,P,Mを用いて定義される数列X[0]...X[M-1],Y[0]...Y[M-1]を用いて、X[i]%N,Y[i]%Nが始点でも終点でもない時、そこには壁があると考える

X[0]=X0
X[i]=(X[i-1]*A+B)%P
Y[0]=Y0
Y[i]=(Y[i-1]*C+D)%P

このボードにおいて、始点から終点まで最大何回の方向転換（90度右回転or左回転)でたどり着くことができるか。

考えたこと

ボードのいち＋向きによるDPのようなダイクストラのような物とは考えついたけれど、
そこからの実装でつまづきまくった。
あと、出力処理があったり少しでもサイズ多めにとったりするとMLEとかTLEとかでお祭り騒ぎになってヤバイ。

コード

bool maze[501][501];
bool ok[501][501][4];
int size;
typedef struct data{
  int x,y,dir,dist;
}data;
class Less{
public:
 bool operator()( const data& a, const data& b ){
    return a.dist < b.dist;
 }
};
priority_queue< data, vector<data>, Less > q;
//(中略)
  int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M) {
    size = N;
    memset( maze, false, sizeof(maze));
    long long X = X0%P;
    long long Y = Y0%P;
    for( int i = 0 ; i < M ; i++ ){
      int tmpx=X%N;
      int tmpy=Y%N;
      if( tmpx!= 0 || tmpy!= 0 ){
        if( tmpx != size-1 || tmpy != size-1 ){
          maze[tmpx][tmpy] = true;
        }
      }
      X = X*A+B;
      Y = Y*C+D;
      X %= P;
      Y %= P;
    }
    /*
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < size; j++ ){
        cout << (maze[i][j]?'#':'.');
      }
      cout << endl;
    }*/
    memset( ok, false, sizeof(ok));
    data right; data under;
    right.x=0;
    right.y=0;
    right.dir=0;
    right.dist=0;
    under.x=0;
    under.y=0;
    under.dir=2;
    under.dist=0;
    q.push(right);
    q.push(under);
    int dxs[] = {1,-1,0,0};
    int dys[] = {0,0,1,-1};
    while( !q.empty()){
      data cur = q.top();
      q.pop();
      int dist = cur.dist;
      //cout << cur.x << ", " << cur.y << ", " << cur.dir<< endl;
      if( cur.x < 0 || cur.y < 0 || cur.x >= size || cur.y >= size ) continue;
      if( maze[cur.x][cur.y] ) continue;
      if( cur.x == size-1 && cur.y == size-1 ) return -dist;
        if( ok[cur.x][cur.y][cur.dir]  ) continue;
        ok[cur.x][cur.y][cur.dir] = true;
        for( int i = 0; i < 4; i++ ){
          int offset = 0;
          if( cur.dir != i ) offset = 1;
          data next;
          next.x = cur.x+dxs[i];
          next.y = cur.y+dys[i];
          next.dir = i;
          next.dist = dist-offset;
          if( next.x < 0 || next.y < 0 || next.x >= size || next.y >= size ) continue;
          if( !ok[next.x][next.y][next.dir] )
          if( !maze[next.x][next.y] )
          q.push( next );                            
        }
    }
    return -1;
  }

SRM 480 Medium NetworkSecurity

問題

acyclicな有向グラフをclientCableとserverCableで表す。
clientCable[i][j]=='Y'はi番目のクライアントからj番目のクライアントに片方向通信路がはられているという事。
serverCable[i][j]=='Y'はi番目のクライアントからj番目のサーバに通信路がはられているということである。
任意のクライアントcと、cから到達可能なサーバsのペアにおいて、少なくともひとつの経路はデータゲートを横断するように、データゲートを配置したい。
最低でも必要なデータゲート数を答えよ。

考えたこと

クライアントをトポロジカルソートの逆バージョン？みたいにならべ、他のクライアントに通信路を持たないクライアントで、サーバとつながっている物はそこにゲートを置き、
それにより上位のクライアントとサーバの接続関係を更新、みたいな方針でいいんじゃ…と思ったけれど、
トポロジカルソートみたいにする所、状態更新など、色々なところでバグらせた。
マジ実装力足らない…

コード

  void rec( int cur, vector<int> rems ){
    ok[cur]=true;
    for( int i = 0 ; i < n_client; i++ ){
      if( !ok[i]&&client[cur][i] ){
        for( int k = 0 ; k < (int)rems.size(); k++ ){
          server[i][rems[k]]=false;
        }
        rec( i, rems );
      }
    }
    return;
  }
  int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
    int result;
    memset( client, false, sizeof(client) );
    memset( server, false, sizeof(client) );
    memset( n_parent, 0 , sizeof(n_parent) );
    n_client = clientCable.size();
    n_server = serverCable[0].size();
    for( int i  = 0 ; i < n_client ; i++ ) for( int j = 0 ; j < n_client; j++ ){
      if( clientCable[i][j] == 'Y' ){
        client[j][i] = true;
        n_parent[i]++;
      }
    }
    for( int i = 0 ; i < n_client; i++ )for( int j = 0 ; j <n_server; j++ ) server[i][j] = (serverCable[i][j]=='Y');
    bool checked[51];
    memset( checked, false, sizeof(checked) );
    result = 0;
    for( int loop = 0 ; loop< n_client; loop++ ){
      int ind = 0;
      while( checked[ind]==true || n_parent[ind]!=0 ){
        cout << ind << ": " << checked[ind] << " , " <<n_parent[ind] << endl;
        ind++;
      }
      checked[ind]=true;
      vector<int> rem;
      for( int i = 0 ; i < n_server; i++ ){
        if( server[ind][i] ){
          result++;
          rem.push_back( i );
        }
      }
      cout << ind ;
      for( int i = 0 ; i < (int) rem.size() ; i++ ) cout << " " << rem[i];
      cout << endl;
      memset( ok, false, sizeof(ok));
      rec( ind, rem );

      for( int i = 0 ; i < n_client; i++ )
        if( client[ind][i] )n_parent[i]--;
    }
    return result;
  }

計算量はクライアント数をNとした時、
トポロジカルソートで１頂点ずつ見ていくところ・上位ノードのたどる所・接続関係を更新する所それぞれで最大Nかかるから、
$O(N^3)$ になるんかな。
上位ノードをたどるときに重複を許すとTLEします。