Atcoder 復習 備忘録3

# 競プロ典型90 006

https://atcoder.jp/contests/typical90/tasks/typical90_f

`multiset`から`erase`するときイテレータではなく値自体を渡してしまうと、同じ値の複数の要素が消されてしまうので注意する。正しくは以下のように書く。

```cpp
multiset<int> st;
int a = 10;
// aを消去する
st.erase(st.find(a));
```
参考→[こちら](https://nizi-24.hatenablog.com/entry/2021/09/10/160755#:~:text=set%3C%20int%20%3E%20st%3B%20st.insert%20%281%29%3B%20st.insert%20%282%29%3B,%3C%3C%20endl%3B%20%2F%2F%201%20multiset%E3%81%A7%E4%B8%80%E3%81%A4%E3%81%A0%E3%81%91%E8%A6%81%E7%B4%A0%E3%82%92%E6%B6%88%E5%8E%BB%E3%81%99%E3%82%8B%20erase%E3%81%AB%20%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF%20%E3%82%92%E6%B8%A1%E3%81%99%E3%81%A8%E4%B8%80%E3%81%A4%E3%81%A0%E3%81%91%E5%89%8A%E9%99%A4%E3%81%A7%E3%81%8D%E3%81%BE%E3%81%99%E3%80%82)


# ABC312 C問題
https://atcoder.jp/contests/abc312/tasks/abc312_c

`vector<pair<int,int>>`の`sort`は`sort(v.begin(),v.end());`とすると1つ目の要素でソートされる。


# ABC312 D問題
https://atcoder.jp/contests/abc312/tasks/abc312_d

mintのクラス↓
https://qiita.com/uesho/items/1ee5c3e665c72c035880

# ABC317 C問題
https://atcoder.jp/contests/abc317/tasks/abc317_c

順列
```C.cpp
std::sort(str.begin(), str.end(), std::greater<>());

do {
    cout << str << endl;
} while (std::next_permutation(str.begin(),　str.end()));

```

# ABC317 D問題
https://atcoder.jp/contests/abc317/tasks/abc317_d

ナップザックDP。ちゃんとDPやり直した方がよさそう。
参考↓
https://qiita.com/drken/items/a5e6fe22863b7992efdb


# 競プロ典型90 013

https://atcoder.jp/contests/typical90/tasks/typical90_m

ダイクストラ法
…グラフ上の頂点sが指定されたときに、頂点sから各頂点に行く最短経路ををそれぞれ求める。
N頂点、M辺のときO((N+M)logN)

参考↓
https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/dijkstra#aoj-grl_1_a---single-source-shortest-path


# 競プロ典型90 21
https://atcoder.jp/contests/typical90/tasks/typical90_u

強連結成分SCC
有向グラフにおいて、互いに行き来が可能な頂点の集合。
を求める。

原理
https://hkawabata.github.io/technical-note/note/Algorithm/graph/scc.html


# ABC318 D問題
https://atcoder.jp/contests/abc318/tasks/abc318_d

bit DPで解く。
dp[b]をうち立っているビットを$i_1,\dots,i_k$としたとき、頂点$i_1,\dots,i_k$についてはその頂点を端点とする辺を選んでいる。選んだ辺の重みの総和の最大値と定義。

```D.cpp
	rep(b, (1 << n) - 1) {
		int l = -1;
		rep(i, n) if(!(b >> i & 1)) {
			l = i;
			break;
		}
		rep(i, n) if(!(b >> i & 1)) {
			int nb = b | (1 << l) | (1 << i);
			dp[nb] = max(dp[nb], dp[b] + d[l][i]);
		}
	}

```
# ABC320　D問題
https://atcoder.jp/contests/abc320/tasks/abc320_d

おそらくメモリオーバーでREに引っかかってしまった。原因はdfsするときの次の値と座標（x,y）の三つの値をvectorとpairで別々に管理していたことにあると思われる。模範解答ではarrayを使用。以下参照

``` D.cpp
	vector<vector<array<int,3>>>G(n);
	for(int i=0;i<m;i++){
		int a,b,x,y;
		cin >> a >> b >> x >> y;
		a--,b--;
		G[a].push_back({b,x,y});
		G[b].push_back({a,-x,-y});
	}

	auto dfs=[&](auto self,int v,ll x,ll y)->void{
		visited[v]=true;
		pos[v]={x,y};
		for(auto[vv,dx,dy]:G[v]){ //構造化束縛で受け取り。C++17じゃないと使えないという警告でる。
			if(!visited[vv]){
				self(self,vv,x+dx,y+dy);
			}
		}
	};
```

ちなみに今まで`make_pair`で`pair`を作ってから代入をしていたが、あらかじめ定義した`pair`に`{x,y}`の形で代入すれば、自動的に`pair`になる。



# ABC321 C問題
https://atcoder.jp/contests/abc321/tasks/abc321_c

bit全探索。使えるようにならなきゃなぁ。

```c.cpp
  for(int i=2;i<(1<<10);i++){
    long long x=0;
    for(int j=9;j>=0;j--){
      if(i&(1<<j)){
        x*=10;
        x+=j;
      }
    }
    ans.push_back(x);
  }
```

# ABC323 D問題

https://atcoder.jp/contests/abc323/tasks/abc323_d

bit演算で解く。
```D.cpp
for(int i=0;i<n;i++){
	cin>>x>>y;
	while((x&1)==0){
		x>>=1,y<<=1;//xを1bit右シフト、yをbit左シフト
	}
	mp[x]+=y;
}
```
mapのイテレータは
`map<int,long long>::iterator itr;`でとれる。`itr=mp.begin();`や`y=(*itr).second;`といった使い方ができる。

ちなみに、`vector<queue<int,int>>`というよくわからないデータ構造を使ったため、沼にはまってしまったが、`map<int,int>`を使えば、自分がやろうとしたのと同じ方針で解けたらしい。反省。

# ABC324 C問題

https://atcoder.jp/contests/abc324/tasks/abc324_c

Sの長さの総和が5*10^5以下という制約をちゃんと書くにしていなかったせいで正答できなかった。
この制約があれので、N(<5*10^5)*S[i].size()のループを回すことでできる。

今回set<string>に考えられる解のすべてをinsertするというアプローチをとったがメモリ不足でREになった。おそらくstringの長さ×setの個数が10*9程度を超えているとREかTLEになる(?)っぽい。
あと、文字列を+で連結するより、appendを使った方が速そうという発見があった。

# ABC325 D問題

難しすぎた。本問とは関係ないが、mapの中身を順番に出力する方法。

```c.cpp
  for (auto iter = tempMap.begin(); iter != tempMap.end(); ++iter) {
    cout << "[" << iter->first << "," << iter->second << "]\n";
  }
```
参考↓
https://www.delftstack.com/ja/howto/cpp/how-to-iterate-over-map-in-cpp/


# ABC142 D問題
https://atcoder.jp/contests/abc142/tasks/abc142_d

```D.cpp
ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}
```
ユーグリッドの互除法の実装


# ABC327 E問題

https://atcoder.jp/contests/abc327/tasks/abc327_e

永遠に解けないDP問題。式の特定の部分を関数M(k)でおいてM(k)に関するDPを解くのがミソ。

・浮動小数点の表示方法

```E.cpp
cout<< std::fixed << std::setprecision(10) <<ans<<endl;
```

std::fixed は小数部の桁数をより正確に指定したい場合には書式フラグ。fixedを使用しないと、setprecisionの指定した長さが整数部も含む。
std::setprecision は入出力ストリームで浮動小数点型の桁数を指定出来るマニピュレータ。
参考　https://qiita.com/ryupim/items/1cbeb860d4a2f056358a

上の表記だと小数点以下10桁まで表示。

# ABC328 E問題
https://atcoder.jp/contests/abc328/tasks/abc328_e

最小全域木かと思ったけれど違った。↓参考
https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/minimum-spanning-tree


与えられた全域木を全探索する方法
```E.cpp
#include <ranges>

    basic_string<bool> use_edges(M, false); // M 本の辺のうち
    ranges::fill(use_edges | views::take(N - 1), true); // N - 1 本を使う
    ranges::reverse(use_edges);
    
    do
    //操作
    while (ranges::next_permutation(use_edges).found);

```
C++ 20が入っていないため、自分のPCでrangesが使えない。時間あったら入れる。


# ABC329 B問題
vectorの最大値を求める。
```b.cpp
int m = *max_element(a.begin(), a.end());
```