K2PC Easy

結果

下らないミスして3完でしたが, しなくても3完です.

A - ハンバーガー(Hamburger)

方針

問題文通りにやれば通る

コード

int main()
{
    int n;
    int a, b, c;
 
    cin >> a >> b >> c;
    cin >> n;
 
    int _a = n, _b = 2 * n, _c = 3 * n;
 
    cout << (_a - a <= 0 ? 0 : _a - a) << ' ' << (_b - b <= 0 ? 0 : _b - b) << ' ' << (_c - c <= 0 ? 0 : _c - c) << endl;
}

B - ビットマニア(BITMANIA)

方針

縦連耐性と各指の最大連続ノートを大きい順から比べていく.

コード

int limit[7];
 
int main()
{
    char map[100][7];
 
    int n;
    cin >> n;
 
    int finger[10];
 
    for(int i = 0; i < 10; i++)
        cin >> finger[i];
 
    sort(finger, finger + 10, greater<int>());
 
    for(int i = 0; i < n; i++)
        cin >> map[i];
     
    for(int i = 0; i < 7; i++)
        for(int j = 0; j < n; j++)
            if(map[j][i] == 'X')
            {
                int count = 0;
 
                while(map[j][i] == 'X')
                {
                    count++;
                    j++;
                }
 
                limit[i] = max(limit[i], count);
            }
    
    sort(limit, limit + 7, greater<int>());
 
    for(int i = 0; i < 7; i++)
        if(limit[i] > finger[i])
        {
            cout << "NO" << endl;
            return 0;
        }
    
    cout << "YES" << endl;
}

C - 紅茶(Tea)

方針

高専生なら知ってますね.ちょっと手を加えるだけです.

m+n=2   | 1段目 : (1, 1)
m+n=3   | 2段目 : (2, 1) (1, 2)
m+n=4   | 3段目 : (3, 1) (2, 2) (1, 3)
m+n=5   | 4段目 : (4, 1) (3, 2) (2, 3) (1, 4)
...
m+n=x+1 | x段目
...

こんな感じで見ると関係性が分かるので, ここから(m, n)が何番目にあるかは

で求めれます.

コード

int x;
 
int f(int n)
{
    int i, j, c = 1;
    for(i = 1, j = 2; i < n; i += j, j++)
        c++;
 
    x = i - (j - 1);
 
    return c;
}
 
int main()
{
    int n, m, xm, k, xi, yi, xn, xj, yj;
 
    cin >> m >> n;
 
    xm = f(m);
    k = m - x;
    xi = xm + 1 - k;
    yi = k;
 
    xn = f(n);
    k = n - x;
    xj = xn + 1 - k;
    yj = k;
 
    m = xj + xi;
    n = yj + yi;
 
    cout << (m + n - 2) * (m + n - 1) / 2 + n << endl;
}

D - 虫歯(Cavity)

方針

カンニングしました.

セグメント木のイメージで考えればよい.
最大の値は
今いるノードをnとすると親のノードはであることを用いる.
徐々に高さを上げていき, 親のノードが治療された神経であれば, nより下の治療された領域はその治療された神経のノード以下の領域に含まれるので, foundの条件分岐で飛ばしています.
親ノードから治療された神経を探すのには二分探索を用いる.

コード

typedef long long ll;
 
vector<vector<ll> > b;
 
ll solve(const ll k)
{
    ll ans = (1LL << k + 1) - 1;
    for(int i = 0; i <= k; i++)
    {
        for(int j = 0; j < b[i].size(); j++)
        {
            bool found = false;
            ll x = b[i][j];
 
            for(int h = i - 1; h >= 0; h--)
            {
                x = (x + 1) / 2;
                if(binary_search(b[h].begin(), b[h].end(), x))
                {
                    found = true;
                    break;
                }
            }
 
            if(!found)
                ans -= (1LL << (k - i + 1)) - 1;
        }
    }
    return ans;
}
 
int main()
{
    ll k, n;
    cin >> k >> n;
    b.resize(k + 1);
 
    for(int i = 0; i < n; i++)
    {
        ll p, q;
        cin >> p >> q;
        b[p].push_back(q);
    }
 
    for(int i = 0; i <= k; i++)
        sort(b[i].begin(), b[i].end());
 
    cout << solve(k) << endl;
}

E - お気に入りの数2(Favorite Number2)

見ていない.