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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 12/13/14

- 12 限定された素数

  • 問題概要

ある整数の区間[L,R]を選んだとき、その区間に含まれる全ての素数の各桁に使われる数字(0~9)を調べる。
0~10の整数N_1,,,N_nが与えられ、区間に含まれる全ての素数の桁にちょうどN_1,,,N_nのみが使われる[L,R]のうち、最大のR-Lを求めよという問題です。

  • 解説

あらかじめエラトステネスのふるいで50万までの素数を列挙しておきます。O(N \log \logN))なので計算は間に合います。
条件を満たす区間の最大長なのでしゃくとり法が使えそうです。
二つの素数[tex:p_L,p_r(p_l

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
bool isprime[5000001];
vector<int>prime;
bool num[500000][10] = { { false } };
int main(void){
    bool ans[10] = { false };
    int N,m;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> m;
        ans[m] = true;
    }
    for (int i = 2; i <= 5000000;i++)isprime[i] = true;
    for (int i = 2; i <= 5000000; i++){
        if (isprime[i]){
            prime.push_back(i);
            for (int j = i * 2; j <= 5000000; j += i)isprime[j] = false;
        }
    }
    for (int k = 0; k < (int)prime.size();k++){
        int q = prime[k];
        while (q){
            num[k][q % 10] = true;
            q /= 10;
        }
        
    }
    int ml=0, mr=-1;
    int l=0;
    bool cnt[10] = {false};
    for (int r = 0; r < (int)prime.size(); r++){
        bool f = true;
        bool g = true;
        for (int i = 0; i < 10; i++){
            cnt[i] |= num[r][i];
            if (ans[i] != cnt[i])g = false;
            if (ans[i] == false && cnt[i] == true)f = false;
        }
        if (f == false){
            for (int i = 0; i < 10; i++)
                cnt[i] = false;
            l = r + 1;
            continue;
        }
        
        if (g == true){
            int R = 5000000;
            if (r + 1 < (int)prime.size())R = prime[r + 1] - 1;
            int L = 1;
            if (l > 0)L = prime[l - 1] + 1;
            if (mr - ml < R - L)
            {
                mr = R, ml = L;
            //	cout << ml << " " << mr << " " << mr - ml << endl;
            }

        }
        
    }
    cout << mr - ml << endl;;
    return 0;
}

- 13 囲みたい!

  • 問題概要

H*Wマスのフィールドがあります。
各マスは数字が書かれていて、隣接する同じ数字のマスはマスの中心同士を線でつなぐことができます。
ある数字を選び、線を引いていきます。
(凹みを許す)K >4 角形が作れるかどうか判定しなさいという問題です。

  • 解説

凹みを許しているのである頂点からスタートしてBFSで線を引っ張っていったとき同じマスで衝突したら囲みとみなしてよいです。
数字が離ればなれになっている可能性もあるので最初にqueueに全ての頂点を入れておくのを忘れないようにしましょう。
各マスを1回のみ訪問するので計算量はO(1000+HW)

親を既訪問リストに保存して次回の訪問候補から外す処理をすることで解決したけどpairでの処理がそこそこ面倒だったので訪問候補の中の既訪問が二つ以上ならreturn trueとする実装のほうが楽だったかも

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, P> PP;
int H, W;
int M[110][110];
vector<list<P>> cd;
#define mp(a,b,c,d) make_pair( make_pair((a),(b)),make_pair((c),(d)) )

#define dir(xx,yy,x,y,i)(xx)=(x)+dir[(i)],(yy)=(y)+dir[(i)+1];

const int dir[] = { 0, 1, 0, -1, 0 };


bool bfs(int c){
    //cout << c << endl;
    queue<PP> que;
    for (auto &u : cd[c])
    if(M[u.first][u.second]==c){
        que.push(mp(u.first, u.second, -1, -1));
        M[u.first][u.second] *= -1;
        while (que.empty() == false){
            auto v = que.front(); que.pop();
            for (int i = 0; i < 4; i++){
                int xx, yy;
                dir(xx, yy, v.first.first, v.first.second, i);
                if ((xx != v.second.first) || (yy != v.second.second)){
                    if (M[xx][yy] == -c){
                        return true;
                    }
                    if (M[xx][yy] == c){
                        M[xx][yy] *= -1;
                        que.push(mp(xx, yy, v.first.first, v.first.second));
                    }
                }
            }
        }
    }
    return false;
}



int main(void){
    cd.resize(1010);
    cin >> W >> H;
    for (int i = 1; i <=H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin >> M[i][j];
            cd[M[i][j]].push_back(make_pair(i, j));
        }
    }

    for (int i = 1; i <= 1000; i++)
        if (cd[i].size() >= 4)
            if (bfs(i))
            {
                
                cout << "possible" << endl;
                return 0;
            }
    cout << "impossible" << endl;
    return 0;
}

