トップ > Codeforces > Codeforces Round #338 (Div. 2)

Codeforces Round #338 (Div. 2)

Codeforces

結構悲惨だったけど、Good Byeよりマシか。

A. Bulbs

問題概要

手元にいくつかのスイッチがあり、各スイッチはいくつかのランプにつながっている。最初は全部のランプが消えているとき、 手元にあるスイッチを押して全部のランプをつけることができるか判定せよ。
Problem - A - Codeforces

解説

既についているランプは消えることが無いので、スイッチを全部押してしまいましょう。 自分はboolの配列を使ってランプがついているか判定させましたが、setを使って入れていくor取り除く方法も簡潔そうです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;   cin>>n>>m;
    bool on[m];
    for(int i=0;i<m;i++) on[i]=false;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        for(int j=0;j<x;j++){
            int y; cin>>y;
            on[y-1]=true;
        }
    }
    for(int i=0;i<m;i++){
        if(!on[i]){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

B. Longtail Hedgehog

問題概要

ハリネズミは胴体と針で構成されていて、胴体は頭から尾までグラフ上の頂点が単調増加な路、針はハリネズミの尾から伸びる長さ1の道である。
ハリネズミの美しさが（胴体に含まれる頂点数）×（針の数）の時、最も美しいハリネズミの美しさを答えよ。
（リンクの例を見ると分かりやすいです）

Problem - B - Codeforces

解説

胴体に含まれる頂点数とその頂点に含まれる針の数を別々に考えます。]

胴体は頭から尾まで単調に増加します。よって頂点1から頂点Nまでループを回し、その中でつながっている頂点の番号が今見ている番号より大きいなら繋がっている頂点を尾とした時の胴体に含まれる頂点数＝max(そのまま、今見てる頂点を尾とした時の胴体+1)と更新していけばOKです。

頂点iを尾とした時の針の数は頂点iに接続している頂点数に等しいです。

あとはこれらの積の最大値を求めればOKです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;   cin>>n>>m;
    vector<int> edge[n];
    vector<int> cnt(n,0);
    for(int i=0;i<m;i++){
        int a,b;   cin>>a>>b;  a--;    b--;
        if(a>b)    swap(a,b);
        edge[a].push_back(b);
        cnt[b]++;   cnt[a]++;
    }
    vector<int> level(n,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<(int)edge[i].size();j++){
            level[edge[i][j]]=max(level[edge[i][j]],level[i]+1);
        }
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        ans=max(ans,(long long)level[i]*cnt[i]);
    }
    cout<<ans<<endl;
    return 0;
}

自分は頂点番号の小さい→大きいへ有向辺を張って、「その頂点への最も長い道の長さ」を求めてました。

C. Running Track

問題概要

文字列s,tが与えられる。sの部分列とそれを反転したものを組み合わせてtを作りたい。最小でいくつの部分列を足せば良いか。

Problem - C - Codeforces

解説

取り敢えず例を1つ。s="abcdbcde",t="abcde"のとき、答えは2ですが、1通りではありません。"abcd"+"e","abc"+"de","ab"+"cde","a"+"bcde"のどれでも正解です。ここでは最初に貪欲に選ぶ手法を取って行きましょう。

tのi文字目を見ているときに、何文字先に進めるのか、というDPをすれば通るのかなぁ…と思いやってみたらO(|S||T|min(|S|,|T|))。TLEしました。ローリングハッシュとかも浮かんだけど、実装したことない。そのままタイムアップでした。

ということでkmjpさんの解説を拝見。

自分はDPを1次元でやりましたが、2次元で「tのi文字目、sのj文字目を先頭とする文字列が何文字一致するのか」を求めるのが正解のようです。LCSとか久しぶりに聞きました。よくLCAと見間違えます。

その後、tを1文字目から再現していくのですが、i文字目以降が作られていない時、先ほどの配列からtがi文字目の時、ループを回してsが何文字目から始まる時最も先へ進めるのかを調べます。1文字も先へ進めない時はtを作ることは出来ません。

