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

憶測が多いブログなので鵜呑みにしないこと

ABC071 D - Coloring Dominoes

リハビリがてら解いた一問
特別な知識が必要ない問題です。ドミノの置き方のパターンを考えればOKです。
結論を言いますと、一番左のドミノが上下に積まれていれば6倍、一本ならば3倍。
上下にドミノが積まれている場合、左も上下に積まれていれば場合の数は3倍、一本ならば2倍。
ドミノが一本の場合、左が上下に積まれていれば1倍、一本ならば2倍に場合の数が増えていきます。
f:id:benntann:20181113202622p:plain
セルに書かれた番号を乗算したものだけ場合の数が増えます。 上が一番左のドミノが2つのドミノで構成される場合で、下が一番左のドミノが1つのドミノで構成される場合です。
一番左以降のパターンはどちらの状況で始まっても同じだけ場合の数が増加します。
最初のドミノの積み方の場合の数を考えます。 一番左のドミノが別々の場合、上のドミノは一番最初のドミノなので何色を選んでも自由です。そのため3つの選択肢があります。下のドミノは、上のドミノが選んだ色以外の色を選択しなくてはなりません。そのため、場合の数は2倍されます。
一方、一番左のドミノが1つだけで始まる場合は、何の縛りがないため3つの選択肢があります。
次に最初のドミノ以外の場合の数を考えます。
上の図の場合、左から二番目のドミノは上下に積まれています。この場合、上のドミノは左のドミノの色のみに縛られますので、場合の数は二倍されます。次にその下のドミノは、上のドミノと左のドミノに色を縛られます。上と左のドミノの色が異なる場合は、選択肢が1つになりますが、同じ場合は選択肢が2つになります。この場合の場合の数は、一番左上の色が赤(R)だとすると、その右と下のドミノは(G,B)、(B,G)、(G,G)、(B,B)の4パターンで、このうち選択肢が二つになるものは(G,G)と(B,B)です。合計6パターンに増加しているため、6/4=3/2のため場合の数は3/2倍になります。
よって一番左のドミノ以外のドミノで、上下に積み重なっているドミノがあり、その左側も上下に積み重なっていれば、上のドミノで2倍、下のドミノで3/2倍になるため、場合の数は3倍になります。一方で下の図の左から二番目のように、左側が1つのドミノであれば、下のドミノが隣接するドミノが同じ色になることはないため、場合の数は、上のドミノで2倍、下のドミノで1倍となります。
上の図の左から三番目のようにドミノが1本の場合を考えます。上の図の左から三番目の場合は、左の2つのドミノに色が縛られます。そのため、場合の数は1倍になります。一方その隣のように、左のドミノも1本であれば、1つのドミノにのみ色が縛られるため、場合の数は2倍になります。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    string s1,s2; cin>>s1>>s2;
    int i=1;
    long sum=3;
    if(s1[0]!=s2[0]){
        i++;
        sum*=2;
    }
    while(i<n){
        bool jud=(s1[i-1]==s2[i-1]);
        if(s1[i]==s2[i]){
            if(jud)
                sum*=2;
            i++;
        }
        else{
            if(jud)
                sum*=2;
            else
                sum*=3;
            i+=2;
        }
        sum%=(int)(1e9+7);
    }
    cout<<sum;
}

このコードだと、sumintにした場合、途中でオーバーフローしました。このような問題はやはりlongを使うと安全だと思います。

ABC113 D - Number of Amidakuji

