2周目振り返りと競技プログラミング

一昨日、土曜日、俺はコンテストに出た。またレートが下がった。

C - Martial artist をBFSっぽく解く

[BFS, ラムダ式, vectorのサイズ,set]
こいつを幅優先探索・BFSっぽく解きます。後せっかくなので、ラムダ式を使います。ラムダ式を使った気持ちとしては、setにinsertするのと、queueにpushするのと、vectorに格納するのを3行書くのが気持ち悪いかな?って思ったからです。

技術のメモ
- set
  
  これは、配列の中に数字があるかを判定するのに使います。set.insert(5)した後に、set.find(5)をすると、多分5が入っていたっていう情報が得られる。知らん。
```
set<int> st;
st.insert(5);
if(st.find(5) != st.end()){
    // stの中に5が格納済みの場合、ここの処理(今回は格納されているのでこっち)
} else {
    // st の中に5が格納されていない場合、ここの処理
}
```
  実際、st.find(x) != st.end() でxが格納されているというのは正直覚えづらいので、map<int,bool> で代用することが僕の場合は多いです。
```
map<int, bool> mp;
mp[5] = true;
if(mp[5]){
    // mpの中に５がすでに入っている
} else {
    // mp の中に５が入っていない
}
```
  まあええか。

この問題を解く気持ちとしては、格闘技のスキルNを習得したいとき、Nの前提技術に、1,2,8が指定されているなら、1,2,8を習得する。

8の前提技術に指定されている技術も修得する。
2の前提技術に指定されているやつも…
1の前提も…

で、次は、1,2,8の前提技術の前提も…っていう入れ子構造的なやつっすね。
これって、修得した技術を親としたときに、前提技術を子とした木みたいな感じになりそうじゃないですか。(実際には、AとBの両方に前提技術としてCが含まれている場合もあるので、木にはならないけど)

ってことで、まずNをqueueに入れて、Nの前提知識をqueueに入れて…、って感じで、BFSでやっていることが使えそうだなってなるね。

5の前提に3,3の前提に5、みたいなことは制約上無いので(Xの前提技術は、X-1以下の整数とされているので)、安心して解ける。

#include <bits/stdc++.h>

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
#define fore(i, a) for(auto &i: a)
//Write From this Line

// BFS っぽく解いてみる
int main(){
    // 入力
    int n; cin >> n;
    vector<int> t(n), k(n);
    vector<vector<int>> a(n);
    rep(i,n){
        cin >> t[i] >> k[i];
        a[i].resize(k[i]);
        rep(j,k[i]) cin >> a[i][j];
    }

    // BFSに必要なもの宣言
    set<int> st;
    queue<int> que;
    vector<int> ans(0); // 必要な技術の一覧

    // 必要な技術をaddする関数
    auto add = [&](int x){
        if(st.find(x) == st.end()){
            st.insert(x);
            que.push(x);
            ans.push_back(x-1);
        }
    };

    add(n);
    //BFS
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(auto nv : a[v-1]){
            add(nv);
        }
    }

    ll sum_time = 0;
    rep(i,ans.size()){
        sum_time += t[ans[i]];
    }
    cout << sum_time << endl;
}

vector ans();
- こいつに、修得する技術の番号を格納する
```
auto add = [&](int x){
  ...
}
```
ラムダ式。技術 x が必要だと分かった時にこいつが呼び出される。

すでに add(x)が呼び出されていた場合、つまりsetの中にxがあった場合、何も行われない。

setの中になかった場合、setへの挿入、queへのpush,vector ansへの格納が行われる。(ansへの挿入時は、添え字をマイナス1しといた(お好みで))
```
while(!que.empty()){
    ...
}
```
BFSのメインの部分。ラムダ式を定義しておいたおかげで6行しか使っていない。きれいに見える。
long long sum_time;

出力する答え。c++とかいうカス言語はintだと32bitしか扱えず、32bitよりも大きい値が答えになりうるのでlong long にする
```
rep(i,ans.size())
```
vector ansのサイズだけループを回す。
```
for(int i = 0; i < ans.size(); i++){
}
```
と同じ。ans.size()はループの度毎回実行されると思いきや、実はコンパイル最適化が行われていてans.size()は1回しか行われないとか？(要出典)
```
sum_time += t[ans[i]];
```
ans[i]を習得するのにかかる時間をsum_timeに足す。