ABC145 解説

27分遅刻の42分全完でした

A - Circle

半径 の円の面積は、半径 の円の面積の何倍ですか？

円の面積は であることを思い出すと 倍である。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int r;
    cin >> r;
    cout << r * r << endl;
}

B - Echo

文字列 は、ある文字列を2回繰り返したものですか？

が2で割れないなら No、2で割れるなら文字列比較をする。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n >> s;
    if(n & 1){
        puts("No");
        return 0;
    }
    n /= 2;
    puts(s.substr(0, n) == s.substr(n, n) ? "Yes" : "No");
}

C - Average Length

ハミルトン路の長さの平均はいくつですか？

ハミルトン路の長さの合計をとって で割る。

なので、 が間に合う。
ある辺を使う回数は 回なので でも解ける。

O(N!N) 解

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

double dist(pii a, pii b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main(){
    int n;
    cin >> n;
    vector<pii> a(n);
    for(auto& i : a) cin >> i.first >> i.second;
    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);
    double ans = 0;
    do{
        for(int i = 0; i < n - 1; i++) ans += dist(a[perm[i]], a[perm[i + 1]]);
    }while(next_permutation(perm.begin(), perm.end())); // 順列全探索はこれが便利
    for(int i = 1; i <= n; i++) ans /= i;
    cout << fixed << setprecision(20) << ans << endl; // 誤差に注意
}

O(N²) 解

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

double dist(pii a, pii b){
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main(){
    int n;
    cin >> n;
    vector<pii> a(n);
    for(auto& i : a) cin >> i.first >> i.second;
    double ans = 0;
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) ans += dist(a[i], a[j]);
    ans *= 2;
    ans /= n;
    cout << fixed << setprecision(20) << ans << endl;
}

D - Knight

にある駒を または に動かして に移動させる時の通り数はいくつですか？

どちらの操作も 方向に 動いているから、 (X + Y) % 3 != 0 なら 0
操作回数を とすると、
どちらの操作も , 方向ともに 以上動いているから、次のように読み換える。

にある駒を または に動かして に移動させる時の通り数はいくつですか？ これは有名問題で、 に動くのが 回、 に動くのが 回の並び替えになるから、 通り。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
ll modpow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1){
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return ans;
}

int main(){
    ll x, y;
    cin >> x >> y;
    if((x + y) % 3 || x > y * 2 || y > x * 2){
        puts("0");
        return 0;
    }
    ll n = (x + y) / 3;
    x -= n;
    y -= n;
    vector<ll> fac(x + y + 1), inv(x + y + 1); // fac[i] = i! mod 1000000007, inv[i] = 1 / i! mod 1000000007
    fac[0] = 1;
    for(ll i = 1; i <= x + y; i++) fac[i] = fac[i - 1] * i % MOD;
    inv.back() = modpow(fac.back(), MOD - 2);
    for(ll i = x + y; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    cout << fac[x + y] * inv[x] % MOD * inv[y] % MOD << endl;
}

E - All-you-can-eat

見た感じナップサック問題なのでDPを疑う。
最後時間ギリギリに注文できるのが厄介。 でも くらいじゃないと間に合わない。
→ 最後に注文する料理をDPの状態に持てばいい。
あとはナップサック問題と同じ

DPの持ち方

料理 まで見たときに 分までに食べ終わるときの美味しさの合計の最大値 料理 まで見たときに 分までに食べ終わり、その後料理を1つ注文するときの美味しさの合計の最大値
このままだとメモリをかなり喰うが、遷移の順番を気をつければ、 に圧縮することができる。

DPの遷移

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }

int main(){
    ll n, t;
    cin >> n >> t;
    ll dp[n + 1][t][2];
    memset(dp, 0x00, sizeof(dp));
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        for(ll j = 0; j < t; j++){
            dp[i + 1][j][0] = dp[i][j][0];
            dp[i + 1][j][1] = max(dp[i][j][1], dp[i][j][0] + b);
            if(j >= a) chmax(dp[i + 1][j][0], dp[i][j - a][0] + b);
            if(j >= a) chmax(dp[i + 1][j][1], dp[i][j - a][1] + b);
        }
    }
    cout << max(dp[n][t - 1][0], dp[n][t - 1][1]) << endl;
}

圧縮版

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }

int main(){
    ll n, t;
    cin >> n >> t;
    vector<vector<ll>> dp(t, vector<ll>(2));
    for(ll i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        for(ll i = t; i --> a; ) chmax(dp[i][1], dp[i - a][1] + b);
        for(ll i = 0; i < t; i++) chmax(dp[i][1], dp[i][0] + b);
        for(ll i = t; i --> a; ) chmax(dp[i][0], dp[i - a][0] + b);
    }
    cout << max(dp[t - 1][0], dp[t - 1][1]) << endl;
}

F - Laminate

項の数列 のうち 項以下を変えた時の の最小値を求めよ。

谷を埋めたり、山を削ったりすると小さくなる。
項以下がやっかいだけど、部分問題に落とせそうなのでDPを疑う。

DPの持ち方

数列を まで見たときに 項を変えて、最後の項が のときの最小値

DPの遷移

しかし、このままでは でTLEになってしまう。
かかっている上の遷移の無駄について考えると、ある項を変えるときは、前の項と同じにするのがよいとわかる。(どんな項が続いても山も谷もできないため)

の値が不連続であるため、unordered_map を使いたくなるが、 TLEする可能性が高いので座標圧縮する。

サンプルコードは疲れたのでこれで