こちらに詳細を書きます。解法はDPです。データ構造はdp[i][j]で、問題の画像でいうところの、ind rowでjにたどり着ける場合の数です。
例えば以下の画像でj=1の線にいるとします。ここで、このポイントから移動できるのは、1から2へ線を引いた時のj=2と、1から0へ線を引いた時のj=0、そしてこの2つの線をどちらも引かなった場合のj=1です。
f:id:benntann:20181105174112p:plain
基本的にはこのパターンで、dp[i-1][j]の場合の数をdp[i][j-1],dp[i][j+1],dp[i][j]にコピーすればよいです。
しかし、他にも線を引けるところが残っている場合、線を引くパターン分だけ乗算する必要があります。 以下の画像では、矢印の移動を行ったとき、他に線を引くことができる箇所を同じ色の四角で示しています。
f:id:benntann:20181105174751p:plain
線を引く場合、線が隣り合わないことが条件なのですが、どのように引ける数のパターンを計算するかというと、線を引く時を1、引かない時を0とした二進数と考えるといいです。
最大のパターンがw=8のとき、0もしくは7の線にいるときに移動しないときの26です。しかし1が連続するbitは存在できないので、実際にはもっと少ないです。そのため計算してしまえば良いです。
もう線を引く場所がないときは、i-1番目のjをそのまま持ってくるので1パターン
1つ線を引く場所があるときは、0と1の2パターン
2つ線を引く場所があるときは、00、01、10の3パターン
3つ線を引く場所があるときは、000、001、010、100、101の5パターン
とみていくと結果として、0から6まで1,2,3,5,8,13,21となります。つまりこれらを掛けただけ増やすことができます。
よく見るとこれは漸化式でa1=1,a2=2,ai=a(i-1)+a(i-2)と表せます。そのためwが8より大きな制約でもこれを解くことができます。なぜこの漸化式になるのかはbitの生成パターンを見ればわかると思いますので、考えてみてください。
あとは移動する線を引いた後、左にいくつ線が引けるのか、右にいくつ線が引けるのかを確かめ、それぞれの場合の数を求めるだけです。
例えば上の画像の左から3番目にいるときを考えます。
左に移動しようとすると、赤い四角で囲ってあるように、移動する線より右側に2つ線が引けますので、
dp[i][4]+=dp[i-1][3]*3
右に移動しようとすると、右側に1つ、左側に1つそれぞれ線が引けますので、
dp[i][2]+=dp[i-1][3]*(2*2)
どこにも移動しないようにすると、右側に2つ、左側に1つそれぞれ線が引けますので、
dp[i][3]+=dp[i-1][3]*(3*2)
このようにDPを行っていきます。
そして最後のdp[h][w](自分のプログラムではdp[h][w-1])に結果が出てきます。

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000007
int main(){
    int h,w,k; cin>>h>>w>>k;
    vector<vector<long>> dp(h+1,vector<long>(w,0));
    dp[0][0]=1;
    int num[]={1,2,3,5,8,13,21};
    for(int i=1;i<=h;i++){
        for(int j=0;j<w;j++){
            int l=j-1,r=w-1-(j+1);
            if(l<0)
                l=0;
            if(r<0)
                r=0;
            int a=num[r];
            if(l-1>=0)
                a*=num[l-1];
            int b=num[l];
            if(r-1>=0)
                b*=num[r-1];
            if(j-1>=0)
                dp[i][j-1]+=(dp[i-1][j]*a)%INF;
            if(j+1<w)
                dp[i][j+1]+=(dp[i-1][j]*b)%INF;
            int n=num[r]*num[l];
            dp[i][j]+=(dp[i-1][j]*n)%INF;
        }
    }
    cout<<dp[h][k-1]%INF;
}

因みに上記のような剰余を行うとDPを保存する配列をintにした場合途中でオーバーフローしました。

ABC113 所感

お疲れ様です。beta版がめちゃくちゃ重いコンテストでした。最近あまりこちらにモチベーションがないのと、これの影響であまり集中してできませんでした(言い訳)

A - Discount Fare

半額になるほうを半額にして出力

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x,y; cin>>x>>y;
    cout<<x+y/2;
}

B - Palace

差分の最小値とその要素番号を保存して、入力毎に比較します。最小値だけでよい場合は、全てのデータを保存する必要がありません。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,t,a; cin>>n>>t>>a;
    double min = 1e10;
    double ele =0;
    for(int i=0;i<n;i++){
        double h; cin>>h;
        double nc=(double)t-h*0.006;
        if(fabs(a-nc)<min){
            min=fabs(a-nc);
            ele=i+1;
            
        }
    }
    cout<<ele;
}

C - ID

