ARC003 C - 暗闇帰り道
C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder
- 二分探索 + bfs な問題。
- 以前解いたのにもかかわらず間違えまくった...。
- bfs では pop 直後に vis を見てはじいてしまったり(致命的)、high = 1<<30 から始めたり、val = min(val,pow(0.99,t)*..) を保持しておこうとしたり...無駄なことを。シンプルに書くことを心がけよう。
class C_DarknessWayHome { public: void solve(void) { int N,M; cin>>N>>M; vector<string> field(N); int sx,sy,gx,gy; REP(i,N) { cin>>field[i]; REP(j,M) { if (field[i][j] == 'g') { gx = j; gy = i; } if (field[i][j] == 's') { sx = j; sy = i; } } } const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; // low より明るい状態で goal までたどりつけるか bfs auto bfs = [&](double low) { queue<tuple<int,int,int>> que; que.emplace(sx,sy,0); vector<vector<bool>> vis(N,vector<bool>(M,false)); while ( !que.empty() ) { int x,y,t; tie(x,y,t) = que.front(); que.pop(); REP(d,4) { int nx = x+dx[d]; int ny = y+dy[d]; if (nx < 0 || M <= nx || ny < 0 || N <= ny) continue; if (field[ny][nx] == '#') continue; if (field[ny][nx] == 's') continue; if (field[ny][nx] == 'g') return true; if ( vis[ny][nx] ) continue; double val = pow(0.99,t+1)*(field[ny][nx]-'0'); if (val < low) continue; vis[ny][nx] = true; que.emplace(nx,ny,t+1); } } return false; }; // ゴールに到達しないケースを先にやる if ( !bfs(0.0) ) { cout<<-1<<endl; return; } double low = 0; double high = 10; // fabs(low-high) < EPS の EPS が小さすぎるとループ回数が // 大きくなって TLE してしまうので最大 100 回でやる // // O(100*N*M) REP(i,100) { if (fabs(low-high) < 1e-10) break; double mid = (low+high)*0.5; if ( bfs(mid) ) low = mid; else high = mid; } cout<<setprecision(20)<<low<<endl; } };
No.206 数の積集合を求めるクエリ
No.206 数の積集合を求めるクエリ - yukicoder
- A[i],B[i] の上限が高々 10^5 であることに着目して解く。
- 以下は他の人のコードを参考にして解いた。bitset 使うとこんなに簡単に書けるとは..。すげー。
class QueryOfNumberProductSet { public: void solve(void) { int L,M,N; cin>>L>>M>>N; // A[i],B[i] の上限が高々 10^5 であること // A,B にて同じ数字が存在しないこと // から A,B を bitset で扱うと A & B の計算、 B の一律加算が簡単に表現できる bitset<100001> A; bitset<100001> B; REP(i,L) { int x; cin>>x; A.set(x); } REP(i,M) { int x; cin>>x; B.set(x); } int Q; cin>>Q; // O(Q*N/64) REP(v,Q) { // 加算によってビットが左にずれる cout<<(A & (B<<v)).count()<<endl; } } };
class QueryOfNumberProductSet { public: void solve(void) { int L,M,N; cin>>L>>M>>N; // // f(x) = ∑ x^A[i] // g(x) = ∑ x^(N-B[i]) (次数がN-B[i]なのは畳み込み後の次数に A[i]-B[i] を入れたいから) // // とするとき // // (f*g)(x) = ∑∑ a[i]b[j] x^(A[i]-B[j]+N) // = ∑ c[i] x^i // // c[N+v] = #{(i,j) | (A[i]-B[j]+N == N+v) } となる // // よって FFT が使える // vector<double> a(N+1,0); vector<double> b(N+1,0); vector<double> c(2*(N+1),0); REP(i,L) { int x; cin>>x; // 次数に対応する係数だけ 1 にする a[x] = 1; } REP(i,M) { int x; cin>>x; b[N-x] = 1; } convolve(a,b,c); int Q; cin>>Q; REP(v,Q) { // round してから cast しないと期待どおりの値にならない cout<<(int)round(c[N+v])<<endl; } } };
No.209 Longest Mountain Subsequence
No.209 Longest Mountain Subsequence - yukicoder
- 何も考えることもない単純な DP。のはずが結構バグを作ってしまった...。
- O(T*N^3) じゃ間に合わないので DP 部分を O(N^2) にしないとダメなのかなぁと思いきやそうでもなかった。
class LongestMountainSubsequence { public: void solve(void) { int T; cin>>T; // O(N^3*T) REP(i,T) { int N; cin>>N; vector<ll> A(N); REP(i,N) cin>>A[i]; vector<vector<int>> dpL(N,vector<int>(N,0)); vector<vector<int>> dpR(N,vector<int>(N,0)); REP(i,N) dpL[i][i] = dpR[i][i] = 1; REP(i,N) FOR(j,i+1,N) { if (A[i] < A[j]) dpL[i][j] = 2; if (A[i] > A[j]) dpR[i][j] = 2; } REP(i,N) FOR(j,i,N) FOR(k,j,N) { if ( A[i] < A[j] && A[j] < A[k] && abs(A[i]-A[j]) < abs(A[j]-A[k]) ) dpL[j][k] = max(dpL[j][k], dpL[i][j]+1); } // 単調減少の方は逆順のループ for (int k = N-1; k >= 0; --k) for (int j = k; j >= 0; --j) for (int i = j; i >= 0; --i) { if ( A[i] > A[j] && A[j] > A[k] && abs(A[i]-A[j]) > abs(A[j]-A[k]) ) dpR[i][j] = max(dpR[i][j], dpR[j][k]+1); } int cnt = 1; // 単調増加・単調現象あわせたもの REP(i,N) REP(j,i) FOR(k,i+1,N) { // A[i] は二重にカウントされているので -1 cnt = max(cnt, dpL[j][i] + dpR[i][k] - 1); } // 単調部分のみ REP(i,N) FOR(j,i+1,N) cnt = max({cnt, dpL[i][j], dpR[i][j]}); cout<<cnt<<endl; } } };
No.184 たのしい排他的論理和(HARD)
No.184 たのしい排他的論理和(HARD) - yukicoder
- uint64 を 64列 x N 行の mod 2 上の行列と考えて rank をもとめればよい。
- col = 63 にすべきところを col = 64 にしたりしてハマった。
// uint64_t 吐き出し法 std::vector<uint64_t> sweep_uint64(const std::vector<uint64_t> &A) { auto a = A; int n = a.size(); int row = 0; // O(64*N) for (int col = 63; col >= 0; --col) { int pivot = row; //row 行目以降だけ見る // 先頭から col 番目のビットが立っている a[i] を見つける while ( pivot < n && !(a[pivot] & 1ULL<<col) ) ++pivot; // col 番目にビットが立つ a はなかった if (pivot == n) continue; std::swap(a[row], a[pivot]); for (int i = row+1; i < n; ++i) { if ( a[i] & 1ULL<<col) a[i] ^= a[row]; } ++row; } return a; } using namespace std; class HappyXorHard { public: void solve(void) { int N; cin>>N; vector<uint64_t> A(N); REP(i,N) cin>>A[i]; A = sweep_uint64(A); int k = count_if(RANGE(A), [](uint64_t a) { return (a>0); }); cout<<(1LL<<k)<<endl; } };
No.186 中華風 (Easy)
- 中国剰余定理を使う問題。
- 蟻本に乗ってたライブラリを使ってしまったが、これくらい自力でかけないとダメかなぁ...。
- 正整数を出力するので 0 や負は変換しないとダメ。
template <typename T> std::pair<T,T> linear_congruence( const std::vector<T> &A, const std::vector<T> &B, const std::vector<T> &M) { T x = 0, m = 1; for (int i = 0; i < A.size(); ++i) { T a = A[i] * m; T b = B[i] - A[i] * x; T d = gcd(M[i], a); if (b % d) // solution does not exist. return std::make_pair(0, -1); T md = M[i]/d; T t = b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d); x = x + m * t; m *= M[i] / d; } return std::make_pair(x % m, m); } class ChiniseStyleEasy { public: void solve(void) { vector<ll> x(3); vector<ll> y(3); REP(i, 3) cin>>x[i]>>y[i]; vector<ll> a(3,1); ll z,m; tie(z,m) = linear_congruence(a,x,y); if (m < 0) { cout<<-1<<endl; return; } ll Y = max({y[0],y[1],y[2]}); if ( z < 0 ) z += (-z/m+1)*m; ll X = Y/m*m + z; if ( X == 0 ) cout<<m<<endl; else cout<<X<<endl; } };
No.147 試験監督（2）
- 繰り返し２乗法を使うもんだい。フィボナッチ数列が隠れているとは...
- 行列繰り返し2乗法で高速化できないか？というのはテクニックとして覚えておこう。(蟻本で見てはいたんだけどなぁ...)
const ll Mod = (int)(1E+9)+7; class Invigilator2 { public: // // x^(10^k) = x^(10^(k-1)*10) // = x^(10^(k-1)) * ... * x^(10^(k-1)) // なので計算量が落とせる ll tenPow(ll a, string k) { reverse(RANGE(k)); ll ret = 1LL; ll prev = a; // a^(10^(k-1)) // O(|k|*10) <= 2000 for (auto c : k) { ll cur = 1LL; ll ten = 1LL; REP(i,c-'0') (cur *= prev) %= Mod; (ret *= cur) %= Mod; REP(i,10) (ten *= prev) %= Mod; prev = ten; } return ret; } // P(x) := x 個いすがある机で x 番目に座る // Q(x) := x 個いすがある机で x 番目に座らない // とすると // // P(x+1) = Q(x) // Q(x+1) = P(x)+Q(x) // の関係式となる // // R(x) = P(x)+Q(x) が求める組み合わせ数で // R(x+1) = Q(x) + P(x) + Q(x) // = R(x) + R(x-1) // R(0) = 1 // R(1) = 2 // // よりこれはフィボナッチ数列となる // フィボナッチ数は行列累乗で O(log(n)) で解ける // // |R(x+1)| |1 1| |R(x) | // | | = | |*| | // |R(x) | |1 0| |R(x-1)| // // S(x+1) = B*S(x) // S(x) = B^x * S(0) // typedef array<ll,4> Mat; Mat mul(const Mat &a, const Mat &b) { return Mat{(a[0]*b[0]%Mod+a[1]*b[2]%Mod)%Mod, (a[0]*b[1]%Mod+a[1]*b[3]%Mod)%Mod, (a[2]*b[0]%Mod+a[3]*b[2]%Mod)%Mod, (a[2]*b[1]%Mod+a[3]*b[3]%Mod)%Mod}; } Mat mpow(const Mat &x, ll k) { Mat a = x; Mat b{1,0, 0,1}; while (k > 0) { if (k & 1) b = mul(b,a); a = mul(a,a); k >>= 1; } return b; } ll calc(ll x) { auto a = mpow(Mat{1,1,1,0}, x); return mul(a, Mat{2,0, 1,0})[2]; } void solve(void) { int N; cin>>N; vector<ll> C(N); vector<string> D(N); REP(i,N) { cin>>C[i]>>D[i]; } ll cnt = 1LL; // O(N*(2000+log(D[i]))) <= 6*10^7 REP(i,N) { (cnt *= tenPow(calc(C[i]), D[i])) %= Mod; } cout<<cnt<<endl; } };
No.205 マージして辞書順最小
- 貪欲法。priority_queue で書くより set で書く方が綺麗にかけたかも。priority_queue の compare 関数がうまく実装できなかった...。
class MergeAndLexicographicOrderSort { public: void solve(void) { int N; cin>>N; auto lex_comp = [](string a, string b) { return b<a; }; priority_queue<string,vector<string>,decltype(lex_comp)> S(lex_comp); REP(i,N) { string s; cin>>s; // z < za の優先度にしてほしいので、末尾に全ての文字コードよりも // 優先度の低い文字コード ~ を追加しておく S.push(s+'~'); } string T; while (!S.empty()) { string s = S.top(); S.pop(); T += s[0]; s = s.substr(1); // 末尾の ~ まで達したら再挿入はなし if (s.length() > 1) S.push(s); } cout<<T<<endl; } };