#include <bits/stdc++.h>
using namespace std;
int dp[2][2110][2110];//rev:s.size:t.size
int main(){
    string s,t; cin>>s>>t;
    for(int i=s.size()-1;i>=0;i--){
        for(int j=t.size()-1;j>=0;j--){
            if(s[i]==t[j])    dp[0][i][j]=dp[0][i+1][j+1]+1;
            if(s[s.size()-1-i]==t[j])    dp[1][i][j]=dp[1][i+1][j+1]+1;
        }
    }
    vector<pair<int,int>> ans;
    int cur=0;
    while(cur<t.size()){
        int tmp=0;
        pair<int,int> add;
        for(int i=0;i<s.size();i++){
            if(dp[0][i][cur]>tmp){
                tmp=dp[0][i][cur];
                add=make_pair(i+1,i+dp[0][i][cur]);
            }
            if(dp[1][i][cur]>tmp){
                tmp=dp[1][i][cur];
                add=make_pair(s.size()-i,s.size()-i-(dp[1][i][cur]-1));
            }
        }
        if(tmp==0){
            cout<<-1<<endl;
            return 0;
        }
        cur+=tmp;
        ans.push_back(add);
    }
    cout<<ans.size()<<endl;
    for(auto i:ans)  cout<<i.first<<" "<<i.second<<endl;
    return 0;
}

文字列操作に弱い自覚はあるけど、何とかしておきたい。

D. Multipliers

問題概要

巨大な数を素因数分解した後の積を数列として与えるので、元の数の約数全てをかけ合わせたものを1e9+7で割った余りを求めてください。

Problem - D - Codeforces

解説

これも「各因数毎に何回かけるのか」が分かれば簡単だよな…とか思いつつやっていました。が、それ以降思いつきませんでした。

C同様kmjpさんの解説を拝見。

まずは数列を整理し、p[i]^q[i]という表示形式にします。

ここで、p[i]^1を含む（p[i]^2以降は含めない）は全体の積の中でp[i]を用いない積の総数、つまりj!=iでの(q[j]+1)の積（=Q[i]とします)になります。この値はp[i]^2でもp[i]^3でも同じなので、p[i]は合計でQ[i]+2Q[i]+...+q[i]Q[i]=Q[i]×q[i](q[i] +1)/2回かけられています。(長いのでP[i]とします）

後はp[i]^P[i]を答えにかけ合わせればいいのですが、Q[i]はそのまま計算すると最大20万20万なのでオーバーフローします。

m=1e9+7とおいておくと、
フェルマーの小定理（a,pが互いにその時、ap≡a(mod p)）で、p[i]^(m-1)≡1(mod m)となるので、P[i]はm-1でのmodを取ってあげれば良さそうです。同様にQ[i]もm-1でmodを取ります。

しかし、mは素数なので確実にフェルマーの小定理が成り立つのですが、m-1は偶数なのでほとんど成り立ちません。こうするとQ[i]を求めるときに「先に全体の積を求めておいて、そこから(q[i]+1)で割る」という方法が取れません。
(mが素数だったらam-2×a≡1(mod m)より、am-2と1/aが同じ役割を果たします)

そこで、L[i]:(q[0]+1)〜(q[i-1]+1)の積、R[i]:(q[i+1]+1)〜(q[n-1]+1)の積とおいて、L[i]×R[i]=Q[i]とすればOKです。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll pows(ll a,ll b){
    ll ret=1;
    while(b){
        if(b%2==1)  ret=ret*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ret;
}
    
int main(){
    int n; cin>>n;
    map<ll,ll> p;//first^second
    for(int i=0;i<n;i++){
        ll a;   cin>>a;
        p[a]++;
    }
    vector<pair<ll,ll>> ls;
    for(auto i:p)    ls.push_back(i);
    vector<ll> left(ls.size()+1),right(ls.size()+1);
    left[0]=1;    right[ls.size()]=1;
    for(int i=1;i<=(int)ls.size();i++)  left[i]=(left[i-1]*(ls[i-1].second+1))%(mod-1);
    for(int i=ls.size()-1;i>=0;i--) right[i]=(right[i+1]*(ls[i].second+1))%(mod-1);
    ll ans=1;
    for(int i=0;i<(int)ls.size();i++){
        auto it=ls[i];
        ll tmpM=left[i]*right[i+1]%(mod-1);
        ll b=it.second*(it.second+1)/2%(mod-1);
        b=b*tmpM%(mod-1);
        ans=(ans*pows(it.first,b))%mod;
    }
    cout<<ans<<endl;
    return 0;
}

感想

2完。つらい。
ふと気がついたけどTopCoderよりCodeforcesの方が英語が難しい？

寝坊して学校に遅刻しかけたので、「前日の競プロの出来が翌日の朝起きられるかどうかに影響する」という命題が真としか思えない。過去にも1度イベントで遅刻しています。