入力した市iの属する県番号と誕生年をvectorに保存して、誕生年でソートしたコピーを作成します。
このコピーを基に、1つの年には最大で1つの市が生まれていることを利用して、年をキーにしたmapに県の番号と、何番目に生まれたかを記録しています。(あとで気が付きましたが、年をキーとした県番号を割り出すmapは必要ありません)その県に対して何番目に生まれたかというのは、県別にカウンタを保持して実装しています。
最初の実装として県別の配列を作成し、それらをソートしてfindを使用して割り出していたのですが、TLEしたのでmapにて記録しています。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m; cin>>n>>m;
    vector<pair<int,int>> v;
    for(int i=0;i<m;i++){
        int p,y; cin>>p>>y;
        v.push_back(pair<int,int>(p,y));
    }
    vector<pair<int,int>>cv = v;
    sort(begin(cv),end(cv),[](auto x, auto y){return x.second<y.second;});
    map<int,int> ken;
    map<int,int> num;
    vector<int> el(n+1,1);
    for(auto x:cv){
        ken[x.second]=x.first;
        num[x.second]=el[x.first];
        el[x.first]++;
    }
    for(auto x:v){
        printf("%06d%06d\n",ken[x.second],num[x.second]);
    }
}

D - Number of Amidakuji

解けませんでした。DPかなという予想です。明日できたら更新します。
(2018/11/5 更新) 別記事にて解説しました。よろしければそちらを参照してください。

everydaytekitou.hatenablog.com

総括

前回よりはパフォーマンスが絶対落ちていると思いますが、C問をちゃんと解けたので良かったです。サーバーが非常に重かったことが残念でした。

ABC104 D - We Love ABC

DPが本当に苦手なので解説も放送も野良解説も訳がわからなく苦労した問題。
i番目の文字に対して以下の情報を保存しながらDPします
0. i番目までで1つも文字を選ばない組み合わせ
1. i番目までで"A"までを選ぶ組み合わせ
2. i番目までで"AB"までを選ぶ組み合わせ
3. i番目までで"ABC"までを選ぶ組み合わせ
i番目の文字が'A'だったとき、上記の1の要素を増やすことができます。それ以外は不変です。どれだけ増えるかというと、i-1番目の0の要素の数だけです。
BとCの場合も同様に考えることができます。
次にi番目の文字が'?'だったときは、二通りの増やし方ができます。
1つ目は、'?'が'ABC'の文字を担って"ABC"を構築しようとするときです。このときは、A,B,Cと同じ考え方で大丈夫です。
2つ目は、'?'が文字の構築に関与しないときです。これはA,B,Cの3つがはいるため、i-1番目のそれぞれの要素を3倍して加算してやればよいです。
具体例を考えます。入力例1のA??Cの場合、DPの遷移は以下のようになります。
A
0. 1
1. 1
2. 0
3. 0
0. Aを選ばないときの1通り
1. このAから文字列を構築し始める場合の1通り
?
0. 3
1. 4
2. 1
3. 0
0. AA、AB、AC、のときにこれらの文字列から文字の構築をしない場合の3通り
1. この?を文字の構築に考慮させず、最初のAで文字を作り始めるときの3通り+最初のAを考慮せずこの?をAにして、文字を作り始める1通り
2. ?をBに割り当てて作る1通り
?
0. 9
1. 15
2. 7
3. 1
0. この?をA,B,Cにしたとき(前の0の3倍)
1. この?を文字の構築に考慮させない場合(前の三倍)+前の2文字を考慮せず、この?で文字を作り始める場合(前の0番目の要素)
以下略
C
0. 9
1. 15
2. 7
3. 8
こんな感じで、最後のdp[N][3]に解がでます。
DP云々っていうよりも数学の組み合わせの問題という面が強いような気がします。このあたりの分野もすごく苦手なのでなんとかしたいです。

#include <bits/stdc++.h>
using namespace std;
#define INF (long)(1e9+7)
int main(){
    string s; cin>>s;
    vector<long[4]> dp(s.size()+1); 
    dp[0][0]=1;
    for(int i=1;i<=s.size();i++){
        for(int j=0;j<=3;j++){
            dp[i][j]=dp[i-1][j];
            if(s[i-1]=='?')
                dp[i][j]*=3;
            dp[i][j]%=INF;
        }
        if(s[i-1]!='?')
            dp[i][s[i-1]+1-'A']+=dp[i-1][s[i-1]-'A'];
        else{
            for(int j=1;j<=3;j++){
                dp[i][j]+=dp[i-1][j-1];
               dp[i][j]%=INF;
            }
        }
    }
    cout<<dp[s.size()][3]%INF;
}   

参考:
AtCoder Beginner Contest 104 - Unhappy Go Lucky!

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

参考:
尺取り法