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