読者です 読者をやめる 読者になる 読者になる

競プロ記録

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

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;
}

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

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

 

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

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

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

 

解答

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

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

自分はNー1ーKー1「Nー1ー(K+1)」を言えば勝てます。

 

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

自分はNー1ーKー1ーKー1「Nー1ー2(K+1)」を言えば勝てます。

 

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

つまり

Nー1ーM(K+1)=0

が成り立つ時

すなわち

N=M(K+1)+1の時

負けます。

したがって

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

 

以上解説でした。

二分探索木:削除

アルゴリズムとデータ構造】二分探索木:削除(解説)

9.4の解説をします。

ある節点Zを削除する時を考えます。

・Zが子を持たない場合

 ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い

 

・Zが子を一つ持つ場合

 Zは親と子供に挟まれているので、Zを削除するためには親の子供の設定をZの子

 供に変え、(Zの子供)の親を(Zの親)に変えてあげればZを削除できます。

 

・Zが子を二つ持つ場合

 Zの次節点とは単にZの上の接点のことを指している。Zが持っている2つの子をZの上の節点に移してあげれば良い。そこでZの次節点の値をZ地震にコピーし、Zの次節点を削除してあげればZを削除したことになる。

 

解説のプログラムの解説をします。

 

二分探索木Tと削除対象Zを受け取ります。

そこで削除対象は、Zが子を持つ場合ではZの次節点でした。そこで削除対象をYに移します。子を持たない、子を1つだけ持つ場合ではY=Zであり、Zが子を持つ場合はZの次節点をYに代入します。

 

次に削除対象の子供を調べます。

左に子があれば左の子をxに代入します。

左に子供がない場合にはxに右の子の値を代入します。この場合実際に右に子供がいなくても構いません。あとで処理します。

 

そしてxがNILじゃないつまり削除対象の子供が存在する場合、削除対象の親を、削除対象の子供の親に設定します。

 

削除対象の親が存在しない時、その削除対象の子供を根とします。

削除対象がその親の左の子供の場合には、左の子供の位置に削除対象の子供を入れます。

削除対象がその親の右の子供の場合には、右の子供の位置に削除対象の子供を入れます。

最後の子供が二ついた場合において次節点が削除された場合

つまり削除対象がZと異なる場合

Zの値に、削除対象の値を代入します。

 

次節点を求めるアルゴリズムの解説

右の子供が存在する場合は値が一番小さい節点が次節点となるので、その節点を調べて返します。

右の子供が存在しない場合には、自身が左の子供になっているような節点の親が次節点となる。

次節点は以下のようにして探索します。まずYにXの親を代入します。

そのYが存在するつまり根ではないかつ、右の子供がXである限り以下の操作を繰り返します。

 

まずXとYを位置関係そのままで上に移していきます。

つまりYはXの親であるから、XにYを代入

YにYの親を代入

を繰り返すことで次節点を探索することができます。

 

次に二分探索木での最小値を求めるアルゴリズムの解説をします。

最小値となる候補はその値かその左の子供であるめ左の子供について一番深い場所にある節点を探索していきます。

Xの左の子が存在するまで繰り返します。

そうすることで二分探索木の最小値を求めることができます。

 

一般的に二分探索木では木の高さをできるだけ低く維持する必要性がある。

バランスのとれた木を平衡二分探索木という。

 

 

 

 

二分探索木:探索

アルゴリズムとデータ構造】二分探索木:探索(解説)

215ページの解説をしていきます。

 

まずどこから探索していくかの基準となるxと調べる値kを引数として受け取ります。

そのあとxをどんどん移していくのですがそのxの値が存在しなくなるまたは、keyにたどり着くまでループ内の作業を繰り返します。

kの値がその基準のxよりも小さい場合にはxを左の子へ移し、大きい場合にはxの子を右の子へ移します。

 

この操作を繰り返すことで、節点を探し出すことができます。

 

以上解説でした。