競プロ用のメモ

競プロのメモです。競プロで得たc++の知識を書きます。atcoder緑が書いてます。

自作バグ：二分探索

bug

```cpp

ll s;

bool check(ll mid){

  s=0;

  s+=mid*....

}

 

int main(){

  ....

  if(ng-ok>1){

  ...

  }

  cout << s << endl;

}

```

みたいなプログラムを作ってcheckで計算したsをそのまま使おうとした．

checkは常にtrueを返すわけではないから，sはokの値で計算しなおす必要がある．

sがグローバル変数なら，

```cpp

check(ok)

```

とかやっておけばOK．

自作バグ：DFS

bug DFS

dfsを再帰で呼び出すときに，引数のベクトルの処理で間違えた．

ループでdfsする場合は変化を加えた変数を元に戻す必要がある．

 

```cpp

void dfs(vec<bool> seen, vec<int> a){

  // 適当な処理

  for(int i=0; i<n ; i++){

    seen[i]=true;

    vec.push_back(i);

    dfs(seen,a)

    seen[i]=false; // ここの処理

    vec.pop_back(); // ここの処理

  }    

}

```

自作バグ：メモ再帰で関数と配列の取り違え

bug dp メモ化再帰

EDPCのJ問題，すしのやつ

https://atcoder.jp/contests/dp/tasks/dp_j

 

```cpp

double f(int s1,int s2,int s3){
  if(seen[s1][s2][s3]) return dp[s1][s2][s3];
  seen[s1][s2][s3]=true;
  double res=1;
  if(s1>0) res+=f(s1-1,s2,s3)*s1/n;
  if(s2>0) res+=f(s1+1,s2-1,s3)*s2/n;
  if(s3>0) res+=f(s1,s2+1,s3-1)*s3/n;
  res/=double(s1+s2+s3)/n;
  //  cout << res << endl;
  return dp[s1][s2][s3]=res;
}

```

と書くべきところ，関数ではなく変数を書いていた．orz

```cpp

  if(s1>0) res+=dp[s1-1][s2][s3]*s1/n;

```

状態の遷移も忘れた．2枚の皿が減れば，1枚の皿が増えるという当たり前のことが分からず．配列もこのことを考えて切る必要がある．

```cpp

  if(s2>0) res+=f(s1,s2-1,s3)*s2/n;
  if(s3>0) res+=f(s1,s2,s3-1)*s3/n;

```

 

 

modintのコンパイルエラー

modint

拾ってきたmodintをコンパイルオプション付きでコンパイルすると，エラーを吐く．

main.cc: In constructor ‘mint::mint(long long int)’:
main.cc:12:20: warning: declaration of ‘x’ shadows a member of ‘mint’ [-Wshadow]
   12 |     mint(long long x=0) : x((x%mod+mod)%mod) {}

xという名前の変数が被ってますよ，という警告． 私が拾ってきたmodintはこんな感じになっていたので，

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}

コンストラクタを一部修正．これで変数xがなくなる．

    mint(long long a=0) : x((a%mod+mod)%mod) {}