Codeforces Round #227

そういえばCodeforces227と228も参加してました。
てか、前回参加(#184)と前々回参加(#153)で日記さぼってたらCodeforcesで日記書くの1年9ヶ月ぶり位になってるんごｗｗ

Problem A George and Sleep

起きた時間と就寝時間を"hh:mm"形式で与えるので就寝時間を答えてください

考えたこと

やるだけ

コード

int main(){
  int sH,sM;
  int tH,tM;
  char c;
  cin >>sH >> c >> sM;
  cin >>tH >> c >> tM;
  int dH = sH-tH;
  int dM = sM-tM;
  if( dM < 0 ){
    dH--;
    dM+=60;
  }
  if( dH < 0 ) dH += 24;
  printf( "%02d:%02d\n", dH,dM);
  return 0;
}

Problem B George and Round

作りたいプロコンの難易度表a1,a2,...anと、すでに用意してある問題難易度b1,b2,...bmがある。(昇順ソート済)
すでにある問題は適宜調節することで難易度を下げることは可能であるが、
それでも足らない問題は再度作成しないといけない。
作成しなければいけない問題数は最小いくらか。

考えたこと

greedyに割り振ればいい

コード

int main(){
  int n,m;
  cin >> n >> m; 
  int a[3001];
  int b[3001];
  for( int i = 0 ; i < n ; i++ ){
    cin >> a[i];
  }
  for( int j = 0 ; j < m ; j++ ){
    cin >> b[j];
  }
  int ind = 0;
  int ans = n;
  for( int i = 0 ; i < n ; i++ ){
    while( b[ind]<a[i] && ind < m ){
      ind++;
    }
    if( ind < m ){
      ans--;
      ind++;
    }
  }
  cout << ans << endl;
}

Problem C George and Number

ある数字の集合b1,b2,...bnからは、以下の操作を繰り返して一つの数字を作成できる
（操作）bi>=bjなペア(bi,bj)を取り出し、二つの数字を連結させた値(bi,bjの順。100,50なら10050ができる。50100はありえない)を新たに集合に加える
最終的な数字を当てるのでそれを実現する最大の集合の個数を答えよ

考えたこと

右から順に数をなめていって、切り離せるものは切り離すスタイル。
今見てる数字が「0」出ない時は、
切り離した数字列が自分より長い限り基本切り離し可能。
逆に短ければ切り離し不可能。
同じ長さの時だけ頑張って切り離し可否を判定しないといけない。

• > 一回submit後落ちるも、同じ長さの時の処理を一部抜かしていたことに気づいて提出したら通った。

コード

int main(){
  string num;
  cin >> num;
  int size = num.size();
  int length = 0;
  int cnt = 0;
  for( int i = size-1; i >= 1 ; i-- ){
    length ++ ;
    string first = num.substr(0,i);
    string second = num.substr(i,length);
    if( second[0] =='0') continue;
    if( first.size() < second.size() ) break;
    else if( first.size() > second.size() ){
      cnt++;
      length = 0;
    }
    else{
      bool ok = true;
      for( int i = 0 ; i < (int)first.size(); i++){
        if( first[i] < second[i] ){
          ok = false;
          break;
        }
        if( first[i] > second[i] ){
          break;
        }
      }
      if( ok ){
          cnt ++;
          length = 0;
      }
    }
  }
  cout << cnt+1 << endl;
}

Problem D George and Interesting Graph

ある有向グラフが「interesting」であるとは

• あるノードuで、任意のノードvに対し枝(u,v)と(v,u)があるものが存在。これをセンターノードという。(枝(u,u)もあるものとする)
• センターノード以外のノードは出次数も入次数も2である

という条件を満たすことである。
与えられたグラフをinterestingにするために枝の追加・削除を最低何回行う必要があるか

考えたこと (途中からミスリーディング)

各ノードをセンターノードにする場合で必要な枝数をチェックする、と考える。
残るノードはセンターノードへの行き来を除き出次数・入次数1にしなければならないので、
センターノードとそれ関連の枝を除き、必要な枝というのは、ループになる枝のみである。
と言うことは、
センターノード以外のノード集合Vに対して、

V	個のノードをそれぞれ左側と右側に持つような二部グラフを考える。（左側が入る側、右側が出る側)

