yukicoder No.129

解説

基本的な解法の方針は動的計画法です。
そしてお金は1000円単位で平等に配るので、n/1000 mod m 円を分配することは容易にわかると思います。
なので k = n/1000 mod m とすると求めるのはm人にk枚を平等に配るので一人あたり1000円になります。よって総数は mCk です。

ここでmCkを動的計画法を用いて求めます。そこで必要となるのがパスカルの三角形です。

パスカルの三角形は聞いたことがあると思うので省略します。動的計画法を用いやすいように左側に寄せて記述すると以下のようになります。

1
1 1
1 2 1
1 3 3 1
1 4 9 4 1
1 5 13 13 5 1
….

よって次の式が成立します。

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

これは比較的簡単に導出できるかと思います。しかしこれですとmか10⁴までなのでメモリが足りません。
なのでi番目の段の値だけを保持して、i+1番目の段の値を計算し、、、を繰り返していけば求めれます。

コード

#include <iostream>
using namespace std;

const int mod = 1e9;
int main(void){
    long long n,m;
    cin >> n >> m;
    long long k = (n/1000)%m;
    long long before[10003], after[10003];
    before[0] = 1;
    if(k != 0){
        for(int i=1; i<=m; i++){
            for(int j=1; j<=i; j++){
                after[j] = (before[j-1]+before[j])%mod;
            }
            before[0] = 1;
            for(int j=1; j<=i; j++){
                before[j] = after[j];
            }
        }
    }
    cout << (before[k]%mod) << endl;
    return 0;
}

yukicoder No390

解説

基本的な解法の方針は動的計画法です dp[i] := 値iの要素が右端になる時の長さの最大値 とします。そうすると以下のような漸化式を立てることができます。 dp[i] = dp[y]+1 (yはiの約数) 基本的にはこれだけなのであとは値iの約数を列挙しなければいけません. √xの値までを調べ、x%i== 0の時、iは約数であり、n/iも約数になります。

コード

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main(void){
    int n, a[100005];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a, a+n);
    int dp[1000006];
    fill(dp, dp+1000006, 0);
    int m = 1;
    dp[a[0]] = 1;
    for(int i=1; i<n; i++){
        dp[a[i]] = 1;
        if(a[i] != 1){
            vector<int> res = divisor(a[i]);
            for(int j=0; j<res.size(); j++){
                dp[a[i]] = max(dp[a[i]], dp[res[j]]+1);
                m = max(m, dp[a[i]]);
            }
        }
    }
    cout << m << endl;


    return 0;
}

yukicoder No.458

解説

基本的な解答の方針は動的計画法です。

小さい素数から順番に見ていって、i番目までの素数で構成される数に対してi+1番目の新たな素数を加えれば、その和の数は異なる素数で表すことができることになります。 そこで素数を加えた回数を保持するために、i番目までの素数で構成される数の個数に1を加えたもの(i+1番目の素数を加えるので)と元の値とを比較すれば素数の数の最大値を保持できるようになります。

ここで i+1番目の素数にi番目までの素数で構成される数を加えるのですが、n以下で小さい方から加えていってしまうと、同じ素数を複数回加えることになってしまいます。 例えば素数は 2, 3, 5, 7, …. ですが 3(i番目までの素数で構成される数)に対して5を加えると8となり, 5は個数2(2+3)であり、8の個数は3になります。そして8の個数は3となり、再び5を加えることになるため、同じ素数を複数回カウントしてしまい適切ではありません。

しかしn以下で大きい方から加えていくと次加える数より必ず大きくなるので同じ素数を複数回加えることはありません。

コード

#include <iostream>
using namespace std;

int prime[20001];
bool is_prime[20001];
int p = 0;
void eratos(int n){
    for(int i=0; i<=n; i++){
        is_prime[i] = true;
    }
    is_prime[0] = is_prime[1] = false;
    for(int i=2; i<=n; i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= n; j += i){
                is_prime[j] = false;
            }
        }
    }
}

int main(void){
    int n;
    cin >> n;
    eratos(20000);
    int dp[20000];
    fill(dp, dp+20000, -1);
    dp[0] = 0;
    for(int i=0; i<p; i++){
        for(int j=n; j >= 0; j--){
            if(dp[j] != -1 && prime[i] + j <= n){
                dp[prime[i]+j] = max(dp[prime[i]+j], dp[j]+1);
            }
        }
    }
    cout << dp[n] << endl;

    return 0;
}

yukicoder No.505

解説

基本的な解放の方針は動的計画法です。 最小値と最大値を保持して計算していけば、答えを求めることができます。 また除算もする必要があるので注意です。 例えば-9 3の場合 -9/3が最大の答えになります。

コード

#include <iostream>
using namespace std;
int main(void){
    int n, a[100];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    long long sum, ma, mi;
    if(a[1] != 0){
        ma = max(max(max(a[0]*a[1],a[0]+a[1]), a[0]-a[1]),a[0]/a[1]);
        mi = min(min(min(a[0]*a[1],a[0]+a[1]), a[0]-a[1]), a[0]/a[1]);
    }else{
        ma = max(max(a[0]*a[1],a[0]+a[1]), a[0]-a[1]);
        mi = min(min(a[0]*a[1],a[0]+a[1]), a[0]-a[1]);
    }
    long long tmp_ma, tmp_mi;
    for(int i=2; i<n; i++){
        if(a[i] != 0){
            tmp_ma = max(max(max(max(ma*a[i],ma+a[i]), ma-a[i]),ma/a[i]), max(max(max(mi*a[i],mi+a[i]), mi-a[i]),mi/a[i]));
            tmp_mi = min(min(min(min(ma*a[i],ma+a[i]), ma-a[i]),ma/a[i]), min(min(min(mi*a[i],mi+a[i]), mi-a[i]),mi/a[i]));
        }else{
            tmp_ma = max(max(max(ma*a[i],ma+a[i]), ma-a[i]), max(max(mi*a[i],mi+a[i]), mi-a[i]));
            tmp_mi = min(min(min(ma*a[i],ma+a[i]), ma-a[i]), min(min(mi*a[i],mi+a[i]), mi-a[i]));
        }
        ma = tmp_ma;
        mi = tmp_mi;
    }
    cout << ma << endl;
    return 0;
}

