接着剤の精進日記

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

AtCoder Beginner Contest 144 (ABC144)

f:id:tkm-kyudo:20191028111255p:plain
なんですかこれは笑
今回紙とペン使えない環境でコンテストに出ましたが、見事にお絵かきが必要な問題がDに出て無事爆死
慣れない環境で出るもんじゃないね()

A - 9x9

A<=9, B<=9確認するだけですね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if(a <= 9 && b <= 9) cout << a * b << endl;
    else cout << -1 << endl;
}

B - 81

制約が小さいときは全探索!(素振り)
[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i*j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C - Walk on Multiplication Table

これちょっと難しいね
約数を全列挙して、組み合わせを全探索してその最小値でやった
よく考えると{\mathcal{O}(\sqrt{N})}全探索で良かったね
提出コード

vector<ll> divisor(ll n){
    vector<ll> res;
    for(ll i=1; i*i <= n; i++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    auto res = divisor(n);
    int s = (int)res.size();
    ll ans = LINF;
    REP(i,s){
        REP(j,s){
            if(res[i]*res[j] == n){
                ll tmp = res[i] - 1 + res[j] -1;
                chmin(ans, tmp);
            }
        }
    }
    cout << ans << endl;
}

D - Water Bottle

なんですかこれは笑
角度を求めたい→辺の長さはいっぱいわかってる→逆三角関数を使うと辺から角度が求められる
以下の記事がとてもわかりやすいので残りは省略
本番中紙で考察できなかったので無理でした…紙で考察したら解けてたかなあ?怪しい
math.nakaken88.com

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double a, b, x, theta;
    cin >> a >> b >> x;
    double V = a*a*b;
    if(x >= V / 2) theta = atan(2 * (a*a*b - x) / (a * a * a));
    else theta = atan((a*b*b) / (2*x));
    theta *= 180 / PI;
    printf("%.12lf\n", theta);
}

E - Gluttony

本番中D解けない→Eちょっと見る→問題文がにぶほうしてと言っている
→貪欲パートが脳内考察でうまくいくかわからなかった→†誤 読 し て た†
寝て起きたら普通に解けました…
証明はeditorialに書いてあるのでそちらに任せます
Aを昇順、Fを降順にしてペアを作り、最大値を達成できるかどうかでにぶほうを使う
提出コード

ll N, K;
vector<ll> A;
vector<ll> F;

bool check(ll m){
    ll cnt = 0;

    REP(i,N){
        if(A[i] * F[i] <= m) continue;
        else{
            cnt += A[i] - (m / F[i]);
        }
    }
    return (cnt <= K);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    REP(i,N){
        ll a;
        cin >> a;
        A.push_back(a);
    }
    REP(i,N){
        ll a;
        cin >> a;
        F.push_back(a);
    }
    sort(A.begin(), A.end());
    sort(F.rbegin(), F.rend());

    ll l = -1, r = 2*LINF;
    while(r - l > 1){
        ll m = (l + r) / 2;
        if(check(m))  r = m;
        else l = m;
    }
    cout << r << endl;
}

おわりに

普段と違う環境でコンテスト出るのはやめようね!
せめて紙とペンはある状況のほうがパフォでます(それはそう)
ところで日経コンも出るとしたら今回と同じ環境になるのですが、出るの控えようかな笑