Help us understand the problem. What is going on with this article?

Codeforces Round #486 (Div. 3) バチャ復習(9/23)

今回の成績

スクリーンショット 2020-09-23 16.46.13.png

今回の感想

D問題を永遠にバグらせていたら一時間半を無駄にしました。E問題も面倒だと思って避けましたが、結果的に場合分けをきっちりしていけばupsolveできたので悔しい限りです。D,E問題共にコーナーケースやバグを発見することができなかったのも今までの反省が生かせていないので次に生かせるように頭の中を整理しておこうと思います。

A問題

レーティングが異なるようにしたいので、set構造でレーティングの種類数を数えて$k$を超えるか判定します。$k$以上の場合は適当な$k$個を出力します。ここでは実装が楽になるようにindexを使いましたが、計算量的には別の方法が良いです(ここでは紹介しませんが$O(k)$でできます)。

A.py
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(set(a))
if len(b)>=k:
    print("YES")
    ans=[]
    for i in range(k):
        ans.append(a.index(b[i])+1)
    print(" ".join(map(str,ans)))
else:
    print("NO")

B問題

題意を満たす文字列の順番がある時、(最初の文字列を除く)任意の文字列は直前の文字列を部分列として持つので、この文字列の順番は長さの昇順になります($\because$背理法により示せます。)。

よって、与えられた文字列を長さの昇順に直し、それぞれ直前の文字列に含むかをinによって判定すれば良いです。この時、計算量は$O(N^2)$となります。

B.py
n=int(input())
a=[input() for i in range(n)]
a.sort(key=lambda x:len(x))
for i in range(n-1):
    if a[i] not in a[i+1]:
        print("NO")
        break
else:
    print("YES")
    for i in range(n):
        print(a[i])

C問題

二つのsequenceを選んでそれぞれから一つずつ要素を抜き出して和が同じものを見つけます。ここで、$i$番目の長さ$n_i$のsequenceから一つ要素を抜き出す和はどの要素を抜き出すかで$n_i$通りあります。また、制約より$\sum_{i=1}^{k}{n_i} \leqq 2 \times 10^5$なので、この和は全列挙することができます

ここで、$i$番目の長さ$n_i$のsequenceの$j$番目の要素を抜き出した時の和は($i$番目のsequenceの和)-($j$番目の要素の値)となり、それぞれのsequenceの和を予め求めておけば、$O(\sum_{i=1}^{k}{n_i})$で求めることができます。また、keyをsequenceの和の値,valueを"その値になる(sequenceのインデックス,抜き出した要素のインデックス)"を保存したvectorとして辞書$m$を置けば、先ほど求めたsequenceの和を順に格納することができます。また、この際にkeyが等しいものの中でsequenceのインデックスが異なるものが二つ以上あれば答えとして出力することができます。逆に二つ以上あるものが一つもない場合はNoを出力すれば良いです。

(気づかなかったですが、Pythonでも書けましたね。なぜC++で書いたのでしょうか…?)

C.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

