4完1WAで23:41
前回事故った分は回復したのでまあよし?
E本番中に通したかったね
A - Circle
を出力!
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int r; cin >> r; cout << r * r << endl; }
B - Echo
奇数ならだめで、偶数のときに文字列を半分に分割して一致するかどうか確かめる
substr使うのが一番楽かな?
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; string S; cin >> N >> S; if(N % 2 == 1) cout << "No" << endl; else{ if(S.substr(0,N/2) == S.substr(N/2, N/2)) cout << "Yes" << endl; else cout << "No" << endl; } }
C - Average Length
を見た瞬間脳死next_permutationをしました
next_permutation使わなくても順列全列挙出来るので、もし興味あればやってみるといいかも
の解法何も考えなかったけど解説なるほどなあとなった
提出コード
int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<double> x(N), y(N); REP(i,N) cin >> x[i] >> y[i]; vector<int> a(N); iota(a.begin(), a.end(), 0); double sum = 0.0; do{ for(int i=1;i<N;i++){ sum += sqrt((x[a[i]] - x[a[i-1]])*(x[a[i]] - x[a[i-1]]) + (y[a[i]] - y[a[i-1]]) * (y[a[i]] - y[a[i-1]])); } }while(next_permutation(a.begin(), a.end())); for(int i=1;i<=N;i++) sum /= (double)i; printf("%.12lf\n",sum); }
D - Knight
こういう系解くと大体水パフォ出る気がする
考え方は最短経路の数え上げと同じでまずならできない
の回数を, の回数を とするとが答え
xとyは以下の連立方程式を解くと、が得られる
提出コード
const int MAX = 1110000; long long fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void comb_init() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long comb(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int X, Y; cin >> X >> Y; comb_init(); if((X + Y) % 3 != 0) cout << 0 << endl; else{ int x = (2 * Y - X) / 3; int y = (2 * X - Y) / 3; cout << comb(x+y, x) << endl; } }
E - All-you-can-eat
本番で解けなかったやつ
普通にDPするだけだとだめで、ちょっと工夫が必要
に最後のものを取ると考えて良いので、最後に取るのはそれ以前に取ったもの以外でが一番大きいものを取ればいい
ソートをするとで一番大きいものを最後に取ることになるので、後は普通にDPをすればおっけー
解説の左右からDP頭いいね、任意の1個を除いた結果が欲しい時は思い浮かべられるようにしたい
提出コード
int dp[3030][6060]; int N, T; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> N >> T; vector<pair<int,int>> A(N); REP(i,N){ cin >> A[i].first >> A[i].second; } sort(A.begin(), A.end()); REP(i,N){ for(int j=0;j<3030;j++){ if(j < T) chmax(dp[i+1][j+A[i].first], dp[i][j]+A[i].second); chmax(dp[i+1][j], dp[i][j]); } } int ans = 0; REP(i,N+1) REP(j,6060) chmax(ans, dp[i][j]); cout << ans << endl; }
おわりに
Bでアホ1WA出した以外はまあまあ
Eはに最後の料理取ればいいなとか考えてたからACまでたどり着きたかったね
前回事故った分戻ったので次でまた水近くまで戻せるといいなー