yukicoder No.533

問題文

1段, 2段, 3段登ることができる人がn段の階段を登っていく場合、n段目までの方法の総数を出力する問題です。 しかし、１つ条件があり、連続して同じ段数を登ることはできません。

解説

基本的な解法の方針は動的計画法です。
連続して、同じ段数登ることができないので何段登って到達したかを保持するために配列を３つ用意します。
dp[i][1] := i段目に1段登って到達する場合の数
dp[i][2] := i段目に2段登って到達する場合の数
dp[i][3] := i段目に3段登って到達する場合の数

ここで、例えば1段のぼって到達した場合にはその前は2段か3段でなければなりせん.よって以下の漸化式を立てることができます。

dp[i][1] = dp[i-1][2] + dp[i-1][3]
dp[i][2] = dp[i-2][1] + dp[i-2][3];
dp[i][3] = dp[i-3][1] + dp[i-3][2];

これをループを回して計算させればdp[n][1]+dp[n][2]+dp[n][3]が答えになります。

しかし、これではnが10⁶であるためメモリが足りません。
そのため前三段分を配列に保持してそれらを用いて計算させるようにすれば答えを求めることができます。

コード

#include <iostream>
#include <queue>
using namespace std;
const int mod = 1e9+7;
int main(void){
    int n;
    long long dp[100000][4];
    queue<long long> memo[4];
    cin >> n;
    if(n==1){
        cout << "1" << endl;
        return 0;
    }
    if(n == 2){
        cout << "1" << endl;
        return 0;
    }
    memo[1].push(1);
    memo[2].push(0);
    memo[3].push(0);

    memo[1].push(0);
    memo[2].push(1);
    memo[3].push(0);

    memo[1].push(1);
    memo[2].push(1);
    memo[3].push(1);

    long long m[5][4];

    for(int i=4; i<=n; i++){
        m[1][1] = memo[1].front();
        m[1][2] = memo[2].front();
        m[1][3] = memo[3].front();

        memo[1].pop();
        memo[2].pop();
        memo[3].pop();

        m[2][1] = memo[1].front();
        m[2][2] = memo[2].front();
        m[2][3] = memo[3].front();
        
        memo[1].pop();
        memo[2].pop();
        memo[3].pop();

        m[3][1] = memo[1].front();
        m[3][2] = memo[2].front();
        m[3][3] = memo[3].front();
        
        memo[1].pop();
        memo[2].pop();
        memo[3].pop();

        m[4][3] = (m[1][2] + m[1][1])%mod;
        m[4][2] = (m[2][1] + m[2][3])%mod;
        m[4][1] = (m[3][2] + m[3][3])%mod;

        memo[1].push(m[2][1]);
        memo[2].push(m[2][2]);
        memo[3].push(m[2][3]);

        memo[1].push(m[3][1]);
        memo[2].push(m[3][2]);
        memo[3].push(m[3][3]);

        memo[1].push(m[4][1]);
        memo[2].push(m[4][2]);
        memo[3].push(m[4][3]);
        
    }
    memo[1].pop();
    memo[2].pop();
    memo[3].pop();

    memo[1].pop();
    memo[2].pop();
    memo[3].pop();

    cout << (memo[1].front()+memo[2].front()+memo[3].front())%mod << endl;
    return 0;
}

Educational Codeforces Round 27

A問題　Chess Tourney

問題文

2*n個の数字が与えられ、それをn個ずつの2組に分割します。そして2組からそれぞれ一つずつ取り出しn個のペアを作ります。 ここで、１つのペアの中で数字が大きい方が勝ちとします。そしてn個のペアで全て勝つような組が作れればYESを、作れなければNOを出力する.

解説

数字をソートして、真ん中の2つの数が等しくなっていないかを判定すれば良いだけです。

コード

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
    int n, r[1001];
    cin >> n;
    for(int i=0; i<2*n; i++){
        cin >> r[i];
    }
    sort(r, r+n);
    if(r[n-1] == r[n]){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
    return 0;
}

Chokudai Speed Run G問題

Chokudai Speed Run001 G問題解説

問題

数列 aが与えられ a を連結させた整数を、 1,000,000,007 で割った余りを求めなさい。

サンプル

Input

7
7 6 5 4 3 2 1

Output

7654321

解説

全てを加えて剰余をとるという方針はlong long では所持できないので不可能です そこで剰余の性質の以下2つを使います。
(x*y)%MOD = ( (x%MOD) * (y%MOD) ) % MOD
(x+y)%MOD = ( (x%MOD) + (y%MOD) ) % MOD

この二つの性質を使うことによって桁を一つづつ見ていくことによって連結した数列の剰余を正しく求めることができます。

以下コード

#include <iostream>
using namespace std;

#define MOD 1000000007

int main(void){
    int n;
    string s;
    cin >> n;
    for(int i=0; i<n; i++){
        string tmp;
        cin >> tmp;
        s += tmp;
    }
    long long ans = 0;
    for(int i=0; i<s.length(); i++){
        ans = ans * 10 + (s[i]-'0');
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}