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

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC 045 B - ドキドキデート大作戦高橋君

問題

問題概要

N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える.

解法

まずimos法を利用して, i番目の教室の掃除を割り当てられている人が何人いるかを求める.
あとは, 教室の掃除が何人に割り当てられているかをもつsegtreeを作り, 一人の人が掃除する区間の最小値が1より大きければ, その人が掃除をしなくてもその区間をだれかが掃除することになりその人はサボれることになる.
値が更新がないので, SparseTableでも解くことができる.

ミス

なし.

コード

高速化したsegtree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, INF); //(1) 初期値を最大に
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        for (dat[k += n] = val; k > 0; k >>= 1){ // kを含む区間のインデックスを下から順に列挙
            dat[k>>1] = min(dat[k], dat[k ^ 1]); // (2) 区間の最大値で更新
        }
    }
    T query(int l, int r){
        T ret = INF; //(3) 最小値に関係ない値
        for (l += n, r += n; l < r; l >>= 1, r >>= 1){
            if(l & 1) ret = min(ret, dat[l++]); //(4) 区間の最小値で更新
            if(r & 1) ret = min(ret, dat[--r]); //(4) 区間の最小値で更新
        }
        return ret;
    }
};

int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    segtree<int> seg(n);
    rep(i, n){
        seg.update(i, imos[i]);
    }
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

蟻本segtree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, INF); //(1) 初期値を最大に
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1; //葉の節点
        dat[k] = val;
        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); // (2) 区間の最小値で更新
        }
    }
    T query(int a, int b, int k, int l, int r){ //[a, b)の最大値を求める
        if(r <= a || b <= l) return INF; //(3) 最小値に関係ない値で更新
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr); //(4) 区間の最小値で更新
        }
    }
    T query(int a, int b){
        return query(a, b, 0, 0, n);
    }
};


int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    segtree<int> seg(n);
    rep(i, n){
        seg.update(i, imos[i]);
    }
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

SparseTable

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : table[][]の中身の型
class SparseTable{
public:
    int N, M; //table[N][M]
    // table[i][k] := [i, i + 2^k)の最小値
    vector<vector<T>> table;
    template<class S> SparseTable(int n, S &val): N(n){ // O(nlogn)
        M = 32 - __builtin_clz(N); // M - 1 <= logN < M
        table.resize(N, vector<T>(M));
        for (int i = 0; i < N; ++i){ // [i, i + 1)までの区間の最小値
            table[i][0] = val[i];
        }
        for (int k = 0; k < M - 1; ++k){ // [i, i + 2^(k+1))の区間を計算
            for (int i = 0; i + (1<< k) < N; ++i){
                // iから2^(k+1)の長さの区間の最小値を2^kの長さの区間の最小値を利用して求める
                table[i][k + 1] = min(table[i][k], table[i + (1 << k)][k]); // (1)最小値
            }
        }
    }
    T query(int l, int r){ // O(1) [l, r) の間の最小値
        int k = 31 - __builtin_clz(r - l); //区間の長さの半分以上の値 (k<= r - l < k + 1)
        return min(table[l][k], table[r - (1 << k)][k]); // (2) 最小値
    }
};

int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    SparseTable<int> seg(n, imos);
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

ARC 045 A - スペース高橋君

問題

問題概要

与えられた文字列に応じて出力する文字列を変更する.

解法

string s;
while(cin>>s){
    //処理
}

上記のような方法で, スペースまでの文字列を受け取り, 終了したらwhileを抜けれる.

ミス

なし.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void){
    string d;
    int f = 0;
    while(cin >> d){
        if(f) printf(" "); f++;
        if(d == "Left") printf("<");
        else if(d== "Right") printf(">");
        else printf("A");
    }
    printf("\n");
    return 0;
}

ARC 044 B - 最短路問題

問題

問題概要

A1をstartとした時の頂点までの最短経路の情報が与えられる. その木の高さで作ることのできるグラフは何通りあるか, mod1e9+7で答えろ.

解法

