競プロ記録

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

Chokudai Speed Run G問題

Chokudai Speed Run001 G問題解説

問題

数列 aが与えられ a を連結させた整数を、 1,000,000,007 で割った余りを求めなさい。

サンプル

Input

7
7 6 5 4 3 2 1

Output

7654321

解説

全てを加えて剰余をとるという方針はlong long では所持できないので不可能です そこで剰余の性質の以下2つを使います。
(x*y)%MOD = ( (x%MOD) * (y%MOD) ) % MOD
(x+y)%MOD = ( (x%MOD) + (y%MOD) ) % MOD


この二つの性質を使うことによって桁を一つづつ見ていくことによって連結した数列の剰余を正しく求めることができます。

以下コード

#include <iostream>
using namespace std;

#define MOD 1000000007

int main(void){
    int n;
    string s;
    cin >> n;
    for(int i=0; i<n; i++){
        string tmp;
        cin >> tmp;
        s += tmp;
    }
    long long ans = 0;
    for(int i=0; i<s.length(); i++){
        ans = ans * 10 + (s[i]-'0');
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

ダイクストラ法(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

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

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

n-3 n-2 n-1

n-2 n-1 0

n-1 0 1

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

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

#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

【TokenMismatchException in compiled.php line3227】

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

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

laracasts.com

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

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

よかった。

No4 おもりと天秤

No4 おもりと天秤 解説

問題

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

解答

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

この問題は動的計画法で解くことができるため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が与えられ。1〜Nの区間での最小の移動回数を求めます。

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

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

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

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

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

数字の「1」のビット数を数得る場合は__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);    //この関数は「1」の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;
}