SRM615
自分のコード落ちるんじゃね？！と思って同様の解き方に対してチャレンジした結果チャレンジ失敗したけどEasyは通ったので良しとする、みたいな回。
チャレンジ力そろそろ磨きたいんですがどうしたらいいんだろうか。
550のMediumはずっとコンテスト中悩んで解けなかったけど他の人の回答読んでちょっと感心した。
950のHardは自分がノーヒントでなんとかとけちゃうレベルなのでHard詐欺な気がする。コンテスト時間中には間に合わないかもだけど。
| Level | ProblemName | Status | Point |
| Easy | AmebaDiv1 | Passed System Test | 132.66 |
| Medium | LongLongTripDiv1 | Opened(Practiced) | 0.0 |
| Hard | AlternativePiles | Unopened(Practiced) | 0.0 |
Easy
問題 AmebaDiv1
アメーバに対して餌X[]を順に与える。
アメーバは自分とピッタリ同じサイズの餌ならばそれを食べて２倍のサイズになるとする。
餌をあげ終えた時に存在し得ないアメーバのサイズを答えよ
考えたこと
Xの要素以外のアメーバは餌をあげてもサイズ変更が無いので餌をあげ終えた時にもサイズをかえない。
よって、Xの要素の中で餌をあげ終えた時に存在できないものを数えれば良い。
あるX[]の要素xに対し、Xを逆順にたどれば初期状態の候補がわかるので、そいつに対してシミュレートをかけた結果がxと異なればカウントアップ、を繰り返す。
コード
int count(vector <int> X){ int size = X.size(); set<int> S; for( int i = 0; i < size; i++ ){ int cur = X[i]; for( int j = size-1 ; j >= 0 ; j-- ){ if( cur%2 == 0 && X[j] == cur/2 ){ cur /= 2; } } for( int j = 0 ; j < size; j++ ){ if( cur==X[j] ) cur+=X[j]; } if( cur != X[i] ){ S.insert(X[i]); } } return S.size();
復習
チャレンジフェーズで他の人のコードを見た結果、X[i]に対して唯一の初期状態に対してシミュレートかけるより任意のX[j]を初期状態としてシミュレートかけたほうが確実だなあ、という気分になる。
例えば X[]={2,8,4} の時に8をつくろうとするならば、自分の解法だと初期状態2の時からシミュレートするが、4を初期状態としても8を作る事ができる。
これの関係で落ちるようなコーナーケースが存在するのではないか…などとちょっと悩んだし、一瞬{2,4,8,2,4}とかが反例になりそうなきがしたけれど、そんなことなかったでござる。
以下少しラフい議論になるけれど、それは背理法によって理解できる。
もしも自分の解法で作成する初期状態からX[i]は作成できないが他の初期状態からX[i]が作成できると仮定すると、
前者の条件を満たすためにはX[i]/4,...,X[i]/2,...X[i]という数列が、
後者の条件を満たすためにはX[i]/2が上の数列よりも手前に存在することになる。つまりX[i]/2,...,X[i]/4,...,X[i]/2,...X[i]
最初のX[i]/2でX[i]を作れたとしてもその後の数列で出てくるX[i]によって終状態は2*X[i]となりX[i]が作成できることに矛盾する。
Medium LongLongTripDiv1
問題
0,...,N-1の頂点を持つ重み付き無向グラフが与えられる。
0からN-1に調度T距離使って移動可能か否かを答えよ。同じ頂点には何度行っても良い。
考えたこと
DPなのだろうか。dp[i]で0〜iまでを用いて移動可能な距離を保存するスタイル？
周期性なども存在するしその辺りをどうやって保存したら良いのかわからないな…
iの小さい値でゴニョゴニョ検証したけれど美味い法則性も見つからず途方に暮れる→タイムアップ
コンテスト終了後
コンテスト上位者の解法をいくらか開く
→謎のDPしてるな…なんでdpした結果がT以下だったらtrueとかなんだ…？
→何人開いても同じような解き方じゃないですかー
→仕方ないので頑張って読んだら以外にちゃんと理解できた (ｲﾏｺｺ)
(0,a)の枝がある時、0とaを行ったり来たりすることでdist(0,a)*2の距離は簡単に稼げてしまうので、dist(0,a)*2の最小値Mを用いて、
Mの剰余系で考えると物事を簡単に考える事ができる。
dist[n][m]を「頂点nにk*M+mの距離で達する事のできる最小値」とすると、
このテーブルはダイクストラチックな方法で埋めることが可能である。
この時、dp[n][T%M]がT以下になるのであれば、残りは0とどこかの頂点を行き来するだけで距離調整できるので、距離Tで到達可能と判断することができる。
コード
class LongLongTripDiv1 { public: string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T){ pair<int,int> graph[N][N]; int n_edge[N]; memset( n_edge,0,sizeof(n_edge)); int Asize = A.size(); for( int i = 0 ; i < Asize;i++){ graph[A[i]][n_edge[A[i]]++]=make_pair(B[i],D[i]); graph[B[i]][n_edge[B[i]]++]=make_pair(A[i],D[i]); } int modulo=INT_MAX/2; for( int i = 0 ; i < n_edge[0]; i++ ){ modulo = min(modulo,graph[0][i].second*2); } if( modulo == INT_MAX/2 ) return "Impossible"; long long dist[N][modulo]; for( int i = 0 ; i < N ; i++ ) for( int j = 0 ; j < modulo; j++ ) dist[i][j] = LLONG_MAX; priority_queue< pair<long long, pair<int,int> > > que; que.push( make_pair(0,make_pair(0,0))); while( !que.empty() ){ pair<long long, pair<int,int> > p = que.top(); que.pop(); long long d = -p.first; int point = p.second.first; int mod = p.second.second; if( dist[point][mod] != LLONG_MAX ) continue; dist[point][mod] = d; for( int i = 0 ; i < n_edge[point] ; i++ ){ int nextpoint = graph[point][i].first; int nextd = d+graph[point][i].second; int nextmod = nextd; nextmod %= modulo; if( dist[nextpoint][nextmod] == LLONG_MAX ){ que.push(make_pair( -nextd, make_pair(nextpoint,nextmod)) ); } } } if( dist[N-1][T%modulo] <= T ) return "Possible"; return "Impossible"; }
Hard AlternativePiles
問題
白、赤、緑、青のカード列と整数Mが与えられる。
今、白いカードを赤or緑or青に塗ることで、以下の条件を満たすようにしたい
考えたこと
ごちゃごちゃ書いてるけどよーするに左から順に見た時に
・赤が常に緑よりも枚数が多い
・赤がM+1枚以上緑より大きくならない
・赤の枚数はMの倍数
という条件を満たすようにすれば良い。
dp[i][j][k] = i枚カードまで見た時、赤が緑よりj枚多く、赤の枚数%Mがkであるパターン数
とすると、
i枚目のカードが赤の時：dp[i][j][k] = dp[i-1][j-1][(k-1)%M]
i枚目のカードが青の時：dp[i][j][k] = dp[i-1][j][k]
i枚目のカードが緑の時：dp[i][j][k] = dp[i-1][j+1][k]
i枚目のカードが白の時：赤・青・緑の各パターンを加算
といった更新式で計算かのう。
iの範囲がカード列の長さ(5000)、j,kの範囲がMの値(50)なので、50*50*5000=1.25*10^7の計算量でなんとか間に合う。
実際はdp[5000][50][50]を用意にしたら最大ケースでセグフォったのでdp[2][50][50]する定番テクニックで回避した。
コード
int count(string C, int M){ int size = C.size(); long long dp[2][M+1][M]; int mod = 1000000007; memset( dp, 0 , sizeof(dp)); dp[0][0][0]=1; for( int i = 1; i <= size; i++ ){ int nxt = i%2; int cur = 1-nxt; int c = C[i-1]; for( int j = 0 ; j <= M; j++ ){ for( int k = 0 ; k < M ; k ++ ){ dp[nxt][j][k] = 0; if(c=='R'||c=='W'){ if( j-1 >= 0 ){ int prevk = (M+k-1)%M; dp[nxt][j][k] += dp[cur][j-1][prevk]; dp[nxt][j][k] %= mod; } } if(c=='G'||c=='W'){ if( j+1 <= M ){ int prevk = k; dp[nxt][j][k] += dp[cur][j+1][prevk]; dp[nxt][j][k] %= mod; } } if(c=='B'||c=='W'){ dp[nxt][j][k] += dp[cur][j][k]; dp[nxt][j][k] %= mod; } } } } /* for( int i=0; i <=size; i++ ){ for( int j = 0 ; j < M+1 ; j++ ){ for( int k=0 ; k<M; k++ ){ cout << dp[i][j][k] <<" "; } cout << ", "; } cout << endl; }*/ return dp[size%2][0][0]; }
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; }
Codeforces Round #229 (Div 2)
10分延長してくれたお陰で色々バグが取れて４問解けた回。当時Div 1だったのでレート変動無くて助かったか？
Eがなかなか勉強になりそうなので、最近のCF参加記そっちのけでここのログ書きます。
Problem A Inna and Alarm Clock
格子状に目覚まし時計が配置されてる。Innaは縦に並んだor横に並んだ目覚まし時計は一変にスイッチオフにできる
最小なんステップで目覚まし時計はスイッチオフにできるか答えよ。
考える事
やるだけ
コード
int main(){ int n; cin >> n; int x[n]; int y[n]; for( int i = 0 ; i < n ; i++ ){ cin >> x[i] >> y[i]; } sort( x, x+n ); sort( y, y+n ); int sizex = unique( x, x+n )-x; int sizey = unique( y, y+n )-y; // cout << sizex << " " <<sizey << endl; cout << min( sizex, sizey ) << endl; return 0; }
Problem B Inna, Dima and Song
２人の演奏者が居て、i番目の音はどちらも最大a[i]の音量を出すことができる。
２人の音量がピッタリb[i]だった時、聴講者は2つの音量の積だけの幸福度を得る。そうでなければ幸福度が１下がる。
得られる最大の幸福度を答えよ。なお、音量は整数のみ認めるとする。
考えたこと
b[i]/2とb[i]-b[i]/2の音量を可能な限り出し続ければOK
ということでさっくり書いたが、b[i]=1の時を弾かないと幸福度0を得る、と算出されることに気が付かず、終了ギリギリまでドはまりした。
コード
int main(){ int n; cin >> n; long long a[n]; long long b[n]; long long ans =0; for( int i = 0 ; i < n ; i++ ) cin >> a[i]; for( int i = 0 ; i < n ; i++ ) cin >> b[i]; for( int i = 0 ; i < n; i++ ){ if( b[i]==1 || a[i]+a[i] < b[i] ) ans--; else{ long long x = b[i]/2; long long y = b[i]-x; ans += x*y; } } cout << ans << endl; return 0; }
Problem C Inna and Candy Boxes
キャンディが一直線上に並べられている。また、入力としてk,wを与える。
その後、l,rをw回与えるので、それぞれに対し、
[l,r]の区間のうちl+k-1,l+2k-1,...,rにしかキャンディが存在しないようにするための操作（飴を取り払うor飴を入れる）数を答えよ
考えたこと
基本的にk距離離れたところの飴の有無しか気にならないので、
sum[N]にN,N-k,N-2k,...のうちに含まれるキャンディ数を保管しておくことにした。
そうすると、l+k-1,l+2k-1,...,rに含まれるキャンディの数はsum[r]-sum[l-1]で、
l+k-1-s,l+2k-1-s,...r-sに含まれるキャンディの数はsum[r-s]-sum[l-1-s]で(s=1〜k-1)ある。
後者の値はそのまま操作数に直結し、前者の値は本来あるべき1の数に足りない分を補完すればよい。
…まで考えたけど、l=rの時の処理方法があんまりよくわからなくて何度かミスった。
コード
int main(){ int n,k,w; cin >> n >> k >> w; string candies; cin >> candies; int sum[n+1]; memset( sum, 0 , sizeof(sum) ); for( int i = 0 ; i < n ; i++ ){ if( i >= k ){ sum[i+1] += sum[i+1-k]; } sum[i+1] += (candies[i]-'0'); } #ifdef DEBUG for( int i = 0 ; i < n+1 ; i++ ){ cout << sum[i] << ", " ; } cout << endl; #endif for( int i = 0 ; i < w; i++ ){ int l,r; cin >> l >> r; if( l == r ){ cout << 1-(candies[r-1]-'0')<< endl; continue; } int n_one = (r-l+1)/k; int cur_one = (sum[r]-sum[l-1]); #ifdef DEBUG cout << "need:" << n_one <<" cur:" << cur_one << endl; #endif int task_to_add = n_one-cur_one; int task_to_erase = 0; for( int j = 1 ; j < k ; j++ ){ int n_extra_one = sum[r-j]; if( l-1-j >= 0 ) n_extra_one -= sum[l-1-j]; task_to_erase += n_extra_one; #ifdef DEBUG cout << "offset:" << j << "..." << n_extra_one << endl; #endif } cout << task_to_erase + task_to_add << endl; } return 0; }
Problem D Inna and Sweet Matrix
n*mの格子状にkこのキャンディを置くこととする。
キャンディを置く時は毎回左上点(1,1)から1マスずつ縦or横に移動して置くこととし、すでにキャンディが置かれた場所は通ることができない。
この時、移動距離がペナルティとして加算される。
最小のペナルティ値とその時のキャンディの運び方を答えよ。
考えたこと
マンハッタン距離が大きい順にk子並べれば良い、以上。
何故か盤面を常に縦長になるように調整したら経路を出すところでミスったり、経路出力でそもそもケアレスミスをしてたりで2WA食らった。
コード
void printpath( pair<int,int> p ,bool swaped ){ int x = p.first; int y = p.second; if(swaped) swap(x,y); cout << "(1,1)"; for( int i = 2 ; i <= x ; i++ ){ cout <<" ("<<i<<",1)"; } for( int i = 2; i <= y ; i++ ){ cout <<" ("<<x<<","<<i<<")"; } cout << endl; } int main(){ int n,m,k; cin >> n >> m >> k; bool swaped= false; if( n < m ){ swaped= true; swap(n,m); } int cnt[101]; memset( cnt, 0, sizeof(cnt) ); int total = 0; int point = 0; vector<pair<int,int> > list[101]; for( int i = 1 ; i <= n ; i++ ){ for( int j = 1 ; j<=m ; j++ ){ list[i+j-1].push_back( make_pair(i,j)); } } for( int i = 1 ; i <= n+m-1 ; i++ ){ int curnum = list[i].size(); if( total+curnum >= k ){ cnt[i]=k-total; point += cnt[i]*i; break; } cnt[i] = curnum; total += curnum; point += cnt[i]*i; } cout << point<<endl; for( int i = 100; i >= 0 ; i-- ){ for( int j = 0 ; j < cnt[i]; j++ ){ printpath( list[i][j],swaped ); } } return 0; }
Problem E Inna and Large Sweet Matrix
n*mの盤面に対し、クエリをw個実行せよ
クエリは以下のフォーマットで与えられる。
- 1行に5個の整数 x,y,x2,y2,vが与えられた時は、x<=i<=x2, y<=j<=y2が成立するすべてのセルにキャンディをv個置く
- 1行に4個の整数x,y,x2,y2が与えられた時は、x<=i<=x2,y<=j<=y2が成立する全セル(i,j)のキャンディ総和と、(i
考えたこと
あーこれなんとかツリーを使うやつじゃなかったっけ？
そのくらいの漠然としたイメージはあるけどいざ問題として出されるととけんな。。。
復習
kmjpさん(http://kmjp.hatenablog.jp/entry/2014/02/12/1000)の記事を読んでそうだBITだーとは思ったけどそもそもBITを使うための考察等色々足らなかったなあと反省。
まず、2番めのクエリをこなすには、x<=i<=x2のキャンディ位数 + y<=j<=y2のキャンディ数 - 全キャンディ数 をすれば良い。
そのため、
- x行目からx2行目までのキャンディ数の計算
- x行目からx2行目間の各行にキャンディc個追加
とかを高速に計算できると良い。クエリ数wが10^5くらいあるので、10^3くらいで計算できると良い。
普通のBITだと前者は高速に計算できるが、後者ができなくて困る。
しかし、1行目からx行目までのキャンディ数を b1*x+b0と求めるようにすると、そこにBITが使える。
- b1(x2)*x2+b0(x2)-b1(x1-1)*(x1-1)+b0(x1-1)を計算するだけ。
- b1(x1,c) b0(x1,-(x1-1)*c), b1(x2+1,-c), b0(x2+1,y2*c)を計算
蟻本をガン見しながら現時点で理解した気になってるけど言葉で説明すると難しい…何度か蟻本を見て復習したい所。
コード
void bit_add( long long* bit, int pos, long long val,int size ){ // pos番目にvalを足した時のbitの総和の値を更新する while( pos < size ){ *(bit+pos) += val; pos += pos-(pos &(pos-1)); } } long long bit_get( long long* bit, int pos ){ long long ret = 0; while( pos != 0 ){ ret += *(bit+pos); pos = pos & (pos-1); } return ret; } int main(){ int n,m,w; cin >> n >> m >> w; long long n_bit_1[n+1]; long long n_bit_0[n+1]; long long m_bit_1[m+1]; long long m_bit_0[m+1]; memset( n_bit_1,0,sizeof(n_bit_1)); memset( n_bit_0,0,sizeof(n_bit_0)); memset( m_bit_1,0,sizeof(m_bit_1)); memset( m_bit_0,0,sizeof(m_bit_0)); long long sum = 0; for( int i = 0 ; i < w ; i++ ){ int type; cin >> type; if( type == 0 ){ int x1,y1,x2,y2,v; cin >> x1 >> y1 >> x2 >> y2 >> v; // add v*(y2-y1+1) to all x such that x1 <= x <= x2 long long addval = v*(y2-y1+1LL); bit_add( n_bit_1, x1, addval,n+1); bit_add( n_bit_0, x1, -addval*(x1-1),n+1 ); bit_add( n_bit_1, x2+1, -addval,n+1); bit_add( n_bit_0, x2+1, addval*x2,n+1 ); // add v*(x2-x1+1) to all y such that y1 <= y <= y2 addval = v*(x2-x1+1LL); bit_add( m_bit_1, y1, addval,m+1 ); bit_add( m_bit_0, y1, -addval*(y1-1),m+1 ); bit_add( m_bit_1, y2+1, -addval,m+1); bit_add( m_bit_0, y2+1, addval*y2,m+1 ); sum += v*(x2-x1+1LL)*(y2-y1+1LL); } else{ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; // x1 to x2 long long xsum = x2*bit_get(n_bit_1,x2)+bit_get(n_bit_0,x2); //cout << xsum <<", "; xsum -= (x1-1)*bit_get(n_bit_1,x1-1)+bit_get(n_bit_0,x1-1); //cout << (x1-1)*bit_get(n_bit_1,x1-1)+bit_get(n_bit_0,x1-1)<<endl; // y1 to y2 long long ysum = y2*bit_get(m_bit_1,y2)+bit_get(m_bit_0,y2); //cout << ysum <<", "; ysum -= (y1-1)*bit_get(m_bit_1,y1-1)+bit_get(m_bit_0,y1-1); //cout << (y1-1)*bit_get(m_bit_1,y1-1)+bit_get(m_bit_0,y1-1)<<endl; //cout << xsum << "+"<< ysum <<"-"<< sum << endl; cout << xsum + ysum - sum<<endl; } } return 0; }
SRM610
Codeforces２回位参加記書いてないけどSRMがあったので先にそっちを。
２完最弱でしたが550を本番に解けたので頑張った方かと思います。
多分Div1で２連続２完って初なんじゃなかろうか。
| Level | ProblemName | Status | Point |
| Easy | TheMatrix | Passed System Test | 162.87 |
| Medium | AlbertoTheAviator | Passed System Test | 181.35 |
| Hard | ???? | Unopened | 0.0 |
Easy TheMatrix
問題
0か1でうめつくされたテーブルを入力として与えるので、テーブル内に含まれる
01010101
10101010
みたいな、チェス盤観たいな配置になっている長方形の最大面積を答えよ
考えたこと
とりあえず、長方形の内部にセル(x1,y1)と(x2,y2)が含められるか否かは、(xi+yi+table[xi][yi])%2が(i=1,2)で等しいかどうかを見れば良い
また、テーブルの辺Nの最大が100なので長方形領域の左端座標×右端座標を与える全探索は計算量N^4で危うい気がする。
ってことは、開始地点の座標(a,b)と長方形の高さkを与えた時に横幅がさっと求められれば良い。
最初はDP?とか思って色々検討したけど上手くいかず。
と言うか、(x,y)から(x,Y)までが同じ長方形に含めることが可能、というY>yの値をnext[x][y]という配列に保存するとすれば、
(a,b)を決める→kを1から順に増やしつつ、next[x][y]を観ながら横幅決定
なんて流れにすることで計算量をN^3にすることができる
next[x][y]はxを固定してyの大きい順にごりごり計算すればN^2の計算量で求まる。
…ここまで考えるために２０分位時間使った悲しみ。
コード
int MaxArea(vector <string> board){ int h = board.size(); int w = board[0].size(); int bit[h][w]; memset( bit, 0 , sizeof(bit)); for( int i = 0 ; i < h ; i++ ){ for( int j = 0 ; j < w ; j++ ){ bit[i][j]= (i+j+board[i][j])%2; } } int next[h][w]; memset( next, 0, sizeof(next) ); for( int i = 0 ; i < h ; i++ ){ next[i][w-1] = w-1; for( int j = w-2; j >= 0 ; j-- ){ if( bit[i][j] == bit[i][j+1] ){ next[i][j] = next[i][j+1]; } else{ next[i][j] = j; } } } /* for( int i =0 ; i < h ; i++ ){ for( int j = 0 ; j < w ; j++ ){ cout << bit[i][j]; } cout << endl; } for( int i =0 ; i < h ; i++ ){ for( int j = 0 ; j < w ; j++ ){ cout << next[i][j]; } cout << endl; }*/ int ans = 0; for( int i = 0 ; i < h ; i++ ){ for( int j = 0 ; j < w; j++ ){ int b = bit[i][j]; int curw = next[i][j]-j+1; int curans = curw; int k = i; while( k < h && bit[k][j] == b ){ curw = min( curw, next[k][j]-j+1 ); curans = max( curans, curw*(k-i+1) ); k++; } ans = max(ans,curans); } } return ans; }
Medium AlbertoTheAviator
問題
燃料duration[i]を消費して後に燃料refuel[i]だけ獲得できるミッションが与えられる。(refuel[i]
考えたこと
ミッション遂行可能ならduration-refuelの小さい順にミッションしてけばいいんでないの？
この値が同じ場合はdurationの大きい順のほうがfuel不足でミッションできないというケースを弾けそう。
→試しに書いてみる
→テストケース 9 {4,6} {0,1}で落ちることが判明。(duration=4,refuel=0を先に実行してしまうと残り燃料が5になりduration=6,refuel=1を実行不可能)良心的なテストケースだ。
→durationの総和-refuelの総和がF以下となるような部分集合を取れば燃料切れを起こさないミッションの順番が作れるとか？
→100 {101} {1}で落ちる。
→そもそもそんなケースってdurationがFより大きい場合くらいしか無い…？ ならそれを弾くだけで良いのだろうけど。。。
→ちょっとサンプルを弄りながら考えてみるけどサラッと反例が作れない。
→コード書いたらサンプル全部通る
→悩んだけど550だし一端提出する
→しばらくして 9 {5,6} {1,1}で落ちることに気づく
→うーん、じゃあDPとかですか？ i番目のミッションまでで燃料をf残した状態を作る最大ミッション数をdp[i][f]にする50*5000のテーブルとか。
→durationの大きい順にミッションを舐めていると 10 {8,4} {0,2}で落ちるしうーん。。。
…
……
………
→ふと、終状態から考えてみる。 9 {4,6}{0,1}は2が解だけど9 {5,6}{1,1}は1が解になるのは、最終的に燃料が0になるから。と言うか、燃料が0になる時、直前でrefuelが非ゼロのミッションはできない。
→…ってことは、燃料fの直前にはrefuel[i]<=fのミッションしか実施できないってこと。
→refuel[i]<=fのミッションの中で燃料をあまり使わないミッションを選べば良い。これを任意の終わり状態について計算。
→サンプル通ったし9{4,6}{0,1}と9{5,6}{1,1}もちゃんと想定通りの解が帰ってくる。やったね。
コード
int MaximumFlights(int F, vector <int> duration, vector <int> refuel){ int size = duration.size(); vector<pair<int,int> > vec; for( int i = 0 ; i < size; i++ ){ vec.push_back( make_pair( refuel[i],duration[i] )); } sort( vec.begin(),vec.end()); int ans =0; for( int i = 0 ; i <= F ; i++ ){ //cout << "start "<<i<<endl; int curans = 0; int f = i; int ind = 0; priority_queue< int > q; while( ind < size && vec[ind].first <= f ){ //cout << vec[ind].first <<"-"<<vec[ind].second<<endl; q.push( vec[ind].first-vec[ind].second ); ind++; } while( !q.empty () ){ int cur = q.top(); q.pop(); f-=cur; if( f > F ) break; //cout << f << endl; curans++; while( ind<size && vec[ind].first <= f ){ q.push( vec[ind].first-vec[ind].second ); ind++; } } //cout <<"try"<<curans<<endl; ans =max(ans,curans); } return ans; }
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; }
SRM609
EasyとMedium解いたのにみんなMedium解いてて何これ怖い状態だった。両方通ってたのが救いか。
結果報告
| Level | ProblemName | Status | Point |
| Easy | getLongest | Passed System Test | 245.51 |
| Medium | minPacks | Passed System Test | 284.41 |
| Hard | isFairTree | Opened | 0.0 |
Easy getLongest
問題
任意のkにおいて、k個の'>'の後にk個の'<'が続く文字列をここでは呪文という。
'>'と'<'からなる文字列を与えるので、そこから文字を削除することによって得られる呪文の最長の長さを答えよ
考えたこと
左から>を探して右から<を探して行くgreedyでok。
コード
int getLongest(string S){ int size = S.size(); int head = 0; int tail = size-1; int ans = 0; while( head < size && S[head]=='<' ) head++; while( tail >= 0 && S[tail] == '>' ) tail--; //while( S[head]!='>' ) head++; //while( S[tail]!= '<' ) tail--; while( head < tail ){ ans += 2; head ++; tail --; while( head < size && S[head]=='<' ) head++; while( tail >= 0 && S[tail] == '>' ) tail--; } return ans; }
Medium minPacks
問題
K種類の色のボールがある。
第i色のボールの個数X[i]は以下の漸化式で定義される
X[0]=A, X[i+1]=(X[i]*B+C)%D+1 (for all i)
このボールをいくつかのpackに分類したい。
各packは必ずK以下のボールからなり
- 全て同じ色のボールである
- 全て違う色のボールである(variety)
のどちらかが充たされていなければならない。
最小のpack数を答えよ
考えたこと
varietyを使う場合は全部の色を1個ずつ使ったほうが得である(使わない理由がない)。
またvariety packを何個使うかで必要pack数が確定。
もし、variety packをY個使うとすると、
必要pack数は
というわけで、各色をKで割った時の数（端数切り上げ）が鍵となってくる予感がするので、X[i]をmod Kごとに管理しようと考える。
modcount[j] = (X[i]%K==jなiの数)とすると、
varietyをj個使えば[tex: \sum_{k
その後は、ボール数が0になった色があれば適宜modcount[j]を調整しつつ、
どうあがいても得をしなくなるvarietyの数を考えれば良いが…
何とかしてvarietyの範囲を決めないとTLEになる香りしかしない。
そこでふと、varietyをK個使った時に必要pack数はたかだかK個しか少なくならないことに気がつく。
ボール数が0になる色ができるとvariety packを使う意味はどんどん薄れてくることも加味すると、
これはつまり、varietyをK個以上使う意味は無い、ということを意味するとわかる。
…つまり、varietyが0〜K-1個の時だけ調べればいいんじゃーん、とわかる。
コード
int minPacks(int K, int A, int B, int C, int D){ long long X[K]; X[0]=A; for( int i = 1 ; i < K ; i++ ){ X[i] = (X[i-1]*B+C)%D +1; } int modcount[K]; memset(modcount, 0 , sizeof(modcount)); for( int i = 0 ; i < K ; i++ ){ modcount[X[i]%K]++; } int ans = 0; for( int i = 0 ; i < K ; i++ ){ ans += (X[i]+K-1)/K; } int ret= ans; int sum=0; for( int i = 1 ; i < K ; i++ ){ sum += modcount[i]; //cout << (i) << " varieties" << sum << "reduction "<<endl; ret = min( ret, ans+(i)-sum ); } return ret; }
Hard isFairTree
問題
親ノード番号を指定する配列を用いて木構造が与えられる。
子ノードは親ノードの下方にあることが約束されており、葉ノードは一直線上に並ぶよう配置しているとする。
今、葉ノードをp子の小領域（各領域無いは連続的であるものとする）に分割し、各分割領域の葉ノードに1〜Pの番号を降る（同じ領域のノードは同じ番号）
ナンバリングされてない各ノードについては、子ノードの番号のどれかが当確率で伝搬するものとする。
根ノードに各番号が等確率で伝搬するような葉ノードの分割方法があれば"YES"を、でなければ"NO"を返せ。
考えたこと
解けないけど面白そうな問題だなあと思います（小並感）
答えが"NO"になる例ってのは
- そもそも確率をP等分できない
- できるけど各領域が連続領域である、という規則に違反する…のどちらか。
各葉ノードに書かれた番号が根ノードに行き着く確率は子供がn兄弟なら1/n…という計算を根からひたすらやり直せば計算可能。
テストケース2を観てると、根ノードに行き着く確率が1/Pより小さい3兄弟を全て違う番号が取り合うような形だったら"NO"なんだなーと漠然と思う。
兄弟はなんかうまい感じでまとめないと行けないってことは分かった。でもだからどうしろ、って感じ。
SRM608
二連続0点でガッツリレートを落とす。２回続けて連続で１００くらいレートが落ちると虚しくなりますな。Easy安定してたと思ってたのは幻想だったのだろうか。
結果報告
| Level | ProblemName | Status | Point |
| Easy | MysticAndCandies | FailedSystemTest(practiced) | 0.0 |
| Medium | BigO | Opened(practiced) | 0.0 |
| Hard | ???? | Unopened | 0.0 |
Easy MysticAndCandies
問題
キャンディーが入った箱がある。
i番目の箱にはlow[i]以上high[i]以下のキャンディーが入っており、キャンディーの総和はCである。
Xこのキャンディーを取るためには最低何個の箱を開ける必要があるか
考えたこと
lowの大きい順に取って行ってXを超えるように取るだけとちゃいますのん？
→ははあ、lowが必要以上に少ない場合があるのだな。これくらいじゃダマされないぞ。
例えばあるiについて、とすると、low[i]>=X-Sであるはずである。
これをlow[i]がこれ以上変わらなくなるまで繰り返せば良いんじゃないかな。
→ケース３で引っかかるけどケース３が大きすぎてよくわからない現象にハマる
→highが変わるケースがある？
→あるiについて、とすると、high[i]<=X-Lであるはずである。それが原因？
→いまだにケース３が引っかかる
→(ﾟДﾟ)…
→ケース３では31を返すところ39(箱の総数)を返しているし、見た感じlow[i]の総和がXより小さそう
→lowが十分小さくても確実にXを越せる箱の組合せってなんだろか
→…high[i]の箱を選ばない、と決断した時は少なくともC-high[i]個のキャンディを貰えると保証される
→…highを小さい順にとってC-Xを超えないギリギリを考える？
→サンプル通ったので出す
（おまけ）
→チャレンジフェースでコーナーケースに気づいて落ちることを確信…orz
コード(SystemTest通過済み)
class MysticAndCandies { public: int minBoxes(int C, int X, vector <int> low, vector <int> high){ vector<int> trueLow; int size = low.size(); int hsum=-1; int lsum=-1; int curhsum = 0; int curlsum = 0; for( int i = 0 ; i < size; i++ ){ curhsum += high[i]; curlsum+=low[i]; } while( curhsum != hsum || curlsum != lsum ){ cout << hsum << ", " << lsum << endl; hsum = curhsum; lsum = curlsum; curhsum=0; curlsum=0; for( int i =0 ; i < size; i++ ){ int s = hsum-high[i]; if( low[i] < C-s ) cout <<"low["<< i << "<- "<< C-s << endl; low[i] = max(low[i],C-s); curlsum += low[i]; } for( int i = 0 ; i < size; i++ ){ int s = lsum-low[i]; if( high[i] > C-s ) cout <<"high["<< i << "<- "<< max(0,C-s) << C <<", "<< s << endl; high[i] = min( high[i], max(0,C-s) ); curhsum += high[i]; } } sort( low.begin(), low.end() ); sort( high.begin(),high.end() ); int cnt = 0; int cur=0; for( int i = size-1; i >= 0 ; i--){ cnt++; cur+=low[i]; if( cur >= X ) break; } int cnt2 = size; int cur2 = 0; for( int i = 0 ; i < size; i++ ){ if( cur2 +high[i] <= C-X ){ //本番はここのイコールが足らなかった cur2 +=high[i]; } else{ break; } cnt2--; } return min(cnt,cnt2); }
補足
本番だとこの方法でなぜよいか？が確証なかったのだけど、
ある箱の集合Bをとった時
(P1)lowの総和がX以上
(P2)Bの補集合に関して、high総和がC-X以下
P1 or P2ならX個キャンディーをゲットできることは明らか。
よって、この方法で解が得られない場合とは、P1もP2も成り立たない時ではX個キャンディーをゲットできない可能性があることを示せれば良い。
これは、not(P2)より、Bの補集合に対してキャンディーをC-X+1個振り分け、not(P1)よりBに対してキャンディをX-1個振り分けることができる…と、すぐにわかる。
Medium BigO
問題
有向グラフを与える。このグラフ上の長さLのパスの個数がと表せる時、kを答えよ。オーダーがこれ以上の時は-1を返せ。
考えたこと
ある強連結成分について一周するパスが複数ある場合はそのパスの選び方を考えるだけでオーダーが２の累乗になる。
これだけならワーシャルフロイドとか書いた後に任意の頂点について、その頂点の子供の中で自分に戻ってこれるものが２つ以上あれば-1を返す、というコードにすれば良いが…
ってどんな場合かわからずに撃沈。
復習
今回参考にしたのはlogicmachineさんのブログ(http://d.hatena.ne.jp/logicmachine/20140207)
になる場合って、強連結成分AとBがA→Bへ移動可能なときに、どのくらいの長さAをぐるぐる回って後にBに移動するか、という所で発生すると理解する。
あとは蟻本を眺めながら強連結成分分解のプログラム書いてゴリゴリ。
どっちみち強連結成分分解のライブラリ用意してないとこの問題は解けなかった臭いですな。
途中で、成分の大きさが１しか無いものはkの増加に寄与しないこと（そこの内部でぐるぐる周れないから）に気づいて少しハマったけど、その他はまあそこまではまらなかったような。
どちらかと言うと強連結成分分解を極力自力で書こうとした結果あり本と似たコードに行き着いて「あーよくデキてるなー」と思った位。
コード(SystemTest通過済み)
#define VSIZE 50 vector<int> edge[VSIZE]; vector<int> rev_edge[VSIZE]; vector<int> labelledNode; int topologicalLabel[VSIZE]; bool used[VSIZE]; void initialize(){ for( int i = 0 ; i < VSIZE; i++ ){ edge[i].clear(); rev_edge[i].clear(); } labelledNode.clear(); memset( topologicalLabel, -1, sizeof(topologicalLabel) ); memset( used,false,sizeof(used)); } void add_edge( int start, int end ){ edge[start].push_back(end); rev_edge[end].push_back(start); } void label_dfs( int node ){ if( used[node] ==true ) return; used[node]=true; int n_edge=edge[node].size(); for( int i = 0 ; i < n_edge; i++ ){ int next = edge[node][i]; label_dfs( next ); } labelledNode.push_back( node ); return; } void scc_dfs(int node, int label ){ if( used[node] ==true )return; used[node]=true; int n_edge = rev_edge[node].size(); for( int i = 0 ; i < n_edge; i++ ){ int next = rev_edge[node][i]; scc_dfs(next,label); } topologicalLabel[node]=label; } int scc(int size){ for( int i = 0 ; i < size; i++ ){ if( used[i]==false) label_dfs(i); } #ifdef DEBUG cout<<"LABEL: "; for( int i = 0 ; i < size; i++ ){ cout << labelledNode[i] <<", "; } cout << endl; #endif int label = 0; memset( used, false , sizeof(used)); for( int i = size-1; i>= 0 ; i-- ){ int node = labelledNode[i]; if( used[node]==false ) scc_dfs(node, label++); } #ifdef DEBUG for( int i = 0 ; i < size; i++ ){ cout << i << "-" << topologicalLabel[i] <<" "; } cout << endl; #endif return label; } int G[VSIZE][VSIZE]; int length[VSIZE]; int nodecnt[VSIZE]; int length_dfs( int i ){ if( length[i] != -1 ) return length[i]; int offset = 1; if( nodecnt[i] < 2 ) offset=0; int ans =offset; for( int j = 0 ; j < VSIZE; j++ ){ if( G[i][j]==1 ){ ans = max( length_dfs(j)+offset,ans); } } return length[i] = ans; } class BigO { public: int minK(vector <string> graph){ initialize(); int size = graph.size(); for( int i = 0 ; i < size; i++ ){ for( int j = 0 ; j <size; j++ ){ if( graph[i][j] == 'Y' ){ add_edge(i,j); } } } int k = scc(size); memset( G, 0, sizeof(G)); memset( nodecnt, 0 , sizeof(nodecnt)); for( int i = 0; i < size; i++ ){ nodecnt[topologicalLabel[i]]++; } int cnt[size]; memset( cnt, 0, sizeof(cnt)); for( int i = 0 ; i < size; i++ ){ for( int j = 0 ; j < size; j++ ){ if( graph[i][j] == 'Y' ){ int start = topologicalLabel[i]; int end = topologicalLabel[j]; if( start != end ){ G[start][end] = 1; } else{ cnt[i]++; if( cnt[i] >= 2 ) return -1; } } } } memset( length, -1,sizeof(length) ); for( int i = 0 ; i < k ; i++ ){ if( length[i] == -1 ) length_dfs( i ); } int ans = 0; for( int i = 0 ; i < k ; i++ ){ ans = max( ans, length[i] ); } return max(0,ans-1); } };
