SRM612
日記書くの追いつかないんだけど！ コンテスト終了後１０分くらいでサクッと書けるようにしないと回らないんだろうか。
SRM611は0完でレートを100落としましたがSRM612で2完して再び100上げたとかそんな感じの250-450-950(?)回。
611早く復習したい。
| Level | ProblemName | Status | Point |
| Easy | EmoticonsDiv1 | Passed System Test | 132.66 |
| Medium | SpecialCells | Passed System Test | 251.72 |
| Hard | ???? | Unopened | 0.0 |
Easy EmotionsDiv1
問題
めっちゃ意訳である。
1個の「ｲｲﾈ｣から始めて以下の操作を繰り返すことでN個の「ｲｲﾈ｣からなる文を作りたい
- これまでの文章をコピーする
- これまでの文章をペーストする
- 「ｲｲﾈ」を1つ削除する
最小操作数を答えよ
考えたこと
削除って必要なんですか？ なんとなく削除なしでコピーとペーストだけ考えれば良さそうだが…
→ 15は 1->2->4->8->16->15のほうが1->2->3->...->14->15より操作数少ないし、削除も必要そう
(後で分かったが、本当はここは1->2->4->6->5->10->16と作るのが最速)
→じゃあどうするか…コピーしてる長さと現在の値を用意するdpとか？
→dpで端から順に埋めてこうとしたけど削除があるせいで上手くいかんぞこれ…
→半分苦肉の策ながら(手数,(現在の｢ｲｲﾈ｣数,クリップボードの「ｲｲﾈ」数))というタプルをつかって幅優先したら最大ケース通るっぽい
→submit
→あ、現在の「ｲｲﾈ｣数の上限を入力長で区切ってしまっていたけど大丈夫だろうか…
→最大ケースとかぶち込んで検証してみたけど大丈夫じゃないですかね、よって放置
コード
int printSmiles(int smiles){ priority_queue< pair<int,pair<int,int> > > q; q.push( make_pair(-1,make_pair(1, 1)) ); bool checked[smiles+1][smiles+1]; memset( checked, false, sizeof(checked)); while( !q.empty() ){ pair<int,pair<int,int> > p=q.top(); q.pop(); int dist = -p.first; int num = p.second.first; int cpy = p.second.second; if( checked[num][cpy] == true ) continue; checked[num][cpy] = true; cout << num << " " << cpy <<" "<<dist << endl; if( num == smiles ) return dist; if( num != cpy && checked[num][num] == false ){ q.push( make_pair( -dist-1, make_pair( num,num) ) ); } if( num >= 2 && checked[num-1][cpy] == false ){ q.push( make_pair( -dist-1, make_pair( num-1,cpy) ) ); } if( num+cpy <= smiles && checked[num+cpy][cpy] == false ){ q.push( make_pair( -dist-1, make_pair( num+cpy,cpy) ) ); } } return 0; }
復習
幅優先の計算量見積がすごい下手くそだなあと思いましたorz
状態数が1000*1000で操作数が3なので探索範囲って3*1000*1000しか無いので間に合いますね。
Medium SpecialCells
ハイパー意訳その２
(x[i],y[i])で表される頂点列を与えられる。
今、数列yをシャッフルした数列y'を用いて、頂点の集合{(x[i],y[i])}と頂点の集合{(x[i],y'[i])}が何個の頂点を共有するかを考える。
最低何個は同じ頂点を共有するか答えよ
考えたこと
極力元の頂点集合と点を共有しないように数列yをシャッフルすることを考える。
最初の頂点列が(x,a),(x,b),(x,c)を持ってるとした時、
可能ならばシャッフル後のy座標はa,b,c以外から利用したいが、他に選択肢がなかったりしたらa,b,cを利用せざるを得ない。
これがすべてのxについて成り立つ。
そんな関係をゴニョゴニョ考えていたら、以下の様な最小費用流を考えれば良いことにたどり着いた。
ケース３：
x={1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}
y={1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3}
の例
黒い線がコスト0，赤い線がコスト1，sから出る辺は容量2，tに入る辺は容量6、その他の辺は容量1
もう少し一般化するならば、
sからx座標値aに入る辺はxに含まれるaの数を容量とするコスト0の辺、
y座標値bからtに入る辺はyに含まれるbの数を容量とするコスト0の辺、
x[i]からy[j]に入る辺は容量1でx[i],y[i]が元の頂点列に含まれる時にコスト1,含まれない時にコスト0とする
このようなグラフに置いて流量x.size()を流すときの最小流を考えると、求める解となる
各辺の条件を以下のように書くともう少し実感沸くだろうか。
- 各x座標値aについて、x[]に含まれるaの数だけyを割り当てなきゃいけない
- 各y座標値bについて、y[]に含まれるbの数だけxに割り当てられなくてはならない
- x座標値aに割り当てるy座標値bは(a,b)が元の頂点列に含まれないことが望ましい。どうしても元の頂点列に含まれるものを選ばなければならないのなら、ペナルティ1を与える。
解きたいこと：ペナルティの数(=元の頂点列と重複する点数）を最小化すること
コード
struct edge{ int to; int cap; int cost; int rev;}; int mincost( vector<edge> graph[], int size, int start, int end, int F ){ bool changed = true; int prev[size]; int prevind[size]; int dist[size]; int cost = 0; while( F > 0 ){ memset( prev, -1, sizeof(prev)); memset( prevind, -1, sizeof(prev)); for( int i = 0 ; i < size; i++ ) dist[i] = INT_MAX/2; dist[start]=0; changed = true; while( changed ){ changed = false; for( int i = 0 ; i < size; i++ ){ for( int j = 0 ; j < (int)graph[i].size(); j++ ){ //cout << i <<"-"<< graph[i][j].to <<","; edge e = graph[i][j]; if( e.cap > 0 && dist[i]+e.cost < dist[e.to] ){ changed = true; dist[e.to] = dist[i]+e.cost; prev[e.to] = i; prevind[e.to] = j; } } } } //for( int i = 0 ; i < size; i++ ) cout << dist[i]<< " , " ; //cout << endl; if( dist[end] == INT_MAX/2){ return -1; } // calc flaw int f = INT_MAX; int p = end; while( p != start ){ f = min(f, graph[prev[p]][prevind[p]].cap ); p = prev[p]; } //cout << endl; f =min( F, f ); // exec flaw p = end; while( p != start){ graph[prev[p]][prevind[p]].cap -= f; int ind = graph[prev[p]][prevind[p]].rev; graph[p][ind].cap += f; cost += f*graph[prev[p]][prevind[p]].cost; p = prev[p]; } F-=f; } return cost; } void addedge( vector<edge> graph[],int from, int to, int cap, int cost ){ //枝を追加する。逆向きには容量0でコストが真逆な枝を追加しておく。 graph[from].push_back( (edge){to,cap,cost,graph[to].size()} ); graph[to].push_back( (edge){from,0,-cost, graph[from].size()-1} ); return; } class SpecialCells { public: int guess(vector <int> x, vector <int> y){ vector<int> Xind = x; vector<int> Yind = y; sort(Xind.begin(),Xind.end()); sort(Yind.begin(),Yind.end()); Xind.erase( unique(Xind.begin(),Xind.end()),Xind.end()); Yind.erase( unique(Yind.begin(),Yind.end()),Yind.end()); int xcnt[100001]; int ycnt[100001]; int xind[100001]; int yind[100001]; memset( xcnt,0,sizeof(xcnt)); memset( ycnt,0,sizeof(ycnt)); memset( xind,-1,sizeof(xind)); memset( yind,-1,sizeof(yind)); int xsize = Xind.size(); int ysize = Yind.size(); for( int i = 0 ; i < (int)x.size(); i++ ){ xcnt[x[i]]++; ycnt[y[i]]++; } for( int i = 0 ; i < xsize; i++ ){ xind[Xind[i]]=i; } for( int i = 0 ; i < ysize; i++ ){ yind[Yind[i]]=i; } int G[xsize][ysize]; memset( G, 0, sizeof(G)); for( int i = 0 ; i < (int)x.size(); i++ ){ G[xind[x[i]]][yind[y[i]]]=1; } for( int i = 0 ; i < xsize; i++ ){ cout <<Xind[i] <<"- "<< xind[Xind[i]] <<" "; } cout << endl; for( int i = 0 ; i < ysize; i++ ){ cout <<Yind[i] <<"- "<< yind[Yind[i]] <<" "; } cout << endl; for( int i = 0 ; i < xsize; i++ ){ for( int j = 0 ; j < ysize; j++ ){ cout << G[i][j]<<" "; } cout <<endl; } cout << endl; // total node 0, 1...xsize, xsize+1...xsize+ysize, xsize+ysize+1 vector<edge> graph[xsize+ysize+2]; for( int i = 1; i <= xsize; i++ ){ addedge(graph,0,i,xcnt[Xind[i-1]],0 ); } for( int i = 1; i<= ysize; i++ ){ addedge(graph,xsize+i,xsize+ysize+1, ycnt[Yind[i-1]],0); } for( int i = 1; i <= xsize; i++ ){ for( int j = 1 ; j <= ysize; j++ ){ if( G[i-1][j-1] == 0 ){ addedge( graph,i,xsize+j,1,0); } else{ addedge( graph,i,xsize+j,1,1); } } } int ans = mincost( graph, xsize+ysize+2 , 0, xsize+ysize+1, x.size() ); return ans; }
