No.180 美しいWhitespace (2)
No.180 美しいWhitespace (2) - yukicoder
- 三分探索を使う問題。三分探索は初めて書いた。double の三分探索でWAくらったりしたが、long long で三分探索して AC。
- inf = (1<<30) じゃ足りなかったりした。
- 二分探索でもできるらしい。
- 極値は線分の交点上でとるはずなんで、うまく必要な交点だけ計算して O(N^2) で計算するって手もあるみたい。
class BeautifulWhitespace2 { public: void solve(void) { int N; cin>>N; vector<ll> a(N); vector<ll> b(N); REP(i,N) cin>>a[i]>>b[i]; // // // / | // --- / | // --- / | // // のような傾きの異なる 3 直線とすると // max(a[i]+b[i]*x) は領域 A 側にもっとも近い線分 // min(a[i]+b[i]*x) は領域 B 側にもっとも近い線分 // // |/ // A / // /| // /|------- // ----/- // / | B // // によって構成される。また max(...) >= min(...) なので // 差は必ず 0 以上となる。よって f(x) は極値を 1 つもつ凹関数となる。 // 三分探索をすればよい。 const ll inf = (1LL<<60); // O(N) auto f = [=](ll x) { if (x <= 0) return inf; ll maxF = a[0]+b[0]*x; ll minF = a[0]+b[0]*x; FOR(i,1,N) { minF = min(minF, a[i]+b[i]*x); maxF = max(maxF, a[i]+b[i]*x); } return maxF - minF; }; const int maxLoop = 1000; ll left = 1; ll right = (1<<30); // O(N*1000) for (int loop = 0; loop < maxLoop; ++loop) { if ( left == right ) break; // // l ---u---v--- r // ll u = (left*2 + right)/3; ll v = (left + right*2)/3; if ( f(u) > f(v) ) left = u; else right = v; } ll x = (left+right)/2; cout<<x<<endl; } };
No.220 世界のなんとか2
- 桁 DP で解く問題。3 の倍数をどうやって桁 DP に組み込むのかというと、ある桁までの mod 3 の値を状態として持っておけばよい。
- 計算解として 10^p - 1 - 2/3 * 9^p ってのもあるらしい。
- とりあえず強引にでも DP で解けるようになりたい。
class SomethingOfWorld2 { public: void solve(void) { int p; cin>>p; // 10^p 以下の数字なので p-1 桁までみればよい --p; // 3 が含まれるかは桁 DP でやればよい // 3 の倍数がいくつあるかを桁 DP に取り入れたい // // 245 = 2*10^2 + 4*10 + 5 // = 2 + (1 + 2) (mod 3) // = 2 (mod 3) // // 各桁の mod 3 での和がその数字の mod 3 での値となる。 // そこでその桁までの mod 3 の値を状態として持てばよい // 同時に 3 を持つかどうかも状態として持つ // // dp[i][j][k] := k mod 3 と一致する i 桁目までの数字のうち 3 // を持つ/持たない (j==1/0) ものの数 // vector<vector<vector<ll>>> dp(p+1,vector<vector<ll>>(2,vector<ll>(3,0))); REP(k,10) { if ( k == 3 ) ++dp[0][1][k%3]; else ++dp[0][0][k%3]; } ll ten = 10; REP(i,p) { REP(j,3) REP(k,10) { int l = (ten*k + j)%3; // i 桁目を追加したときの mod 3 の値 if ( k == 3 ) dp[i+1][1][l] += dp[i][0][j]; else dp[i+1][0][l] += dp[i][0][j]; dp[i+1][1][l] += dp[i][1][j]; } ten *= 10; } ll cnt = 0; REP(i,3) cnt += dp[p][1][i]; cnt += dp[p][0][0]; // 0000...00 のケースをのぞく cout<<(cnt-1)<<endl; } };
No.217 魔方陣を作ろう
- やるだけ問題。でも割と楽しかった。
class MakeMagicSquare { public: typedef vector<vector<int>> Mat; void report(const Mat &mat) { int n = mat.size(); REP(i,n) { REP(j,n) { cout<<mat[i][j]; if (j < n-1) cout<<" "; } cout<<endl; } } Mat makeOddMS(int n) { Mat mat(n,vector<int>(n,0)); int i,j; i = 0; j = n/2; for (int k = 1; k <= n*n; ++k) { mat[i][j] = k; int ii = i, jj = j; i = (i-1+n)%n; j = (j+1)%n; if ( mat[i][j] > 0) { i = (ii+1)%n; j = jj; } } return mat; } Mat make4xMS(int n) { Mat mat(n,vector<int>(n,0)); auto tmp(mat); // 白黒ボードとして tmp を塗る // 4x4 ブロックに区切り対角線部のみぬる REP(dx,n/4) REP(dy,n/4) { // 左上の座標を計算 int x = 4*dx; int y = 4*dy; REP(i,4) { tmp[x+i][y+i] = 1; tmp[x+i][(4+y)-1-i] = 1; } } int x,y; x = y = 0; // 左上から右へブロックの対角線部のみ数字をおく for (int k = 1; k <= n*n; ++k) { if ( tmp[y][x] ) mat[y][x] = k; ++x; if ( x == n ) { ++y; x = 0; } } x = y = n-1; for (int k = 1; k <= n*n; ++k) { if ( !tmp[y][x] ) mat[y][x] = k; --x; if ( x < 0 ) { --y; x = n-1; } } return mat; } Mat LUX(int n) { int m = n/2; auto small = makeOddMS(m); REP(i,m) REP(j,m) small[i][j] = 4*(small[i][j]-1); vector<vector<char>> lux(m,vector<char>(m,'L')); REP(i,m) lux[m/2+1][i] = 'U'; FOR(i,m/2+2,m) REP(j,m) lux[i][j] = 'X'; swap(lux[m/2][m/2], lux[m/2+1][m/2]); Mat mat(n,vector<int>(n,0)); const Mat L = {{4,1}, {2,3}}; const Mat U = {{1,4}, {2,3}}; const Mat X = {{1,4}, {3,2}}; REP(i,n) REP(j,n) { int iy = i/2; int ix = j/2; int dy = i%2; int dx = j%2; switch ( lux[iy][ix] ) { case 'L': mat[i][j] = L[dy][dx] + small[iy][ix]; break; case 'U': mat[i][j] = U[dy][dx] + small[iy][ix]; break; case 'X': mat[i][j] = X[dy][dx] + small[iy][ix]; break; } } return mat; } void solve(void) { int n; cin>>n; int N = n*(n*n+1)/2; if (n % 2 == 1) { report(makeOddMS(n)); } else if (n % 4 == 0) { report(make4xMS(n)); } else if (n % 4 == 2) { report(LUX(n)); } } };
SRM 679 Div2 Hard ForbiddenStreets
TopCoder Statistics - Problem Statement
- 本番では開いただけの問題。最短経路が複数あるとき、指定の経路を含むもの以外の最短経路を見つけるのがミソな問題。
- どうやって見つけるのかは思いつず、以下のブログを参考にした。最短経路のパターン数を持っておいて、パターン数を比較すればよいのか。
- ワーシャルフロイドでも最短パターン数を計算できるのかもだけど、うまく書けなかった。
- 以下コードではとりあえず long long にパターン数を格納して system test が通ったけど、下記ブログにあるように mod で計算しないとテストケースが厳しいと long long オーバーフローして落ちてしまうのかも。
TopCoder SRM 679 Div2 Hard ForbiddenStreets - kmjp's blog
class ForbiddenStreets { public: vector <int> find(int N, vector <int> A, vector <int> B, vector <int> time) { int M = A.size(); const int inf = (1<<30); vector<vector<ll>> dist(N,vector<ll>(N,inf)); // 最短経路長 vector<vector<ll>> pat(N,vector<ll>(N,0)); // 最短経路数 vector<vector<pair<int,int>>> tree(N); REP(i,M) { tree[A[i]].emplace_back(B[i],time[i]); tree[B[i]].emplace_back(A[i],time[i]); } // O(N*M*log(N)) REP(start,N) { typedef pair<int, int> P; priority_queue<P,vector<P>,greater<P>> pque; auto &d = dist[start]; d[start] = 0; pat[start][start] = 1; pque.emplace(0,start); while ( !pque.empty() ) { int u,t; tie(t,u) = pque.top(); pque.pop(); if ( d[u] < t ) continue; for (const auto &edge : tree[u]) { int to,cost; tie(to,cost) = edge; if ( d[u] + cost < d[to] ) { d[to] = d[u] + cost; // 最短経路長が更新されたのでパターン数も初期化 pat[start][to] = 0; pque.emplace(d[to], to); } // 最短経路長が一致するときはパターン数を加算 if ( d[u] + cost == d[to] ) { pat[start][to] += pat[start][u]; } } } } vector<vector<int>> cnt(N,vector<int>(N,0)); vector<int> ret(M,0); REP(i,M) { // A[i]~B[i] 間を止めるとき REP(j,N) REP(k,N) { // 最短経路に A[i]~B[i] が含まれるときをチェック // pattern 数が一致しない(他に最短経路がある)ときはスキップ if ( dist[j][k] == dist[j][A[i]] + time[i] + dist[B[i]][k] && pat[j][k] == pat[j][A[i]] * pat[B[i]][k] ) { ++ret[i]; } } } return ret; } };
SRM 679 Div2 Medium
TopCoder Statistics - Problem Statement
- 復習。復習。
- 問題文の意味がわからなくてタイムロスしてしまった。
- ある時間での勝者を探す。時間の範囲は 0~10^9 なので単純なループじゃ TLE するが、各 submit time とその前後 1 秒くらいだけ調べればよいので 3*n のループで済む。
- submit 数がどれくらなのかがちょっとわからないので、累積和を事前に計算して、二分探索によって高速化しておく。
- 本番時間ギリギリでサンプル通してサブミットしたのに system test で落ちた...。
- 原因は time == 0 のときの累積和計算を push_back していなかったから。
- 区間端のコーナーケースの処理忘れをしないように注意しよう。もったいなさすぎる。
class ContestScoreboard { public: vector <int> findWinner(vector <string> scores) { int n = scores.size(); vector<ll> ret(n,0); vector<string> names(n); vector<vector<pair<ll,ll>>> sbm(n); // vector<vector<pair<ll,ll>>> sum(n); vector<ll> time; // O(n) REP(i,n) { auto tokens = split(scores[i], " "); names[i] = tokens[0]; FOR(j,1,tokens.size()) { auto v = split(tokens[j],"/"); ll t,val; t = stoll(v[1]); val = stoll(v[0]); sbm[i].emplace_back(t,val); //sort by time // 探索対象となる時間は submit time とその前後 1 秒くらいでよい time.push_back(max(t-1,0LL)); time.push_back(t); time.push_back(max(t+1,0LL)); } sort(RANGE(sbm[i])); // 累積和を計算しておく ll s = 0; sum[i].emplace_back(0,0); // time == 0 のときを入れないとダメ REP(j,sbm[i].size()) { ll t,v; tie(t,v) = sbm[i][j]; s += v; sum[i].emplace_back(t,s); } } // 重複時間削除 sort(RANGE(time)); time.erase(unique(time.begin(), time.end()), time.end()); // O(n*3 * n * log(m)) vector<int> win(n,0); for (auto T : time) { int maxj = -1; string maxName="$"; ll maxScore = -1; REP(i,n) { auto idx = lower_bound(RANGE(sum[i]),make_pair(T,-1LL)) - sum[i].begin(); if (idx == 0) continue; ll val; tie(ignore,val) = sum[i][idx-1]; if ( val > maxScore || (val == maxScore && names[i] < maxName)) { maxj = i; maxName = names[i]; maxScore = val; } } if (maxj >= 0) win[maxj] = 1; } return win; } };
No.173 カードゲーム（Medium）
No.173 カードゲーム（Medium） - yukicoder
- ARC003 D - シャッフル席替え - shifth’s blogでやったモンテカルロ法の復習問題。というかこの問題を解くために ARC003 を解いたんだけど。
- 等確率を計算したつもりが等確率になっていなくてバグに悩んだ。できるだけシンプルに書くようにしないと...。
class CardGameMedium { public: void solve(void) { int N; double Pa,Pb; cin>>N>>Pa>>Pb; vector<int> A(N); vector<int> B(N); REP(i,N) cin>>A[i]; REP(i,N) cin>>B[i]; std::mt19937 engine; uniform_real_distribution<double> g(0,1); const int T = 200000; // O(T*N^2*log(N)) double p = 0.0; REP(_,T) { int scoreA = 0; int scoreB = 0; auto a(A); auto b(B); REP(i,N) { int ia,ib; ia = ib = 0; if (a.size() > 1) { sort(RANGE(a)); sort(RANGE(b)); double u = g(engine); if ( u >= Pa ) {// 最小値以外のカードを当確率で選ぶ int x = (u-Pa)/(1.0-Pa)*(a.size()-1); ia = x+1; } u = g(engine); if ( u >= Pb ) { int x = (u-Pb)/(1.0-Pb)*(b.size()-1); ib = x+1; } } if (a[ia] > b[ib]) scoreA += a[ia]+b[ib]; else if (a[ia] < b[ib]) scoreB += a[ia]+b[ib]; a.erase(a.begin()+ia); b.erase(b.begin()+ib); } if (scoreA > scoreB) p += 1; } p /= T; cout<<setprecision(20)<<p<<endl; } };
ARC003 D - シャッフル席替え
- モンテカルロ法を使う問題。
- 解法については以下のスライドを参照。技術的な内容だけではなくて表現がかなり面白かったです。こういうの好き。
ARC#003D from nullmineral
www.slideshare.net
- Hoeffding 不等式については以下が参考になる。
Hoeffdingの不等式 - 機械学習の「朱鷺の杜Wiki」
http://www.math.cm.is.nagoya-u.ac.jp/~kanamori/lecture/lec.2008.1st.stat-ana/01.pdf
- 何回シミュレーションすればいいのかについてなんだけど、他の人のコードを見ると施行回数が十分なだけループするのではなくて、制限時間分ループするという手もあるみたい。
class D_ShuffleDesk { public: void solve(void) { // 単純な数え上げだと O((N*N)^K) になって計算不可 // 許容誤差が大きいのでモンテカルロ法で解く // // 確率 p で 1, 1-p で 0 をとる確率分布を Bernoulli 分布という // // X を Bernoulli 分布に従う確率変数とすると // // P(X=1) = p // P(X=0) = 1-p // // である。 // // --- Hoeffding 不等式(Bernoulli 確率変数版) --- // // X1,...,Xn が独立な Bernoulli 確率変数とするとき // n // P(|1/n * Σ Xi - p| ≧ ε) ≦ 2 * e^(-2*n*ε^2) // i=1 // となる。 // int N,M,K; cin>>N>>M>>K; vector<vector<bool>> bad_pair(N,vector<bool>(N,false)); REP(i,M) { int a,b; cin>>a>>b; bad_pair[a][b] = bad_pair[b][a] = true; } // // テストケースが 100 個あるとすると // 0.9999^100 = 0.9900... より // 1ケース正当する確率が 99.99% くらいならよい // ε=0.002 として Hoeffding 不等式より // // 2*e^(-2*n*ε^2) < (1.0-0.9999) = (誤答確率) // <=> n > 1.23794e+06 // // 1300000 くらい施行すれば十分 // double p = 0.0; const int n = 1300000; vector<int> idx(N); // O(n*(K+N)) REP(i,n) { // そのままシュミレーション iota(RANGE(idx),0); auto tmp(idx); REP(k,K) { random_shuffle(RANGE(tmp)); swap(idx[tmp[0]],idx[tmp[1]]); } int X = 1; REP(j,N) { if ( bad_pair[idx[j]][idx[(j+1)%N]] ) X = 0; } p += X; } p /= n; cout<<setprecision(20)<<p<<endl; } };
