Codeforces 665 -----

CF665A

リンク

CF665Aの問題文

A市とB市はバスで結ばれており、最初の運行は朝5:00から、最終便は夜11:59までです。

A市から出るバスはa分ごとに発車し、B市への所要時間はta分です。B市から出るバスはb分ごとに発車し、A市への所要時間はtb分です。

運転手Simonは仕事に飽きて、運行途中に見かけたバスの数を数えました。ただし、出発地と到着地でのバスは数えていません。

SimonがA市からB市へ行くのに要する時間を与えるとき、Simonが見かけるバスの数を求めてください。

CF665Aの解法

赤い問題にやられてしまったEric

B市から出るバスの出発時刻をシミュレーションして、Simonの移動時間内に見えるかどうかを判定します。

CF665Aのコード

#include<bits/stdc++.h>
using namespace std;
int a, ta, b, tb, x, y;
signed main(){
    scanf("%d%d",&a,&ta);
    scanf("%d%d",&b,&tb);
    scanf("%d:%d",&x,&y);
    int tmp = (x - 5) * 60 + y;
    int i = 0,cnt = 0;
    while(i < tmp + ta && i <= 18 * 60 + 59){
        if(i + tb > tmp)cnt++;i += b;
    }
    printf("%d\n",cnt);
    return 0;
}

CF665B

CF665Bの問題文

小Wの店ではオンライン注文、現地受け取りのサービスがあります。店にはk個の商品（1からk番）があり、n人の顧客がこのサービスを使っています。

各顧客の注文にはm個の商品が含まれ、オンライン支払いが行われます。ai,jはi番目の顧客のj番目の商品の番号です。

すべての商品は一列に並んでおり、小Wがi番目の商品を受け取ったとき、彼は前から順にすべての商品ai,j (1≤j≤m)を探します。pos(x)は顧客が求めている番号xの商品が配列中の何番目にあるかを示します。

小Wが必要とする時間はpos(ai1)+pos(ai2)+...+pos(aim)です。

小Wがx番目の要素にアクセスすると、新しい商品をリストの先頭に移動し、x番目の要素を削除します。このリストは常に更新されます。小Wがかかる総時間を計算してください。市場には無限の在庫があると仮定します。

CF665Bの解法

なぜ問題文がこんなに長いのか

シミュレーションで十分です。O(n3)でも通ります。

CF665Bのコード

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 200;
int n, m, k;
vector<int> vec;
signed main(){
    n = read(); m = read(); k = read();
    for(int i = 1;i <= k;i++){vec.push_back(read());}
    int ans = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            int x = read(), t = 0;
            for(t = 0;t < vec.size();t++){if(vec[t] == x)break;}
            vec.erase(vec.begin() + t);
            vec.insert(vec.begin(),x);
            ans += t + 1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

CF665C

リンク

CF665Cの問題文

文字列を与えられるので、隣接する文字が異なるようにできるだけ少ない文字を変更してください。任意の解を出力してください。

CF665Cの解法

連続した同じ文字列を変更する際、奇数回は変更せず、偶数回は変更するだけで良いというアイデアです。

CF665Cのコード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n;char A[maxn], B[maxn];
signed main(){
    scanf("%s",A + 1);n = strlen(A + 1);
    for(int i = 1;i <= n;i++){
        int j = i;while(A[j + 1] == A[i])j++;
        char ch = 'a';while(A[j + 1] == ch || A[i] == ch)ch++;
        bool book = 0;
        for(int k = i;k <= j;k++){B[k] = book ? ch : A[i];book = !book;}
        i = j;
    }
    for(int i = 1;i <= n;i++)putchar(B[i]);
    puts("");
    return 0;
}

CF665D

リンク

CF665Dの問題文

数列a1,a2,...,anが与えられる。任意の2つの数の和が素数になるような部分列を求めてください。

CF665Dの解法

最後の部分列は以下の3つの中のいずれかになります。

• すべて1である場合、素数-1の数があればそれも含める
• 奇数と偶数の和が素数になる
• 任意の数を一つ選ぶ

詳細な処理を追っていきます。

CF665Dのコード

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e3 + 10;
int a[maxn], n;
bool book[maxn * maxn * 4];
int prime[maxn * maxn], tot;
vector<int> ans1,ans2,ans3;
signed main(){
    for(int i = 2;i <= 3e6;i++){
        if(!book[i])prime[++tot] = i;
        for(int j = 1;j <= tot && i * prime[j] <= 3e6;j++){
            book[i * prime[j]] = 1;
            if(i % prime[j] == 0)break;
        }
    }
    n = read();
    for(int i = 1;i <= n;i++){a[i] = read();if(a[i] == 1)ans1.push_back(1);}
    bool book2 = false, book1 = false;
    ans3.push_back(a[1]);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n && !book2;j++)
            if(!book[a[i] + a[j]] && !book2 && i != j){
                ans2.push_back(a[i]);ans2.push_back(a[j]);
                book2 = true;break;
            }
        if(ans1.size() && !book[a[i] + 1] && !book1 && a[i] != 1){
            book1 = true;ans1.push_back(a[i]);
        }
    }
    if(ans2.size() >= ans1.size() && ans2.size() >= ans3.size()){
        printf("%d\n",ans2.size());for(int i : ans2)printf("%d ",i);
    }
    else if(ans1.size() >= ans2.size() && ans1.size() >= ans3.size() && ans1[0] == 1){
        printf("%d\n",ans1.size());for(int i : ans1)printf("%d ",i);
    }
    else{
        printf("%d\n",ans3.size());for(int i : ans3)printf("%d ",i);
    }
    return 0;
}