- 14

  • 問題概要

N個の整数列a_1,a_2,,,a_Nがある。
a_iを固定しa_i+1,,,a_Na_iとの最小公倍数の小さい順でソートする。
これをi=1,,,Nまで繰り返したとき最終的な数列はどのようになっているか答えよという問題です。

  • 解説

全部ソートする必要はなく、最小公倍数の最小値がほしいのでlcmを求めるのにO(\log K)であることから普通に固定して最小値を求めてを繰り返してもC++なら間に合うみたいです。
これはyukicoderがJava向けに制限時間を5秒にしているからであって実際C++でも4秒ぐらいかかってしまうみたいです。

しかしもっと余裕に解く解法があります。
まず問題の制約から、最初の整数はa_1であることが確定するのでまずこれを出力します。
まず全てのa_iについて約数を列挙しておきます。
そのついでにjを約数にもつa_iを昇順に列挙しておきます。
a_iをあらかじめソートしておけば約数列挙と同時に行えます。

ここまで事前準備です。

a_1との最小公倍数について考えます。
a_1が約数kを持つとき,同じ約数kをもつa_mとの公倍数はa_1*a_m/kです。
これが最小公倍数とは限りませんが、同じ約数kを持つまだ固定されていない最小のa_mが候補に入ります。
これをa_1の全ての約数について求め、約数と同じ数の候補ができます。
その中のa_1*a_m/kの最小値は明らかに最小公倍数であり、最小公倍数の中の最小値です。
これをa_2,a_3,,,を固定したときも同様の操作を行うのですが、既に固定してしまった数字は候補から省く必要があるので、約数kをもつ整数の昇順のリストは双方向性リストで実現すると計算量がO(N \sqrt N)となります。
説明難しい。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;

//(1/約数,元の数)
typedef pair<int, int> P;


vector <list<int>> sorted(10001);
vector<list<int>>divisor(10000);
int main(void){
    int N;
    int A[10000];

    cin >> N;
    
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    sort(A + 1, A + N);
    
    for (int i = 0; i <N; i++)
    {
        for (int j = 1; j*j <= A[i]; j++)
        {
            if (A[i] % j == 0){
                divisor[i].push_back(j);
                sorted[j].push_back(i);
                if (j*j != A[i]){
                    divisor[i].push_back(A[i] / j);
                    sorted[A[i] / j].push_back(i);
                }
            }
        }
    }
    
    int now = 0;
    for (int i = 0; i < N-1; i++)
    {
        cout << A[now] << " ";
        int pivot = A[now];
        A[now] = -1;
        P res = make_pair(100000000, 10000);
        for (auto &div : divisor[now])
        {
           // cout<<"("<<div;
            while ((sorted[div].empty()==false) && (A[sorted[div].front()] == -1))
                sorted[div].pop_front();
            if (sorted[div].empty())continue;
            int k = sorted[div].front();
            res = min(res, make_pair(pivot*(A[k] / div), sorted[div].front()));
            //cout << "("<<A[k];
        }

        now = res.second;
        //cout << endl;
    }
    cout << A[now]<< endl;


    return 0;
}