各枝の容量を１とし、
左から右へは「すでに張ってある枝ならコスト０，それ以外はコスト１」
右から左へは「すでに張ってある枝ならコスト１，それ以外はコスト０」
とすれば、左ノードに全て接続してるソースノード・右ノード全てから接続されているシンクノードを導入し、
流量|V|の最小費用流を考えれば良い。
→あれっ、計算時間足らない…それは困ります。。。

復習

唯の最大マッチングで良さげという話に気づいて凹んでいます。
と言うか、状況整理のために改めて図を書いてみたら最小費用流じゃwrong answer吐きそうっていう。

↑書いていた図がこちら。
ま、仮に最小費用流の方向性があっていたとしても、このような枝の貼り方だと、
最小費用流の計算量O(F|E|log|V|)とかO(F|V|^2)とかでは時間が足りない。(|E|が500^2、|V|が500、Fも500、これをセンターごとに繰り返すための500…と、どうあがいても500^4位必要)
最大流の計算量はO(F|E|)だけれど、この場合の枝集合は完全グラフにしなくて良いため、問題文の枝の上限(1000)に収まる。

コード

#define GRAPH_SIZE 1003
struct edge{ int to, cap, rev; };
vector<edge> graph[GRAPH_SIZE];
bool used[GRAPH_SIZE];

void clear(){
  for( int i = 0 ; i < GRAPH_SIZE; i++ ){
    graph[i].clear();
  }
}
void addedge( int from, int to, int cap ){
  //枝を追加する。逆向きには容量0の真逆な枝を追加しておく。
  graph[from].push_back( (edge){to,cap,graph[to].size()} );
  graph[to].push_back( (edge){from,0, graph[from].size()-1} );
  return;
}

int dfs( int v, int t, int f ){
  if( v==t ) return f;
  used[v]=true;
  for( int i = 0 ; i < (int)graph[v].size(); i++){
    edge &e = graph[v][i];
    if( !used[e.to] && e.cap > 0 ){
      int d = dfs(e.to, t, min(f,e.cap) );
      if( d > 0 ){
        e.cap -= d;
        graph[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow( int s, int t ){
  int flow = 0;
  while(true){
    memset(used, 0 , sizeof(used) );
    int f = dfs(s,t,INT_MAX/2);
    if( f == 0 ) return flow;
    flow += f;
  }
}

int main(){
  int n,m;
  cin >> n >> m;
  int g[600][600];
  memset( g, -1, sizeof(g));
  for( int i = 0 ; i < m ; i++ ){
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a][b]=1;
  }
  int result = INT_MAX;
  for( int center = n-1 ; center >=0; center-- ){
    //cout << "center:"<< center<<endl;
    int ans = 0;
    int n_center=0;
    for( int ch = 0 ; ch < n; ch++ ){
      if( center == ch ){
        if( g[ch][ch] == -1 ) n_center++;
      }
      else{
        if( g[center][ch]==-1 ){
          n_center++;
        }
        if( g[ch][center]== -1 ){
          n_center++;
        }
      }
    }
    ans = n_center;
    int n_subEdge = 0;
    clear();
    // 0 ,1...n-1, n,...2n-2, 2n-1
    for( int i = 0 ; i < n ; i++ ){
      if( i == center ) continue;
      addedge( 0, 1+i-(i>center),1);
      addedge( n+i-(i>center), 2*n-1,1);
    }
    for( int i = 0 ; i < n; i++ ){
      for( int j = 0 ; j < n ; j++ ){
        if( i == center || j == center ) continue;
        if( g[i][j] == 1 ){
          n_subEdge++;
          addedge( 1+i-(i>center), n+j-(j>center),1);
        }
      }
    }
    int f = max_flow( 0, 2*n-1);
    int n_del = n_subEdge-f;
    int n_add = n-1-f;
    ans+= n_del;
    ans+= n_add;
    result = min( result, ans );

  }
  cout << result << endl;

}