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); } };
