n度あることはn+1度ある

書きたいことを書く 統一性はない

Tenka1 Programmer Beginner Contest 2018(天下一プログラマーコンテスト) 所感

コンテストお疲れさまでした。自分としては非常に悔しくも今までのコンテストの中で一番いい結果に終わりました。
コードはコンテストに提出したものそのままで、ブラッシュアップしていません。
以降ネタバレ注意

A - Measure

受け取った文字のサイズを見て条件分岐させるだけです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    if(s.size()==2)
        cout<<s;
    else{
        reverse(begin(s),end(s));
        cout<<s;
    } 
}

B - Exchange

kの最大値が100までなので、実際にシミュレーションしてやれば大丈夫です。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long a,b,k;
    cin>>a>>b>>k;
    for(int i=0;i<k;i++){
        if(i%2==0){
            if(a%2!=0)
                a--;
            a/=2;
            b+=a;
        }
        else{
            if(b%2!=0)
                b--;
            b/=2;
            a+=b;
        }
    }
    cout<<a<<" "<<b;
}

C - Align

与えられた数列の最小値もしくは最大値を、今までに作成した、差分が最大となるような数列の右もしくは左に置いたとき、最も差分が大きくなる箇所に最小値もしくは最大値を与えられた数列がなくなるまで置いていきます。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long n;
    cin>>n;
    vector<long> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(begin(a),end(a));
    long first=0,last=a.size()-2;
    long left=a[last+1],right=a[last+1];
    long sum=0;
    a.pop_back();
    while(first<=last){
        long t1=max(abs(left-a[first]),abs(right-a[first]));
        long t2=max(abs(left-a[last]),abs(right-a[last]));
        if(t1>t2){
            sum+=t1;
            if(abs(left-a[first])>abs(right-a[first]))
                left=a[first];
            else
                right=a[first];
            first++;
        }
        else{
            sum+=t2;
            if(abs(left-a[last])>abs(right-a[last]))
                left=a[last];
            else
                right=a[last];
            last--;
        }
    }
    cout<<sum;
}

D - Crossing

ここで自分が各問題をACした時間を見てみましょう。
f:id:benntann:20181027225733p:plain
はい。微妙に間に合いませんでした。思考はあっていたのですが、完全にコーディング能力不足です。
コンテストが終わった直後、ちょっと直したら普通にACして今年一番の悲しみでした・・・
この問題は結論を言うと、与えられたNが、n(n+1)/2、つまり1+2+3...+nの和に等しくなければ、問題の部分集合は作れません。
また部分集合はn+1個作成でき、部分集合の要素数はいずれもn個になります。
証明はちょっと分かりませんが、自分で一度書いてみると分かります。
[例]
ABCDという1つの部分集合を作成したとき、残りの部分集合は
AEFG,BEHI,CFHJ,DGIJとなります。数値にすると{{1,2,3,4},{1,5,6,7},{2,5,8,9},{3,6,8,10},{4,7,9,10}}となります。
この部分集合の作成をどうしようかなとすごい悩んだせいで時間内にACできませんでした。
自分がとった方法としては、以下の(汚い)画像のように丸で囲ってある部分を、同じ色の線の要素からコピーしていきています。それ以外の要素は、単純に加算しています。
f:id:benntann:20181027230849p:plain

