ドイツ大学院生日記

問題を解いた際に自分の復習用として使ってます

ダイクストラ法(priority_queue)、経路復元

競技プログラミング

経路復元(ダイクストラ法)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct edge {
    int to, cost;
};
typedef vector<vector<edge> > AdjList;
AdjList graph;

typedef pair<int, int> P;

const int INF = 10000000;

vector<int> dist; 
vector<int> prever;

void dijkstra(int n, int s){
    dist = vector<int>(n,INF);
    prever = vector<int>(n,-1);
    dist[s] = 0;

    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0,s));

    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v] < p.first){
            continue;
        }
        for(int i=0;i<graph[v].size();i++){
            edge e = graph[v][i];
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                prever[e.to] = v;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}

vector<int> get_path(int t){ //頂点tへの最短路
    vector<int> path;
    for(; t != -1;t=prever[t]){
        path.push_back(t);
    }

    reverse(path.begin(), path.end());
    return path;
}

int main(void){
    int n, m;
    cin >> n >> m;
    graph = AdjList(n);
    for(int i=0;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back((edge){to,cost});
    }
    dijkstra(n,0);
    
    vector<int> ans = get_path(3);
    for(int i=0;i<ans.size();i++){
        cout << ans[i] << endl;
    }
    return 0;
}

ベルマンフォード法とダイクストラ法をvectorで実装

競技プログラミング

ベルマンフォード法

#include <iostream>
#include <vector>
using namespace std;


struct Edge {
    int to, cost;

};
typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;

const int INF = 1000000;

vector<int> dist;


bool bellman_ford(int n, int s){
    dist = vector<int>(n,INF);
    dist[s] = 0;
    for(int i=0;i<n;i++){
        for(int v=0;v<n;v++){
            for(int k=0;k<graph[v].size();k++){
                Edge e = graph[v][k];
                if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){
                    dist[e.to] = dist[v] + e.cost;
                    if(i == n-1) return true;
                }
            }
        }
    }
    return false;
}

int main(void){
    int n, m;
    cin >> n >> m;

    graph = AdjList(n);

    for(int i=0;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back((Edge){to,cost});
    }

    bellman_ford(n,0);

    for (int i = 1; i < n; i++){
       if(dist[i] != INF){
           cout << "0から" << i << "へのコスト:" << dist[i] << endl;
       }
    }
    return 0;
}

ダイクストラ法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;

struct edge {
    int to, cost;
};
typedef vector<vector<edge> > AdjList;

AdjList graph;

const int INF = 10000000;
vector<int> dist;

void dijkstra(int n, int s){
    dist = vector<int>(n,INF);
    dist[s] = 0;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0,s));

    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v] < p.first){
            continue;
        }
        for(int i=0;i < graph[v].size();i++){
            edge e = graph[v][i];
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}


int main(void){
    int n, m;
    cin >> n >> m;

    graph = AdjList(n);

    for(int i=1;i<m;i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back((edge){to,cost});
    }
    dijkstra(n,0);

    for(int i=0;i<n;i++){
        if(dist[i] != INF){
            cout << "0から" << i << "へのコスト:" << endl;
        }
    }
    return 0;
}

参考

最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会

蟻本

055ABC D問題D - Menagerie

競技プログラミング

問題D - Menagerie

この問題は１番目と２番目を決めてあげれば３番目がSかWかが決定できます。

そこで１番目、２番目を 『S、S』『S、W』『W、S』『W、W』と決めてあげれば与えられた文字列から全体を決定することができます。 そして完成した文字列が与えられた文字列と矛盾していないか最後には判定します。文字列を作成するのにはox文字列の最後から一つ前まで見てあげれば良いです。 したがって矛盾判定を行う箇所はox文字列最後の要素を含んだ３組を判定してあげれば良いです。 具体的には以下の３組ようになります。

n-3 n-2 n-1

n-2 n-1 0

n-1 0 1

