AtCoder Beginner Contest 145 （ABC145）

4完1WAで23:41
前回事故った分は回復したのでまあよし？
E本番中に通したかったね
f:id:tkm-kyudo:20191117022524p:plain

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

$N = 8$ を見た瞬間脳死next_permutationをしました
next_permutation使わなくても順列全列挙出来るので、もし興味あればやってみるといいかも
$N^2$ の解法何も考えなかったけど解説なるほどなあとなった
提出コード

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

こういう系解くと大体水パフォ出る気がする
考え方は最短経路の数え上げと同じでまず $(X + Y) \% 3 != 0$ ならできない
$(i+1, j+2)$ の回数を $x$ , $(i+2, j+1)$ の回数を $y$ とすると $_{x+y}C_x$ が答え
xとyは以下の連立方程式を解くと、 $x = \frac{2Y - X}{3}，y = \frac{2X - Y}{3}$ が得られる
$x + 2y = X$
$2x + y = 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するだけだとだめで、ちょっと工夫が必要
$T - 1$ に最後のものを取ると考えて良いので、最後に取るのはそれ以前に取ったもの以外で $A_i$ が一番大きいものを取ればいい
ソートをすると $A_i$ で一番大きいものを最後に取ることになるので、後は普通に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は $T-1$ に最後の料理取ればいいなとか考えてたからACまでたどり着きたかったね
前回事故った分戻ったので次でまた水近くまで戻せるといいなー

接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。