まず, A1からの最短経路の情報が与えられているはずなので, A1以外で最短経路が0であればそのようなグラフは作れない.
また, 最短経路は連続したものであるといえる. (最短経路が0, 1, 3のように与えらた場合, 2がないので, どのようにやってもグラフは作れない)
ではグラフが作れる条件を満たしている場合どのようにすれば場合の数が数え上げることができるかだが, まず最短経路が同じもの同士を繋いでも最短経路が変わることはないので, 同じ高さ同士のものは好きなようにつなぐことができる. 同じ高さの頂点を2つ選び方法は, sum[i] := 距離iの頂点個数として, sum[i] C 2 で求まり, その辺を使うか使わないかそれぞれ選ぶことができるので, pow(2, sum[i] C 2)通りあることになる.
次に距離の違うもの同士をどのように繋ぐかだが, まず, 距離の差が1より大きいものと繋いでしまうと, 最短経路の情報がずれてしまうのでダメ(1と 3をつなぐと最短経路3のものが最短経路2になってしまう)
よって距離i, i+1の場合を考えれば良いことになる. 距離i+1の頂点は, iの頂点のどれかと必ず繋がないと, グラフとつながっていないことになってしまうので, i のどれかと繋ぐようにする. i+1の頂点一つについて考えれば,
pow(2, sum[i]) - 1
となる. -1はどれも選ばないのをなくすため.
あとは, これをi+1の頂点全てについて考えれば良い.

ミス

考察段階でだいぶ悩んだ. 1つの辺をつけるかつけないかの2通りということを意識して考えていけば, もっとすんなりいけた?

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

ll n;
ll a[200010];
ll sum[200010];

//x^k mod
long long powmod(long long x, long long k, long long m){ // 繰り返し二乗法(logk)
    if(k == 0) return 1;
    if(k % 2 == 0) return powmod(x * x % m, k / 2, m);
    else return x * powmod(x, k - 1, m) % m;
}