#include <bits/stdc++.h>
using namespace std;
long t;
long j;
int main(){
    long n;
    cin>>n;
    for(int i=1;i<=1000;i++){
        if(i*(i+1)/2 == n){
            cout<<"Yes"<<endl;
            cout<<i+1<<endl;
            t=i;
            break;
        }
        if(n < i*(i+1)/2){
            cout<<"No";
            return 0;
        }
    }
    int a[t+1][t];
    long last;
    for(int i=0;i<t+1;i++){
        if(i==0){
            for(j=0;j<t;j++){
                a[i][j]=j+1;
            }
            last=a[0][t-1];
        }
        else{
            j=0;
            while(j<i){
                    a[i][j]=a[j][i-1];
                    j++;
            }
            int offset=1;
            while(j<t){
                a[i][j]=last+offset;
                j++;
                offset++;
            }
            last=a[i][t-1];
        }
    }
    for(int i=0;i<t+1;i++){
        cout<<t<<" ";
        for(j=0;j<t;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}

総括

一応パフォーマンスは最高(?)の1600を初めてとれたので良かったという反面、ギリギリ提出できないという非常に悔しい思いをしたのでまた精進していきます。

Tenka1 Programmer Beginner Contest 2017 D - IntegerotS

bitの生成に難儀した問題。
詳しい解法は公式放送や解説を見てもらえれば分かると思います。
簡単に説明すると、与えられたkよりも小さな値でbitが立っている数値を足していき、一番大きなものを出力するというものです。一見230全てのパターンを行わなければならないと思いますが、10101というbit列が与えられたとき、00100や00001などを考慮する必要がないことは簡単にわかります。
10101であれば考慮するのは、10101、10011、01111の3つです。これはあるbitが立っていればそれを0にし、それ未満のbitを全て立てればよいです。
最大で30通りほどなので、全て試しても問題なくAC可能です。
bitの生成をどうやろうかなとかなり長考していました。
ビット演算に慣れていると思っていましたが、自由自在にビット生成をできるにはまだレベルが足りていなかったようでした。

#include <bits/stdc++.h>
using namespace std;
int main() {
    long n,k; cin>>n>>k;
    vector<long> a(n),b(n);
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i];
    long MAX=0,mask=0;
    for(int i=0;i<=30;i++){
        if(i==0||(k&(1<<i))!=0){
            long cmask= mask|((k>>(i+1))<<(i+1));
            if(i==0) cmask=k;
            long sum=0;
            for(int i=0;i<n;i++){
                if((cmask|a[i]) == cmask)
                    sum+=b[i];
            }
            MAX=max(sum,MAX);
        }
        mask|=(1<<i);
    }
    cout<<MAX;
}

ABC098 D - Xor Sum 2

ビット演算の性質とアルゴリズムの難しさが重なった問題でした。
XORというものは、A XOR BA OR Bを考えたとき、必ずA XOR BA OR Bとなります。これは解説にもあるように、桁上がりがされないからです。
そのため、l=1,r=3が成り立ち、l=1,r=4がダメであれば、l=1,r>4だと成り立つ場合は1つもありません。
l=1,r=4のXORの結果をXA4、ORの結果をOA4とします。このときは成り立っていないので、上記の理由によりXA4 < OA4です。
l=1,r=5のときXA4 XOR a5OA4 OR a5が行われますが、XA4 < OA4で、同じa5を演算対象にしたとき、上記の理由によりORの結果と同じになることはあり得ず、rだけを大きくしていっても累積排他的論理和の結果は、常に累積論理和の結果未満になり続けます。
よって、以下のような流れでACできます。
1. a[r]の値を、現在の累積排他的論理和、累積論理和に累積させる
2. それぞれの累積値が異なれば、累積値が同じになるまで、a[l]をそれぞれから引き、lを進める
3. 結果にl-r+1を加える
所謂尺取り法とよばれるアルゴリズムだそうです。
a[r]の値を加えたときにダメでも、今まで累積させたものを引いていけば同一になる可能性があるので、lも進めていく必要があります。
ORのほうは単純に減算すればいいですが、XORはA XOR A = 0という性質があるため、これで累積値から引くことができます。関係ないですが、これはレジスタの0初期化などにも使われています。
l-rというものは、その分各数列に加えられるためです。+1というものはl=rの分を加えています。
XORの性質に気づけなかったことは、少し残念でした。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long n; cin>>n;
    vector<long> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    long x=a[0],s=a[0];
    long b=0,r=1;
    for(int i=1;i<n;i++){
        x^=a[i],s+=a[i];
        while(x!=s){
            x^=a[b],s-=a[b];
            b++;
        }
        r+=i-b+1;
    }
    cout<<r;
}

参考:
尺取り法

ABC035 C - オセロ

初めてのいもす法を使用してACした問題。
いもす法とはいもすさんが考案されたアルゴリズムです。
自分も詳しく知っているわけではありませんが、配列の1番目から10番目まで2を足す、3番目から6番目まで5を足す....とやっていき、最後に配列の中身を表示するといった、区間の累積和をとっていき最終的な答えを求める場合に有効なアルゴリズムだそうです。
解説のプレゼンの19ページ目からの説明がわかりやすいと思います。
A,B間にCという値を加算する場合、愚直に全て加算するのではなく、A番目の要素にC、B+1番目の要素に-Cを加算し、最後に纏めて算出するといった感じです。
愚直に全て加算していくと今回の場合は最悪4*1010のループが発生しますが、いもす法を使用すると最後の累積和以外ループを使用しないので、最悪でも2*105で求まります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long n,q; cin>>n>>q;
    vector<long> g(n,0);
    for(int i=0;i<q;i++){
        long l,r; cin>>l>>r;
        g[l-1]++;
        if(r!=n)
            g[r]--;
    }
    long sum=0;
    for(auto x:g){
        sum+=x;
        cout<<sum%2;
    }
    cout<<endl; //このコンテストでは解のあとに改行がないとACされません
}

ABC067 D - Fennec VS. Snuke

木構造の性質を忘れていて解答ACしてしまった悔しい問題。
この問題は問題文に最大のヒントが与えられています。
マスと道から構成されるグラフは木です
つまりこのグラフ上に閉路(ループ)は存在しません。ある点iからある点jに行くための道は1つしか存在しません。そのため解答にもあるように、1とNが繋がっている道にある頂点以外は、それぞれ接続されているプレイヤーしか塗りつぶせません。逆に言うと、この道にある頂点が共有で塗りつぶせる頂点なのでここを多くとる必要があります。
結果、1とNが繋がっている道にある頂点を最優先で塗りつぶして、残りの頂点を塗りつぶす動きが最適ということです。
木構造を使用することがないため、閉路がないという性質をすっかり忘れていました。これから木構造に関する問題が出た場合は利用できるようにしていきたいです。

