C - 高橋君、24歳 モンモール数・Montmort Number

Quiz

https://atcoder.jp/contests/arc009/tasks/arc009_3

AC Code

https://atcoder.jp/contests/arc009/submissions/6521277

モンモール数を求める

  • シグマの入った一般式は負の符号が出てくるので避け、漸化式からdp的に求めた

大きい値でWAが出たので対処法

  • テストケースとして最大のN, Kを設定して実行するとオーバーフローが見つかった
  • NCKの箇所でNをかけるまえにmodしておく必要があった

用語

  • derangement 撹乱
  • 攪乱順列（完全順列）
  • モンモール数 (Montmort Number)

0-1 ナップサック 個数x容量の表を埋めるVer (N=100, W=10000, よくある形) O(NW)

制約

  • 荷物数N=100
  • バッグの容量の最大値W=10000
  • 買うか買わないか(1 or 0)

その他

解き方

  • その１：dp[i][j]
  • その２：メモ化再帰 rec(i, j)

Quiz

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B

AC code

https://onlinejudge.u-aizu.ac.jp/status/users/peroon/submissions/1/DPL_1_B/judge/3754207/C++14

感想

  • ナップサックはいろいろな亜種があるのでそれぞれソラで書けるようにしたい

code

// i番目以降を見て
// jキャパシティに入る最大の価値
ll dp[101][10001];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, C; // C : capacity
    cin >> N >> C;

    vector<ll> V(N);
    vector<ll> W(N);
    FOR(i, 0, N){
        cin >> V[i]; 
        cin >> W[i];
    }

    for(int i=N-1; i>=0; i--){
        FOR(j, 0, C+1){
            if(W[i]>j){
                // 入らない
                dp[i][j] = dp[i+1][j];
            }
            else{
                ll v0 = dp[i+1][j];
                ll v1 = dp[i+1][j-W[i]] + V[i];
                dp[i][j] = max(v0, v1);
            }
        }
    }
    p(dp[0][C]);
    return 0;
}

bitsetで殴るとは

bitsetの使い方

  • 今までは2進数表示でprintするときしか使っていなかった
  • 以下のような使い方ができる
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    bitset<10> dp;
    dp[0] = 1;
    dp[3] = 1;
    cout << dp << endl;

    dp |= (dp<<1); // 左に1シフトして自身に足す
    cout << dp << endl;

    return 0;
}

結果は

0000001001
0000011011

これにより、以下の問題が解けます。

  • A = [a0, a1, ..., aN]
  • K
  • Aからいくつか選び（全てでもいいし、0でもいい）、Kが作れるか判定せよ

応用問題

関連

  • 個数制限つきナップサック アリ本p64

Visual Studio Codeにbits/stdc++.hを認識させる

環境設定

前提環境

なくてもコンパイルは通る

  • WSLではincludeパスが通っているのであろう、コンパイルは通る
  • しかし、VSC側で
#include<bits/stdc++.h>
  • に波線表示。これのせいで他のインテリセンスも効きづらい

VSC内のc_cpp_properties.jsonに追記

{
    "configurations": [
        {
            "name": "Win32",
            "includePath": [
                "${workspaceFolder}/**",
                "C:/Program Files (x86)/Microsoft Visual Studio/2017/Community/VC/Tools/MSVC/14.16.27023/include/bits/*"
            ],
            "defines": [
                "_DEBUG",
                "UNICODE",
                "_UNICODE"
            ],
            "windowsSdkVersion": "10.0.16299.0",
            "compilerPath": "C:/Program Files (x86)/Microsoft Visual Studio/2017/Community/VC/Tools/MSVC/14.16.27023/bin/Hostx64/x64/cl.exe",
            "cStandard": "c11",
            "cppStandard": "c++17",
            "intelliSenseMode": "msvc-x64"
        }
    ],
    "version": 4
}
  • include/bitsと書いてる箇所が追記したところ

実際に配置

  • そのパスに実際にbitsフォルダを作り、stdc++.hを置く。ファイルは、

stdc++.h · GitHub

結果

インテリセンスが効きやすくなった

追記：より永続的な場所に置く

  • 2021/11/13
  • Visual Studio 2019に移行したのでVisual Studio 2017をアンインストールしたらインテリセンスが効かなくなった。ファイルが無くなったので当然
  • これからもVisual Studioは更新していくだろうから、永続的なところにinclude系を置きたい
  • C:\Program Files (x86)\Microsoft Visual Studio\2999\include\bits\stdc++.h
  • C:\Program Files (x86)\Microsoft Visual Studio\2999\include\atcoder\convolution.hpp などACL系全部（ACLを使う場合）
  • のように置き、Visual Studio Codeのc_cpp_properties.jsonをこのように書いたら、インテリセンスが効く 
{
    "configurations": [
        {
            "name": "Win32",
            "includePath": [
                "${workspaceFolder}/**",
                "C:/Program Files (x86)/Microsoft Visual Studio/2999/include"
            ],
            "defines": [
                "_DEBUG",
                "UNICODE",
                "_UNICODE"
            ],
            "windowsSdkVersion": "10.0.16299.0",
            "compilerPath": "C:/Program Files (x86)/Microsoft Visual Studio/2017/Community/VC/Tools/MSVC/14.16.27023/bin/Hostx64/x64/cl.exe",
            "cStandard": "c11",
            "cppStandard": "c++17",
            "intelliSenseMode": "msvc-x64"
        }
    ],
    "version": 4
}