int main(void){
    ll max_a = 0;
    cin >> n;
    rep(i, n){
        cin >> a[i];
        chmax(max_a, a[i]);
    }

    if(a[0] != 0){
        printf("0\n"); return 0;
    }
    reps(i, 1, n) if(a[i] == 0){
        printf("0\n"); return 0;
    }

    rep(i, n){
        sum[a[i]]++;
    }
    rep(i, max_a + 1){
        if(sum[i] == 0){ // グラフの高さにで飛んでいるものはない
            printf("0\n"); return 0;
        }
    }

    ll ans = 1;
    //同じ高さのものをつなぐ
    reps(i, 1, max_a + 1){
        //同じ高さの頂点を2つ選ぶ方法は, sum[i] C 2 通り
        ans *= powmod(2, sum[i] * (sum[i] - 1) / 2, MOD);
        ans %= MOD;
    }
    //下のやつと一つ上のやつをつなぐ 
    for (int i = max_a; i >= 1; --i){
        //任意の下のやつ1つに対して上のやつを選ぶか選ばないか (何も選ばないのはダメ)
        ll t = powmod(2, sum[i - 1], MOD) - 1;
        ans *= powmod(t, sum[i], MOD); //下の奴がsum[i]個あるので
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

ARC 044 A - 素数判定

問題

問題概要

Nが素数ならPrime
Nが合成数で, 1の位が2,5で割り切れず, 各桁の和が3で割り切れないとき, Prime
それ以外なら Not Prime

解法

まず, 普通に素数判定をし, 素数ならPrime.
次に, 1のくらいが2, 5で割り切れず, 各桁の和が3で割り切れないければ, Primeとして それ以外はNot Primeとなる.

ミス

各桁の和が3の倍数の時は, その数は3の倍数でした. 忘れてた.
N = 100a+10b + c = 99a + 9b + (a + b + c)
なので, a+b+c(各桁の和)が3の倍数であれば, 3の倍数となる. 各桁の和が9の倍数なら, 9の倍数でもあるのか.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int main(void){
    string s; cin >> s;
    ll n = stoll(s);
    if(n == 1){
        printf("Not Prime\n"); return 0;
    }
    auto d = s.back() - '0';
    int sum = 0;
    bool f = true;
    for(auto u : s) sum += u - '0';
    for (int i = 2; i * i <= n; ++i){
        if(n % i == 0){
            f = false;
            break;
        }
    }
    if(f){
        printf("Prime\n"); return 0;
    }

    if((d % 2 != 0 && d != 5) && sum % 3 != 0){
        printf("Prime\n");
    }else{
        printf("Not Prime\n");
    }
    return 0;
}

Codeforces 400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend

問題

問題概要

i番目のものをi+1として考えて, 色を塗っていく. 塗る色はその数の素因数と同じ色にしてはいけない. 塗る色の最小数を求める問題.

解法

その数しか素因数を持たない素数はすべて同じ色で塗ることが可能. そのようにすると, 素数でない数はすべてその数が持つ素因数が同じ色で塗られているので, その色以外の色で塗ることができる. つまり素数は色1, 素数でないものは色2で塗ることができる.
ただし, n = 1, 2の時は別でやる.

ミス

なし.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


bool isprime[100100];
//エラトステネス
void eratos(int m){
    for (int i = 0; i <= m; ++i) isprime[i] = true;
    isprime[0] = isprime[1] = false;
    //iを残してiの倍数を消していく
    for (int i = 2; i <= m; ++i){
        if(isprime[i]){
            for (int j = 2 * i; j <= m; j += i){
                isprime[j] = false;
            }
        }
    }
}

int main(void){
    int n; cin >> n;
    if(n == 1){
        printf("1\n");
        printf("1\n");
        return 0;
    }else if(n == 2){
        printf("1\n");
        printf("1 1\n");
        return 0;
    }
    eratos(n + 10);
    printf("2\n");
    reps(i, 2, n + 2){
        if(isprime[i]){
            printf("1 ");
        }else{
            printf("2 ");
        }
    }
    printf("\n");
    return 0;
}

Codeforece 400 (Div. 1 + Div. 2, combined) A. A Serial Killer

問題

問題概要

文字列が2つ与えられる. ひとつの文字列を指定された文字列に置換する操作を行うクエリに応える.

解法

setで管理しながら, 置換される方をeraseして, 加える方をinsertしていけばいい.

ミス

なし.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void){
    set<string> se;
    vector<string> ans;
    rep(i, 2){
        string t; cin >> t;
        se.insert(t);
        ans.pb(t);
    }
    int n; cin >> n;

    rep(i, n){
        string t1, t2; cin >> t1 >> t2;
        se.erase(t1);
        se.insert(t2);
        for(auto u : se){
            ans.pb(u);
        }
    }
    int cnt = 0;
    for(auto u : ans){
        if(cnt % 2 == 0) cout << u << " ";
        else cout << u << endl;
        cnt++;
    }
    return 0;
}

codeforces 401 div2 D. Cloud of Hashtags

問題

問題概要

与えられた文字列をすべて与えらた順番で辞書順にする. そのために各文字列から末尾の文字を好きなだけ取り除いていい. 取り除く文字の最小数を求める問題.

解法

一番後ろの文字はそのままにできることがわかるので, 後ろから順番に見ていき, 貪欲にできるだけ文字を残していけばいい. どこまで残すかの判定は, i番目とi+1番目の文字列を考えた時に, s[i][p] と s[i + 1][p] のようにiとi+1の文字列のp番目の文字を比較した時に, i番目の文字がi+1番目の文字以下である間は残して, 超えたらその文字より手前でi番目の文字列を切ればいい.

ミス

計算量大丈夫なんかな. resize便利

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int n;
string s[500100];

int main(void){
    scanf("%d", &n);
    rep(i, n) cin >> s[i];
    for (int i = n - 2; i >= 0; --i){
        if(s[i] > s[i + 1]){ //変える必要あり
            int p = 0;
            while(p < s[i + 1].size() && p < s[i].size() && s[i][p] <= s[i + 1][p]) p++;
            s[i].resize(p);
        }
    }
    rep(i, n){
        printf("%s\n", s[i].c_str());
    }
    return 0;
}