Atcoder 復習 備忘録3

競プロ典型90 006

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

multiset<int> st;
int a = 10;
// aを消去する
st.erase(st.find(a));

参考→こちら

ABC312 C問題

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

ABC312 D問題

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

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問題

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

競プロ典型90 013

ダイクストラ法
…グラフ上の頂点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

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

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

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問題

おそらくメモリオーバーで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問題

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問題

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問題

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

今回setに考えられる解のすべてを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問題

D.cpp

ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}

ユーグリッドの互除法の実装

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://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());