競プロ用のメモ

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

abc403_d D - Forbidden Difference

問題名: （例：ABC123 C - Typical Problem）

1. 問題概要

b_i-b_j\neq D となるように数列を間引く

2. 想定された解法

  1. mod D で分類
  2. 分類したものを捨てる，捨てないでDPする．

3. 必要な知識・テクニック

  • modによる演算
  • DP

4. 解くために必要な発想

  • modで分類した後に，「DP」という二段階のやり方

5. 解けなかった理由

  • modまでは気付けた．そのあとに，DPするという処理が思いつかなかった．もっと簡単な処理だと信じ切ってしまった．

6. 再発防止・次回の対策

  • D問題でもこのような重めの複合問題が出ると認識する．

7. 今後の課題・練習予定

  • 特にない

8. 再挑戦予定日（任意）

  • 2025/6/30以降

学習用メモのtemplate

問題名: （例：ABC123 C - Typical Problem）

  • 問題URL: [リンクを貼る]

1. 問題概要

問題の内容を簡潔に日本語で要約（コピペでなく、自分の言葉で書くのがおすすめ）

2. 想定された解法

  • アルゴリズムや方針の要点を日本語で説明
  • 計算量、データ構造などに触れると良い

3. 必要な知識・テクニック

  • 例：二分探索、累積和、DFS/BFS、Union-Find、DP（bit DP）など

4. 解くために必要な発想

  • 例：「制約が小さいので全探索できる」「貪欲で構築できる」など
  • 自分が解法に至るうえで気づくべきだったポイントを書く

5. 解けなかった理由

  • どこで詰まったか、何が分からなかったか
  • 勘違い・思い込み・実装の詰めの甘さなど

6. 再発防止・次回の対策

  • 次に似た問題が出たらどうするか
  • どのように考え始めるか、何を疑うべきか

7. 今後の課題・練習予定

  • 強化したいアルゴリズムやテクニック
  • 解法パターンの反復練習など

8. 再挑戦予定日（任意）

  • 例：1週間後の2025-05-07にもう一度解く

9. メモ・参考リンク（任意）

  • 解説ブログ、解説動画、類題など

自作バグ：二分探索

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(); // ここの処理

  }    

}

```