yukicoder 171 参加記録
yukicoder 171に参加しました。
5/6完で45位でした。
星3のDPが解けなかった。
No.552 十分簡単な星1の問題
long long でもオーバーフローするのでstringで受け取って+“0"する。
ただし、0が入力される場合はそのまま出力することに注意。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { string s; cin >> s; if(s.length() == 1 && s[0] == '0') cout << 0 << endl; else cout << s << 0 << endl; return 0; }
No.553 AlphaCoder Rating
やるだけだけど数式が複雑でめんどくさそうなので後回しにした。
誤差±1までOKなので誤差を気にせず実装して大丈夫だった。
逆関数の知識が必要。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { int N; cin >> N; double r[N]; FOR(i,0,N) cin >> r[i]; double Fn, fn, f1, finf; FOR(i,1,N+1) Fn += pow(0.81, i); Fn = sqrt(Fn); double tmp = 0; FOR(i,1,N+1) tmp += pow(0.9, i); Fn /= tmp; f1 = sqrt(0.81) / 0.9; finf = sqrt(0.81 / 0.19) / (0.9 / 0.1); fn = (Fn - finf) / (f1 - finf) * 1200; double ans = 0; FOR(i,1,N+1) { ans += pow(2, r[i-1] / 800.0) * pow(0.9, i); } ans /= tmp; ans = 800 * log(ans) / log(2); ans -= fn; cout << int(ans) << endl; return 0; }
No.554 recurrence formula
第2項から順に求めていく。
和の部分を毎回求めていたらO(n2)となるのでTLE。
累積和を保存しておけばO(n)となってAC。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const ll mod = 1e9 + 7; int main() { int n; cin >> n; ll oddsum = 1, evensum = 0; ll a = 1; FOR(i,2,n+1) { if(i % 2 == 0) { a = i * oddsum; a %= mod; evensum += a; evensum %= mod; } else { a = i * evensum; a %= mod; oddsum += a; oddsum %= mod; } } cout << a % mod << endl; return 0; }
No.555 世界史のレポート
DPぽいなと思ったけどできなかった問題。
dp[i] := 長さをi以上にするのに必要な最小コストとしてしまうとO(n2)となりTLE。
dp[i] := 長さをちょうどiにするのに必要な最小コストとする。 長さをiにするには、長さがiの約数dになった時にコピーしてペーストを(i - d) / d回する。 iの約数の個数は高々 らしいのでO()となりAC。
長さがn-1の時にコピーしてペースとしたら2n-2になるので、dp[2n-2]まで計算する。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { int N, C, V; cin >> N >> C >> V; ll dp[2*N]; FOR(i,0,2*N) dp[i] = 1e9; dp[0] = dp[1] = 0; // ちょうどiにする FOR(i, 1, 2*N) { // Aの個数がiの約数dになったらコピーしてそのあとペースト // (i / d - 1) 回足せばちょうどiになる for(int d = 1; d * d <= i; d++) { if(i % d == 0) { dp[i] = min(dp[i], dp[d] + C + V * (i / d - 1)); dp[i] = min(dp[i], dp[i/d] + C + V * (d - 1)); } } } ll ans = dp[N]; FOR(i, N, 2 * N) ans = min(ans, dp[i]); cout << ans << endl; return 0; }
No.556 仁義なきサルたち
Union-Findを使う。子分の数を保存しておく。
xとyが喧嘩したらxとyを同じグループにする。この時子分の数が多い方を親とする。 子分の数が同じ時はx<yならxを親にする。x>yならyを親にする。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; // union - find tree !!!!!!!!!!!!!!!!!!!!!!!!! vector<int> par; //oya vector<int> rnk; //子分の数 // n要素で初期化 void init(int n){ par.resize(n);rnk.resize(n); FOR(i, 0, n){par[i] = i;rnk[i] = 1;} } //木の根を求める int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } //xとyの属する集合を併合 void unite(int x, int y){ x = find(x);y = find(y); if(x == y) return; if(rnk[x] < rnk[y]) swap(x, y); if(rnk[x] == rnk[y] && x > y) swap(x, y); par[y] = x; rnk[x] += rnk[y]; rnk[y] = 0; return; } int main() { int N, M; cin >> N >> M; init(N+1); FOR(i,0,M) { int a, b; cin >> a >> b; unite(a, b); } FOR(i,1,N+1) { cout << find(i) << endl; } return 0; }
No.557 点対称
それぞれの桁に何通りの数字がありえるのか考える。
そして全てかける。
ただし、最大でくらいの計算をする必要が出てくるのでTLEに注意。
高速に(O(log n))累乗を計算するテクニックを使う必要がある。
例えば、aの8乗を計算する時はaを8回かけるよりa->a×a->(a2)×(a2)->(a4)×(a4)というように掛け算した結果を使用した方が早い。a ×= aを3回計算すれば終わる。 100乗の場合100 = 64(26) + 32(25) + 4(22)であり、a ×= aを5回計算すれば終わる。100を2進数にした時に右のbitから調べていき1になっている時にaを足せば良い。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const int mod = 1e9 + 7; int main() { ll N; cin >> N; if(N == 1) { cout << 2 << endl; return 0; } ll ans; if(N % 2 == 1) ans = 3; else ans = 1; // 5^(N/2-1)を高速に計算 ll j = 0; ll fi = 5; ll p = N / 2 - 1; while((1LL<<j) <= p) { if((p>>j)&1) { ans *= fi; ans %= mod; } fi *= fi; fi %= mod; j++; } ans *= 4; cout << ans % mod << endl; }