AtCoder Beginner Contest 044

[TakefumiYamamura]

http://abc044.contest.atcoder.jp/

[TakefumiYamamura]

C - 高橋君とカード / Tak and Cards

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 300 点

問題文

高橋君は、N 枚のカードを持っています。 i (1≤i≤N) 番目のカードには、整数 xi が書かれています。 高橋君は、これらのカードの中から 1 枚以上を選び、 選んだカードに書かれた整数の平均をちょうど A にしたいと考えています。 そのようなカードの選び方が何通りあるか求めてください。

制約

1≤N≤50 1≤A≤50 1≤xi≤50 N, A, xi はいずれも整数である 部分点 1≤N≤16 を満たすデータセットに正解した場合は、200 点が与えられる。

まずbit操作を使った全列挙、当然nが大きくなると解けず、部分点解答 計算のオーダー O(n*(2^n) )

#include <iostream>
#define ll long long
using namespace std;

int main(){
    ll n, a;
    ll x[51];
    cin >> n >> a;
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i];
    }
    ll ans = 0;
    for (int i = 0; i < (1 << n) ; ++i)
    {
        ll tmp = 0;
        ll tmp_count = 0;
        for (int j = 0; j < n; ++j)
        {
            if(i >> j & 1){
                tmp += x[j];
                tmp_count++; 
            }
        }
        if(tmp_count != 0 && tmp == tmp_count * a){
            ans++;
        }
    }
    cout << ans << endl;
}

dpでとく、O(n_n_n * a) 添字ミスったせいで手こずる

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main(){
    ll n, a;
    ll x[51];
    // ll dp[55][55][2505];
    // dp[i][j][k] 
    // i番目のカードの中からj個選んだ際に合計がkになる場合の数
    cin >> n >> a;
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i];
    }
    vector<vector<vector<ll> > > dp;
    dp = vector<vector<vector<ll > > >(n+1, vector<vector<ll > >(n+1, vector<ll >(n*a+10, 0)));  
    dp[0][0][0] = 1;
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= i ; ++j)
        {
            for (int k = 0; k <= n*a ; ++k)
            {
                if (i-1>=0 && j-1 >= 0 && k-x[i-1]>= 0)
                {
                    dp[i][j][k] += dp[i-1][j-1][k-x[i-1]];
                }
                if(i-1 >= 0){
                    dp[i][j][k] += dp[i-1][j][k];
                }
                // cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl; 
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans += dp[n][i][i*a];
    }
    cout << ans << endl;
}

[TakefumiYamamura]

D - 桁和 / Digit Sum

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 500 点

問題文

2 以上の整数 b および 1 以上の整数 n に対し、関数 f(b,n) を次のように定義します。

n<b のとき f(b,n)=n n≥b のとき f(b,n)=f(b, floor(n⁄b))+(n mod b) ここで、floor(n⁄b) は n⁄b を超えない最大の整数を、 n mod b は n を b で割った余りを表します。

直感的に言えば、f(b,n) は、n を b 進表記したときの各桁の和となります。 例えば、

f(10, 87654)=8+7+6+5+4=30 f(100, 87654)=8+76+54=138 などとなります。

整数 n と s が与えられます。 f(b,n)=s を満たすような 2 以上の整数 b が存在するか判定してください。 さらに、そのような b が存在するならば、その最小値を求めてください。

制約

1≤n≤1011 1≤s≤1011 n, s はいずれも整数である

note

I deeply feel that math is very important in the field of the computer science.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long
using namespace std;

ll compute(ll b, ll n){
    if(n<b){
        return n;
    }else{
        return  compute(b, n/b) + n%b;
    }
}

int main(){
    ll n, s;
    ll b = 2;
    ll ans = -1;
    cin >> n;
    cin >> s;
    if(n == s){
        cout << n+1 << endl;
        return 0;
    }
    while(b*b <= n){
        if(compute(b, n) == s){
            cout << b << endl;
            return 0;
        } 
        b++;
    }
    // そうじゃないときは|n-s|の最大公約数で|n-s|をわったものにプラス１がB
    ll ab = abs(n-s);
    ll sq = sqrt(ab);

    bool flag = false;
    b = 1000000000005;
    for (ll p = 1; p < sqrt(n); ++p)
    {
        if(ab % p == 0 ){
            if(ab/p + 1 >= sqrt(n) ) {
                if(compute(ab/p+1, n) == s){
                    b = min(ab/p + 1, b);
                    flag = true;
                }
            }
        }
    }
    if(flag){
        cout << b << endl;
        return 0;
    }

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