Codeforces Round#574(Div.2)A,B,C,D 1,D 2題解

A. Drinks Choosing
最初は題意に引っかかって、最初はいくら買うかと思っていたが、後に買ったものがどれだけの人に飲めるかを発見した.

#include
#define int long long
using namespace std;
const int maxn = 1010;
int vis[maxn];
signed main()
{
    ios::sync_with_stdio(false);
    int n,k,tmp;
    cin >> n >> k;
    for(int i = 1;i <= n; ++i)
    {
        cin >> tmp;
        vis[tmp]++;
    }
    tmp = 0;
    for(int i = 1;i <= k; ++i)
        tmp += vis[i] / 2;
    cout << (n+1)/2-tmp+tmp*2 << endl;
    return 0;
}

B. Sport Mafia
入れた個数が累加されているので、砂糖があるときは先に入れて食べるのと変わらないので、法則を見つければいいのです

#include
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    int n,k,sum = 0,i;
    cin >> n >> k;
    for(i = 1;sum - (n - i + 1) < k; ++i)
        sum += i;
    cout << n - i + 1 << endl;
    return 0;
}

C. Basketball Exercise
左から右の各列の3つの場合、1行目の人、2行目の人、1行目の2行目の人は取りません.

#include
#define int long long
using namespace std;
const int maxn = 1e5+10;
int a[maxn],b[maxn],dp[maxn][5];
signed main()
{
    ios::sync_with_stdio(false);
    int n,k,sum = 0,i;
    cin >> n;
    for(int i = 1;i <= n; i++)
        cin >> a[i];
    for(int i = 1;i <= n; i++)
        cin >> b[i];
    for(int i = 1;i <= n; i++)
    {
        dp[i][0] = max(max(dp[i-1][0],dp[i-1][1]),dp[i-1][2]);
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + a[i];
        dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + b[i];
    }
    cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
    return 0;
}

D1. Submarine in the Rybinsk Sea (easy edition)
各数字の各桁の寄与を考慮し,加算して和を求める

#include
#define int long long
using namespace std;
const int mod = 998244353;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,mp,ans = 0;
    cin >> n;
    for(int i = 0;i < n; i++)
    {
        cin >> mp;
        int xx = 0,pos = 1;
        while(mp)
        {
            xx = (xx + (((mp % 10) * pos) % mod) * 11) % mod;
            pos *= 1ll*100;
            mp /= 10;
        }
        xx = (xx * n) % mod;
        ans = (ans + xx) % mod;
    }
    cout << ans << endl;
    return 0;
}

D2. Submarine in the Rybinsk Sea (hard edition)
問題の意味は前の問題と同じですが、前の問題で与えられた数字はすべて等長で、貢献値は計算しやすいので、この問題は等長でないと少し問題があります.

#include
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e5+10;
int cnt[15],x[maxn][15],sum;
void Cal(int tmp,int base,int y)
{
    while(tmp)
    {
        sum += base * (tmp % 10) % mod;
        sum %= mod;
        if(y > 0)
            base *= 100*1ll;
        else
            base *= 10*1ll;
        base %= mod;
        tmp /= 10;
        y--;
    }
}
signed main()
{
    //freopen("in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,xx;
    cin >> n;
    for(int i = 1;i <= n; i++)
    {
        cin >> xx;
        int tmp = 0,y = xx;
        while(y)
        {
            tmp++;
            y /= 10;
        }
        x[cnt[tmp]++][tmp] = xx;
    }
    int ans = 0;
    for(int i = 1;i <= 10; i++)
    {
        for(int j = 1;j <= 10; j++)
        {
            for(int k = 0;k < cnt[i]; k++)
            {
                if(cnt[j] == 0)
                    continue;
                sum = 0;
                Cal(x[k][i],1,j);
                Cal(x[k][i],10,j-1);
                sum  = (sum * cnt[j]) % mod;
                ans = (ans + sum) % mod;
            }
        }
    }
    cout << ans << endl;
    return 0;
}