これらの３組が全て矛盾していないか判定し、一例を示せば良いです

ソースコードは以下のようになります。

#include <iostream>
#include <string>
using namespace std;

char a[4][100005];
char s[100005];

bool check(int x, int y, int z, int j){
    bool flag = false;
    if(s[y] == 'o'){
        if(a[j][y] == 'S'){
            if(a[j][x] == 'S' && a[j][z] == 'S'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'W'){
                flag = true;
            }
        }else if(a[j][y] == 'W'){
            if(a[j][x] == 'S' && a[j][z] == 'W'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'S'){
                flag = true;
            }
        }
    }else if(s[y] == 'x'){
        if(a[j][y] == 'S'){
            if(a[j][x] == 'S' && a[j][z] == 'W'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'S'){
                flag = true;
            }
        }else if(a[j][y] == 'W'){
            if(a[j][x] == 'S' && a[j][z] == 'S'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'W'){
                flag = true;
            }
        }
    }
    return flag;
}

int main(void){
    long n;
    int cnt = 0;
    bool flag2 = false;
    
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> s[i];
    }

    a[0][0] = 'S';
    a[0][1] = 'S';
    
    a[1][0] = 'S';
    a[1][1] = 'W';
    
    a[2][0] = 'W';
    a[2][1] = 'S';
    
    a[3][0] = 'W';
    a[3][1] = 'W';

    for(int j=0;j<4;j++){
        for(int i=2;i<n;i++){
            if(a[j][i-2] == 'S'){
                if(a[j][i-1] == 'S'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'S';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'W';
                    }
                }else if(a[j][i-1] == 'W'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'W';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'S';
                    }
                }
            }else if(a[j][i-2] == 'W'){
                if(a[j][i-1] == 'S'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'W';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'S';
                    }
                }else if(a[j][i-1] == 'W'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'S';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'W';
                    }
                }
            }
        }
        if(check(n-3,n-2,n-1,j) == true && check(n-2,n-1,0,j) == true && check(n-1,0,1,j) == true){
            for(int i=0;i<n;i++){
                cout << a[j][i];
            }
            cout << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
    return 0;
}

TokenMismatchException in compiled.php line3227

Laravel

【TokenMismatchException in compiled.php line3227】

webシステムをLaravelで開発しているのですが、このフォーム送信時にエラーが出ました。

まずgoogleで検索をしたら以下のサイトを見つけました。

laracasts.com

このサイトでの結論は{{ csrf_field() }}が埋め込まれていないことが原因だそうです。

これを試したところ無事エラーは出なくなりました。

よかった。

No4 おもりと天秤

競技プログラミング

No4 おもりと天秤　解説

問題

NとWがN個与えられ、２組に重りを分け、その２組の重さが等しくなるようにできるのかどうかを調べる問題です。

解答

まず２組が等しくなるためには全ての重りの和が偶数でなければいけません。
その場合にその半分の和となる選び方ができれば重りを等しくすることができます。

この問題は動的計画法で解くことができるためbool型の以下のようなdp配列を用意します。
dp[i番目までの重りを選んだ時][重さ]
まず全てfalseを入れておきdp[0][0]にはtrueを入れておきます。
そしてdp[i][j]がtrueの時、次の重り、つまりi+1番目まで選択した時そのi+1番目の重りを加えた重さまでは作ることができるのでtrueを入れます。
反対にi+1番目の重りを入れない場合でもtrueにします。

dp[i+1][j+w[i]] = true;
dp[i+1][j] =true;

そのようにして0≦ i < n, 0≦j≦mの範囲で繰り返すとdp[n][m]には答えが入っています。

以上解説でした。

以下ソースこーどです。

#include <iostream>
using namespace std;

