AtCoder Beginner Contest 085

起きたら 21:25 で絶望した
コンテストと無関係な要因で順位が暴落するのは本当に悲しい

A - Already 2018

S の 4 文字目に '8' を代入する

int problemA()
{
    string S;
    cin >> S;
 
    S[3] = '8';
    cout << S << endl;


    return 0;
}

B - Kagami Mochi

異なる値を持つ要素の数だけ段数を重ねることができるので，set にぶちこんで要素数を出力する

int problemB()
{
    int N, d;
    cin >> N;
 
    set<int> st;
 
    for (int i = 0; i < N; i++) {
        cin >> d;
        st.insert(d);
    }
 
    cout << st.size() << endl;

    return 0;
}

C - Otoshidama

10000 円札 a 枚，5000 円札 b 枚，1000 円札 c 枚とすれば，

10000 a + 5000 b + 1000 c = Y
a + b + c = N

より

9 a + 4 b = Y / 1000 - N
c = N - a - b

c が負にならないことに注意してループを回す

int problemC()
{
    int N, Y;
 
    cin >> N >> Y;
    Y /= 1000;
 
    for (int a = 0; a * 9 <= Y - N; a++) {
        for (int b = 0; a + b <= N && a * 9 + b * 4 <= Y - N; b++) {
            if (9 * a + 4 * b == Y - N) {
                int c = N - a - b;
                cout << a << " " << b << " " << c << endl;
                return 0;
            }
        }
    }

    cout << -1 << " " << -1 << " " << -1 << endl;
    return 0;
}

D - Katana Thrower

投げ攻撃力が高い順に i 個刀を投げた時の攻撃力の和を vec[i] に格納

最も振り攻撃力が高い刀の攻撃力を D としたとき，x_i = ((H - vec[i]) + D - 1) / D が刀を振るべき回数となる．

あとは i = 1 ~ N について min(x_i + i) を求めればいい

HP が負になる場合を考慮せず 1WA 出してしまったので，ア

typedef long long ll;

int main()
{
    ll N, H;
    vector<ll> vec;
    vec.push_back(INT64_MAX); // 1-based にするため
    cin >> N >> H;
 
    ll maxa = 0;
    for (int i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        vec.push_back(b);
 
        maxa = max(maxa, a);
    }
 
    sort(all(vec), greater<ll>());
    // i 個投げるといくつダメージを与えられるか？
    for (int i = 1; i < vec.size() - 1; i++) {
        vec[i + 1] += vec[i];
    }
 
    ll ans = INT64_MAX;
    for (int i = 1; i < vec.size(); i++) {
        ll HPrem = max(0LL, H - vec[i]);       // 残りHP
        ll x = (HPrem + maxa - 1) / maxa;      // 攻撃力最大の刀を振るべき回数
        ans = min(ans, i + x);
    }
    cout << ans << endl;
 
    return 0;
}

30 分遅刻で順位が 200 位近く落ちていてかなしい