CF665E

リンク

CF665Eの問題文

数列a1,a2,...,anが与えられる。点対(i,j)の個数を求めてください。

• 1≤i<j≤n
• ai⊕ai+1⊕...⊕aj≥k

CF665Eの解法

c_i = a1⊕a2⊕...⊕aiと置くと、問題は以下に変換されます。

• 1≤i<j≤n
• ci−1⊕cj≥k

この式はTrieで処理できます。

CF665Eのコード

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e6 + 10;
int n, a[maxn], c[maxn], K;

int trie[maxn * 30][2], tot = 1;
ll cnt[maxn * 30];
void insert(int x){
    int u = 1;
    // printf("x=%d\n",x);
    for(int i = 31;i + 1;i--){
        bool v = (x >> i) & 1;
        if(!trie[u][v])trie[u][v] = ++tot;
        u = trie[u][v];cnt[u]++;
        // printf("u=%d-&gt;",u);
    }
    // printf("u=%d\n",u);
}
ll query(int x,int k){
    int u = 1;ll ans = 0;
    for(int i = 31;i + 1;i--){
        bool v = (x >> i) & 1, ki = (k >> i) & 1;
        if(!ki){ans += cnt[trie[u][!v]];u = trie[u][v];}
        else{u = trie[u][!v];}
    }
    return ans;
}

signed main(){
    // freopen("CF665E.out","w",stdout);
    n = read(); K = read();
    for(int i = 1;i <= n;i++){a[i] = read(); c[i] = c[i - 1] ^ a[i];}
    ll ans = 0;
    // for(int i = 1;i <= 40;i++)printf("cnt[%d]=%lld\n",i,cnt[i]);
    for(int i = 0;i <= n;i++){
        ll tmp = query(c[i],K - 1);
        // printf("%lld\n",tmp);
        ans += tmp; insert(c[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

CF665F

リンク

CF665Fの問題文

n (n≤10^11)が与えられる。[1,n]の範囲内で約数が4個しかない数の個数を求めてください。

CF665Fの解法

性質を満たすためには以下のどちらかが必要です。

• 2つの異なる素数の積
• ある素数の3乗

n≤10^6の範囲であればブルートフォースで列挙可能。

答えは以下の式で表されます。

ans = f(3√n) + Σ(i=1,prime_i≤√n)(f(n/prime_i) - f(prime_i))

f(i)はi以下の素数の個数を示します。

CF665Fのコード

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
int n;
bool book[maxn];
const int N  = 1e6 + 10;
const int M  = 7;         //メモリ削減のため
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17; //メモリ削減のため
bool np[N];
int pr[maxn], tot;
int prime[N], pi[N];
int phi[PM + 1][M + 1], sz[M + 1];
    int cnt = 0;

int getprime() {
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for (int j = 1; j <= cnt && i * prime[j] < N; ++j) {
            np[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    return cnt;
}

void init() {
    getprime();
    sz[0] = 1;
    for (int i = 0; i <= PM; ++i) phi[i][0] = i;
    for (int i = 1; i <= M; ++i) {
        sz[i] = prime[i] * sz[i - 1];
        for (int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
    }
}

int sqrt2(int x) {
    int r = (int)sqrt(x - 0.1);
    while (r * r <= x) ++r;
    return (int)(r - 1);
}

int sqrt3(int x) {
    int r = (int)cbrt(x - 0.1);
    while (r * r * r <= x) ++r;
    return (int)(r - 1);
}

int getphi(int x, int s) {
    if (s == 0) return x;
    if (s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if (x <= prime[s] * prime[s]) return pi[x] - s + 1;
    if (x <= prime[s] * prime[s] * prime[s] && x < N) {
        int s2x = pi[sqrt2(x)];
        int ans  = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for (int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}

int getpi(int x) {
    if (x < N) return pi[x];
    int ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for (int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
    return ans;
}

int lehmer_pi(int x) { //x以下の素数の個数
    if (x < N) return pi[x];
    int a  = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b  = (int)lehmer_pi(sqrt2(x));
    int c  = (int)lehmer_pi(sqrt3(x));
    int sum = getphi(x, a) + (int)(b + a - 2) * (b - a + 1) / 2;
    for (int i = a + 1; i <= b; i++) {
        int w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        int lim = lehmer_pi(sqrt2(w));
        for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
    }
    return sum;
}

signed main(){
    scanf("%lld",&n);int len = sqrt(n);init();
    int sum = lehmer_pi(cbrt(n));
    for(int i = 1;i <= cnt && prime[i] < len;i++){
        // printf("pr[%lld]=%lld sum=%lld\n",i,prime[i],sum);
        sum += lehmer_pi(n / prime[i]) - lehmer_pi(prime[i]);
    }
    printf("%lld\n",sum);
    return 0;
}