signed main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll k;cin>>k;
    map<ll,vector<pair<ll,ll>>> m;
    REP(i,k){
        ll ni;cin>>ni;
        vector<ll> a(ni);REP(j,ni)cin>>a[j];
        ll s=0;REP(j,ni)s+=a[j];
        REP(j,ni){
            m[s-a[j]].PB(MP(i+1,j+1));
        }
    }
    FORA(i,m){
        if(SIZE(i.S)>1){
            map<ll,ll> x;
            //同じ数列被り排除
            FORA(j,i.S){
                x[j.F]=j.S;
            }
            if(SIZE(x)>1){
                auto y=x.begin();
                cout<<"YES"<<endl;
                cout<<y->F<<" "<<y->S<<endl;
                y++;
                cout<<y->F<<" "<<y->S<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
}

D問題

(UnionFindによる操作はほぼ定数とみなして計算量を表記しています。)

全体から部分集合を選ぶというイメージで行うと沼にハマってしまうかもしれません。ここでは、二つの点の距離が$2^d$かつ最大で$2 \times 10^9$なので、$d=$0~30のみを調べれば良いことに注目します。

この時、それぞれの$d$について最大の部分集合を求めることを考えます。また、ある点$x$に注目した時$2^d$だけ離れている点は$x-2^d,x+2^d$であり、全ての点をsetで管理すれば離れている点が存在するかを$O(\log{n})$で確かめることができます(任意の点で調べれば$O(n \log{n})$)。したがって、UnionFindを用いて間が$2^d$離れている点どうしをつないでいくことで下図のような点の部分集合がいくつかできます。

IMG_0642.JPG

また、上図の部分集合に含まれる点は全て題意を満たすような部分集合に含まれるとしたいのですが、高々3つの点までしか含めることができません。なぜなら、3つより点が大きい場合は距離が2の冪乗にならない点の組が必ず含まれるからです。

以上より、$d=$0~30それぞれでUnionFindを行って(集合内の要素を昇順に並べると座標の間隔が$2^d$である)素集合系を求め、要素数が三以上の集合が少なくとも一つある場合はその集合を昇順で並べた時に隣合う三つの点を出力し、(前述の条件を満たさず)要素数が2のものが少なくとも一つある場合はその集合に含まれる二点を出力し、それ以外の場合は適当な一点を出力すれば良いです。

また、点同士をuniteする場合にindexを指定したかったので値に対してのインデックスを与えるmapとしてindを用意し、出力の際にインデックスから要素の値に直すためのvectorとしてvalを用意しました。また、UnionFindで得られた集合はインデックスの昇順になっているので、値の昇順と一致させるためにvalを昇順に直してからindに格納する必要があります。(昇順のソートをしていなかったのに気づかず、デバッグに数時間かかりました…。考察段階では気づいていたミスなので、焦ったときは自分の考察と照らし合わせるようにしたいです。)

9/25追記

実は高々三つであることにのみ注目すれば横を見れば良いだけで実装も軽く高速に実装できます。これに気づいていればと思うと悔しいです。二つ目のPythonのコードを参照してください。

D.cc
//デバッグ用オプション:-fsani

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//以下、素集合と木は同じものを表す
class UnionFind {
public:
    vector<ll> parent; //parent[i]はiの親
    vector<ll> siz; //素集合のサイズを表す配列(1で初期化)
    map<ll,vector<ll>> group;//素集合ごとに管理する連想配列(keyはそれぞれの素集合の親、valueはその素集合の要素の配列)
    ll n;//要素の個数

    //コンストラクタ
    UnionFind(ll n_):parent(n_),siz(n_,1),n(n_){ 
        //全ての要素の根が自身であるとして初期化
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //データxの属する木の根を取得(経路圧縮も行う)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//代入式の値は代入した変数の値なので、経路圧縮できる
    }

    //xとyの木を併合
    void unite(ll x,ll y){
        ll rx=root(x);//xの根
        ll ry=root(y);//yの根
        if(rx==ry) return;//同じ木にある時
        //小さい集合を大きい集合へと併合(ry→rxへ併合)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//xとyが同じ木にない時はyの根ryをxの根rxにつける
    }

    //xとyが属する木が同じかを判定
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //xの素集合のサイズを取得
    ll size(ll x){
        return siz[root(x)];
    }

    //素集合をそれぞれグループ化
    void grouping(){
        //経路圧縮を先に行う
        REP(i,n)root(i);
        //mapで管理する(デフォルト構築を利用)
        REP(i,n)group[parent[i]].PB(i);
    }

    void clear(){
        for(ll i=0;i<n;i++){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    set<ll> x;
    //値に対してのind
    map<ll,ll> ind;
    //indに対しての値
    vector<ll> val(n);
    REP(i,n){
        ll y;cin>>y;
        x.insert(y);
        val[i]=y;
    }
    sort(ALL(val));
    REP(i,n){
        ind[val[i]]=i;
    }
    vector<ll> v(1,0);
    pair<ll,vector<ll>> ans=MP(1,v);
    UnionFind uf(n);
    REP(i,31){
        uf.clear();
        FORA(j,val){
            if(x.find(j+(1LL<<i))!=x.end()){
                uf.unite(ind[j],ind[j+(1LL<<i)]);
            }
        }
        uf.grouping();
        for(auto j=uf.group.begin();j!=uf.group.end();j++){
            if(SIZE(j->S)>ans.F){
                //3は超えない
                //sortされてない(valは)はー???????
                if(ans.F==1){
                    if(SIZE(j->S)==2){
                        vector<ll> w(2);
                        w={j->S[0],j->S[1]};
                        ans=MP(2,w);
                    }else{
                        cout<<3<<endl;
                        cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
                        return 0;
                    }
                }
                if(ans.F==2){
                    if(SIZE(j->S)>2){
                        cout<<3<<endl;
                        cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout<<ans.F<<endl;
    REP(i,ans.F){
        if(i==ans.F-1){
            cout<<val[ans.S[i]]<<endl;
        }else{
            cout<<val[ans.S[i]]<<" ";
        }
    }
}
D.py
n=int(input())
x=list(map(int,input().split()))
y=set(x)
ans=[x[0]]
for d in range(31):
    e=2**d
    for i in range(n):
        if x[i]-e in y and x[i]+e in y:
            print(3)
            print(x[i]-e,x[i],x[i]+e)
            exit()
        elif x[i]-e in y:
            ans=[x[i],x[i]-e]
        elif x[i]+e in y:
            ans=[x[i],x[i]+e]
if len(ans)==2:
    print(2)
    print(ans[0],ans[1])
else:
    print(1)
    print(ans[0])

E問題

考察は難しくないですが、実装を詰め切るのが面倒な問題だと思いました。

まず、25の倍数となる条件は下二桁が$00,25,50,75$のいずれかになる時です。また、swapをしてできるだけ近いところにある数を持ってくれば良いのも自明です。しかし、最上位桁に与えられる数がある場合は最上位桁に0が来る可能性があるので、この時の場合分けをする必要があります。また、$00$の場合は唯一同じ数を二つ考えなければならないかつ最上位桁に与えられる数があることがないので、他の三つとは分けて考えることにしました。

まず、一桁のみの場合は場合分けが面倒なので予め-1を出力します。そして、二桁で成り立つ場合も場合分けがしにくかった(WAも出した)ので、$25,75,50$の場合は0を$52,57$の場合は1を出力します。

この元で$25,50,75$を最下位桁に持ってくるのに必要なswapの最小回数を求めます。ここで、最小回数を求める関数を$calc1$とし、引数は$x,y$とします($(x,y)=(2,5),(5,0),(7,5)$)。まず、swapの際には最下位桁からどれだけ離れているかを知りたいので、与えられた数を数の配列と見て反転します(反転したものを$m$とします)。ここで、$x,y$がいずれも桁に含まれてない場合は最小回数は存在しないので$inf$を返します。この元で、$m$における$x,y$のインデックスを$ix,iy$として求めます。また、$x,y$のいずれも一番右側(最上位桁)にない場合、最下位桁に近い方($ix,iy$の小さい方)から順にswapするのが最適で、$ix<iy$の場合は最下位桁の反転がこのままでは起きているのでさらに一回のswapが必要です。

次に、いずれかが一番右側にある場合を考えますが、$x,y$のどちらでも最下位桁の間のswap以外は全て同じ操作なので、$x$が一番右側の時を以下では考えます。$x$が一番右側の時、最上位桁から下の桁へと見ていって0でないかつそのインデックスが$iy$でない初めの要素を選択して最上位の桁とのswapをするのが最小回数として最適なので、そのswapを行います。また、0でないかつそのインデックスが$iy$でない要素が存在しない場合は$inf$を返します(初めに場合として除いた$25,75,50,52,57$はこれを満たさないので先に場合分けしました。)。そして、この桁を$i$とすれば最上位の桁との交換回数は簡単に求めることができます。また、$i<iy$である場合は$i$を上位桁へと運ぶ際のswapで$iy-=1$されるので注意が必要です。よって、最上位桁とのswapを行うことができれば、$iy$をswapしてその後に$ix$をswapすればよく、合計のswapの回数を数えれば良いです。

また、最下位桁を$00$にする場合は最下位桁から近い$00$のインデックスを求めて近い方から最下位桁へと近づければよく、最下位桁が異なることによるswapも発生しないので簡単な実装になります。

以上より、$00,25,50,75$のそれぞれの場合についての最小回数を求めることができその中での最小回数を求めますが、仮にその最小回数が$inf$の場合は-1を出力する必要があります。

意外と考察しきればそこまで実装の重くない問題でした。このような問題は無心に実装できるよう頑張りたいです。

E.py
n=[int(i) for i in input()]
l=len(n)
#長さが2の場合も
if len(n)==1:
    print(-1)
    exit()
#これだけの場合
if n in [[2,5],[7,5],[5,0]]:
    print(0)
    exit()
if n in [[5,2],[5,7]]:
    print(1)
    exit()
inf=10**12
#一番左にある場合はめんどいので場合分けしちゃう(逆にする)
#00も場合分け
def calc1(x,y):
    global n,l,inf
    m=n[::-1]
    if x not in n or y not in n:
        #print(x,y,0)
        return inf
    ix,iy=m.index(x),m.index(y)
    #一番右にない場合
    if max(ix,iy)<l-1:
        if iy<ix:
            #print(x,y,1)
            return iy+(ix-1)
        else:
            #print(x,y,2)
            return iy+(ix-1)+1
    else:
        ret=0
        #print(ix,iy)
        if ix==l-1:
            #右から探して左を見る(0かつ他の選択するやつでない)
            for i in range(l-2,-1,-1):
                if m[i]!=0 and i!=iy:
                    break
            else:
                #print(x,y,3)
                return inf
            if i<iy:
                iy-=1
                ret+=(l-1-i)
                ix-=1
                ret+=(iy+(ix-1))
                #print(x,y,4,ret)
                return ret
            else:
                ret+=iy
                ret+=(l-1-i)
                ix-=1
                ret+=(ix-1)
                #print(x,y,5,ret)
                return ret
        else:
            #右から探して左を見る(0かつ他の選択するやつでない)
            #他の選択するやつだけの可能性(最初に排除)
            #外でやる
            for i in range(l-2,-1,-1):
                if m[i]!=0 and i!=ix:
                    break
            else:
                #print(x,y,6)
                return inf
            if i<ix:
                iy-=1
                ret+=(l-1-i)
                ix-=1
                ret+=(iy+(ix-1)+1)
                #print(x,y,7,ret)
                return ret
            else:
                ret+=iy
                ret+=(l-1-i)
                ix-=1
                ret+=((ix-1)+1)
                #print(x,y,8,ret)
                return ret
#00の時
def calc2(x,y):
    #一番右には絶対ない
    global n,l,inf
    if n.count(0)<2:
        return inf
    m=[l-1-i for i in range(l) if n[i]==0][::-1]
    return m[0]+m[1]-1

ans=min([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
#print([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
print(-1 if ans==inf else ans)

F問題

今回は飛ばします

DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away