競プロ記録

問題を解いた際に自分の復習用として使ってます

DMM FX DEMO 2日目

競プロに全く関係ありません。


昨日に引き続き今日も上昇傾向で、一時1ドル110円まであがりました。
そのため本日も容易に利益を出すことができたのでよかったです👍

そのうち大損しそうだから気をつけなければ、、、
一体どこまで上がるのだろう?確実に110円までは上がると考えていたけどこっからがわからない
これからアップルの発表もあるしもっと上がるのかな?
112円ぐらいまで上がってもおかしくはないはず

結果

本日の利益 +142,850円(+46750)
累計 +515,640円
f:id:takuma2460-0131:20170913003540p:plain

DMM FX DEMO

※競プロに全く関係ありません。

今日からDMM FX デモでキャンペーンが始まりました。
それは5,000,000円スタートで3ヶ月間でいくらに増やせるかというのを競います。

夏休みからデモで FXを始めました。
でも暇つぶしにやっているだけで現金は投入する予定はないですね、、それに未成年ですしね笑

なんか試しに去年のランキングを見てみたのですが、入賞してる人の中で最下位が +200,000円でした笑
それだけ利益を出すこと自体が難しいってことですね。

とりあえず今日の成果。

先週は建国記念日北朝鮮がミサイルを打つとか打たないとかでドル安、しかし9日北朝鮮がミサイルを打ちませんでした。
そのため今日はずっとドル高だったためチャートを予想することが容易でした。

気をつけないといけないのは、最近北朝鮮のミサイル開発が活発なため不意に打たれると大損してしまうのでなるべく短期間での売買で稼いでいきたいと考えてます。

今日の結果

f:id:takuma2460-0131:20170912010955p:plain
fx0911

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か104までなのでメモリが足りません。
なので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段目までの方法の総数を出力する問題です。 しかし、1つ条件があり、連続して同じ段数を登ることはできません。

解説

基本的な解法の方針は動的計画法です。
連続して、同じ段数登ることができないので何段登って到達したかを保持するために配列を3つ用意します。
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が106であるためメモリが足りません。
そのため前三段分を配列に保持してそれらを用いて計算させるようにすれば答えを求めることができます。

コード

#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;
}