#include <bits/stdc++.h>
using namespace std;
vector<vector<long>> tree(1e5+1);
void f(long k,vector<long>& d){
    queue<long> q;
    q.push(k);
    while(!q.empty()){
        long t=q.front(); q.pop();
        for(auto x:tree[t]){
            if(x!=k&&d[x]==0){
                d[x]=d[t]+1;
                q.push(x);
            }
        }
    }
}
int main(){
    long n; cin>>n;
    for(int i=0;i<n-1;i++){
        long a,b; cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    vector<long> df(n+1,0),ds(n+1,0);
    f(1,df);
    f(n,ds);
    long sum=0;
    for(int i=1;i<=n;i++)
        sum+=df[i]<=ds[i]?1:-1;
    if(sum>0)
        cout<<"Fennec";
    else
        cout<<"Snuke";
}

ABC073 D - joisino's travel

初めてワーシャルフロイド法を使用した問題。
1つ前の記事で挙げた迷路のような、スタートとゴールがはっきりしている問題では幅優先探索が使用できますが、定まらない場合やグラフの全ての頂点と頂点間の最短距離を求めるのに有効なアルゴリズムとしてワーシャルフロイド法というものがあります。
直結の道を辿るほうが早いか、途中の道を辿ったほうが早いかを確かめていきそれを拡張するようなアルゴリズムです。詳しくは参考URLを参照してください。
解の流れとしては、
1. ワーシャルフロイド法により、全ての町と町の間の最短距離を求める
2. 町の辿る順番を変えながらその中の最短距離を求める
です。
ワーシャルフロイド法のオーダーはO(N3)のため使用可能です。
町を辿る順番は順列で列挙します。最高で8つの町を辿るだけなので、最高で40320通り(8*7*6*5*...*1)で間に合います。
列挙にはnext_permutationを使用しました。指定するコンテナの要素が昇順にソートされていればdo_whileを使用し簡単に順列を生成できます。
shibh308さんのブログで紹介されているものを現在解いていっていますが、今のところ一番学ぶことができた問題でした。
このようにfor文を多用するとコードが長くなるので、defineする方法も覚えました。便利なので使っていきたいです。

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define REP(i, n) for(int i = 0;i < n;i++)
#define RE(i, n) for(int i=1;i<=n;i++)
int main(){
        long N,M,R;
        long d[201][201]={0};
        cin>>N>>M>>R;
        vector<long> r(R);
        REP(i,R)
                cin>>r[i];
        sort(begin(r),end(r));
        RE(i,N){
                RE(j,N){
                        if(i!=j)
                                d[i][j]=INF;
                }
        }
        REP(i,M){
                long a,b,c;
                cin>>a>>b>>c;
                if(d[a][b]==INF)
                        d[a][b]=d[b][a]=c;
        }
        RE(k,N){
                RE(j,N){
                        RE(i,N)
                                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
        }
        unsigned long min=-1;
        do{
                long sum=0;
                REP(i,R-1)
                        sum+=d[r[i]][r[i+1]];
                if(sum<min)
                        min=sum;
        }while(next_permutation(begin(r),end(r)));
        cout<<min;
}

参考URL:
ワーシャルフロイド法とその例題 - ゆらのふなびと
順列生成 next_permutation, prev_permutation 入門
競技プログラミング for beginners! ~C++実装テク編~ - 西から昇って東に沈むアレ

ABC088 D - Grid Repainting

初めて幅優先探索を使用する問題を解いてみました。
最短の道を通り、残りの白い面を埋めればACという考え方です。
幅優先探索自体は知っていたのですが、最初に見つかったゴールが最短ということを忘れており、チェックするのめんどくさいと投げ出してしまいした。
また以下の迷路外の例外処理をcontinueではなく、breakにしていたせいで小一時間ほど悩んでしまいました。

if(ttx<0||ttx>=w||tty<0||tty>=h)
       continue; //breakにすると、残りの選択肢を探索しなくなる
#include<bits/stdc++.h>
using namespace std;
#define FF 99999
#define P pair<int,int>
int main(){
        int h,w;
        cin>>h>>w;
        vector<string> m(h);
        int sum=0;
        for(int i=0; i<h; i++){
                cin>>m[i];
                for(int j=0; j<w; j++){
                        if(m[i][j]=='.')
                                sum++;
                }
        }
        sum-=1;
        vector<vector<int>> route(h,vector<int>(w,FF));
        route[0][0]=0;
        queue<pair<int,int>> now;
        now.push(P(0,0));

        while(!now.empty()){
                P ax;
                ax=now.front(),now.pop();
                int tx=ax.first,ty=ax.second;
                if(tx==w-1&&ty==h-1){
                        cout<<sum-route[h-1][w-1];
                        return 0;
                }
                int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
                for(int i=0; i<4; i++){
                        int ttx=tx+dx[i],tty=ty+dy[i];
                        if(ttx<0||ttx>=w||tty<0||tty>=h)
                                continue;
                        if(m[tty][ttx]=='.'&&route[tty][ttx]==FF){
                                route[tty][ttx]=route[ty][tx]+1;
                                now.push(P(ttx,tty));
                        }
                }
        }
        cout<<-1;
}