int main(void){
    int n,w[1005], sum = 0, m;
    bool dp[105][10001];
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> w[i];
        sum += w[i];
    }
    m = sum/2;
    for(int i=0; i<n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j] = false;
        }
    }
    if(sum %2 == 1){
        cout << "impossible" << endl;
        return 0;
    }else{
        dp[0][0] = true;
        for(int i=0; i<n;i++){
            for(int j=0;j<=m;j++){
                if(dp[i][j] == true){
                    dp[i+1][j+w[i]] =true;
                    dp[i+1][j] = true;
                }
            }
        }

    }
    if(dp[n][m] == true){
        cout << "possible" << endl;
    }else{
        cout << "impossible" << endl;
    }
    return 0;
}

No.3　ビットすごろく

競技プログラミング

yukicoder No.3　ビットすごろくの解説

この問題はある数字Nが与えられ。１〜Nの区間での最小の移動回数を求めます。

位置の数字を２進数で表し「１」のbit数だけ前、後に移動することができます。

まずqueueとしてQを宣言します。Qにはその位置から移動できる場所を入れていきます。前に移動した場合と後に移動した場合の２通りを入れていきます。

そして移動した回数を保存していく配列dを宣言します。

また移動したか、していないかを保存する配列を宣言します。

移動したことがあるばい、前回に保存されている方が移動回数は少ないため更新する必要性はありません。この操作を移動できなくなる。つまりキューが空になるまで続けることで答えを導き出すことができます。

数字の「１」のビット数を数得る場合は__builtin_popcount 関数を使えば求めることができます。

以上解説でした。

以下ソースコードになります。

#include <iostream>
#include <queue>
using namespace std;
const int INF = 100000000;

int main(void){
    int n, i;
    int v[10005], d[10005]; //vは移動したかしていないかを判別する配列、dはiまでの最小移動回数を保存する配列
    cin >> n;
    for(int i=1;i<=n;i++){
        v[i] = 0;    //全て移動していないことにする。
    }
    for(int i=1;i<=n;i++){
        d[i] = INF;    //全て移動移動できないとしておく
    }
    
    queue<int> que;    //queは移動できる場所を格納する
    que.push(1);
    v[1] = 1;
    d[1] = 1;

    while(!que.empty()){
        int bit;
        i = que.front();
        que.pop();
        bit = __builtin_popcount(i);    //この関数は「１」のbit数を返してくれる
        if(i+bit >= 1 && i+bit <= n && v[i+bit] == 0){
            que.push(i+bit);
            v[i+bit] = 1;
            d[i+bit] = d[i] + 1;
        }
        if(i-bit >= 1 && i-bit <= n && v[i-bit] == 0){
            que.push(i-bit);
            v[i-bit] = 1;
            d[i-bit] = d[i] + 1;
        }
    }
    cout << (d[n] != INF ? d[n] : -1) << endl;
     return 0;
}

No.8 N言っちゃダメゲーム

競技プログラミング

No.8 N言っちゃダメゲーム　解説

 

この問題はNとKが与えられ、Kを宣言したら負けとなるゲームです。

自分は必ず先攻で、相手は後攻です。

１〜Kの値までで加算して宣言することができます。

 

解答

この問題は自分がN−１をいうことができれば勝てます。

相手にN−１−K≦X≦N−２を相手に言わせれば良い。

自分はNー１ーKー１「Nー１ー（K＋１）」を言えば勝てます。

 

相手にNー１ーKー１ーK≦X≦N−１ーKー１ー１を言わせれば良い

自分はNー１ーKー１ーKー１「Nー１ー２（K＋１）」を言えば勝てます。

 

このように続けていくと「Nー１ーM（K＋１）」（Mは定数）を言える時自分は勝つことがでいます。逆にこの値を相手に言わせてしまうと負けになります。自分は先攻で自分の初期状態は０であるためこの値が０と等しいと自分はこの値を宣言することができません。そのような場合相手は必勝法を使うため自分は勝てません。

つまり

Nー１ーM（K＋１）＝０

が成り立つ時

すなわち

N＝M（K＋１）＋１の時

負けます。

したがって

N mod (K+1) == 1の時負けとなります。

 

以上解説でした。