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

srupのメモ帳

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

yukicoder No.492 IOI数列

yukicoder 行列 数学

問題

問題概要

a1 = 1, ai = 100ai-1 + 1という数列がある.
第N項を1000000007と101010101010101010101で割ったあまりを求める.

解法

前半の解
数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けない. また行列を利用して, 第n項を求める方法でもよい. 蟻本p180参照.
後半の解
答えは周期11で回っているので, mod11をしたあとに, 計算すればいい.
サンプルなどから周期はありそうで, 周期の見つけ方は,

mod = 101010101010101010101
d = 0
for i in xrange(1, 30):
    print d % mod
    d = d * 100 + 1
1
101
10101
1010101
101010101
10101010101
1010101010101
101010101010101
10101010101010101
1010101010101010101
0
1
101
10101
1010101
101010101
10101010101
1010101010101
101010101010101
10101010101010101
1010101010101010101
0
1
101
10101
1010101
101010101
10101010101
1010101010101

ミス

行列を使った問題初めて.

コード

漸化式を解くパターン

#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 ll INF = 1e9;
const ll INFF = 1e18;

// x^k (mod m)
long long powmod(long long x, long long k, long long m){
    long long ret = 1;
    while(k){
        if(k & 1) ret = ret * x % m;
        x = x * x % m;
        k >>= 1;
    }
    return ret;
}
// 1/a mod(p(素数))
long long invmod(long long a, long long p){
    return powmod(a, p - 2, p);
}

int main(void){
    ll n; cin >> n;
    ll d = powmod(100, n, MOD) + MOD - 1;
    d %= MOD;
    d *= invmod(99, MOD);
    printf("%lld\n", d % MOD);

    if(n % 11 == 0){
        printf("0\n"); return 0;
    }
    string s = "1";
    n %=11;
    rep(i, n  - 1){
        s = "10" + s;
    }
    cout << s << endl;

    return 0;
}

行列演算でanを求める.

#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 ll INF = 1e9;
const ll INFF = 1e18;

typedef vector<long long> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B){ // A * B の計算
    mat C(A.size(), vec(B[0].size()));
    for(int i = 0; i < A.size(); i++){
        for(int k = 0;k < B.size(); k++){
            for(int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % (ll)MOD; // mod
            }
        }
    }
    return C;
}
mat pow(mat A, long long n){ // A^n の計算
    mat B(A.size(), vec(A.size()));
    for(int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}


int main(void){
    ll n; cin >> n;
    mat A(2, vec(2));
    A[0][0] = 100, A[0][1]  = 1;
    A[1][0] = 0, A[1][1] = 1;
    auto ret = pow(A, n - 1);
    ll an = (ret[0][0] + ret[0][1]) % MOD;
    printf("%lld\n", an);

    int m = n % 11;
    ll ans = 0;
    rep(i, m){
        ans = ans * 100 + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

yukicoder No.491 10^9+1と回文

yukicoder

問題

問題概要

1以上N以下の整数で、109 + 1 の倍数かつ回文の数の個数を求めな

解法

109+1の倍数かつ回文になるには, 109+1に回文をかければ良い. よって, Nを109+1で割った数以下の整数で, 回文の個数を数えれば良い.
よって, dfsを用いて, その整数の桁数以下の桁数で作れる回文を作成し, その整数以下であるかをしらべてカウントした. 回文なので, 右半分は左半分と一致しているので, 左半分を作ったら, ひっくり返して右側にくっつければよい. 奇数桁の時は真ん中に注意.
もっと単純にできる. N <= 1018よりN/(109+1)は109以下の整数になり, 回文の条件より, 左半分の5桁までを全探索すれば, すべての回文数を列挙できる.

ミス

もっと単純に全探索すればよかった.

int main(void){
    ll n; cin >> n;
    ll cnt = 0;
    ll m = n / (1000000001);
    set<ll> se;
    for (int i = 1; i <= 100000; ++i){
        string left = to_string(i);
        string right = left; reverse(all(right));
        string even = left + right;
        string odd = left + right.substr(1);
        se.insert(stoll(odd)); se.insert(stoll(even));
    }
    for(auto u : se) if(u <= m) cnt++;
    printf("%lld\n", cnt);
    return 0;
}

コード

#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 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;

set<string> tmp;

void dfs(string s, int cnt, int size){
    if(cnt == size){
        tmp.insert(s);
        return;
    }
    if(cnt < size / 2){
        rep(i, 10){
            string d = to_string(i);
            dfs(s + d, cnt + 1, size);
        }
    }

    if(cnt >= size / 2){
        auto left = s;
        auto right = s;
        reverse(all(right));
        if(size % 2 == 1){
            rep(i, 10){
                string d = to_string(i);
                tmp.insert(left + d + right);
            }
        }else{
            tmp.insert(left + right);
        }
    }
    return;
}

ll solve(ll n){
    ll ret = 0;
    string s = to_string(n);
    reps(cnt, 1, s.size() + 1){
        reps(i, 1, 10){
            auto d = to_string(i);
            dfs(d, 1, cnt);
        }
    }
    for(auto u : tmp){
        ll d = stoll(u);
        if(d <= n) ret++;
    }
    return ret;
}

int main(void){
    ll n; cin >> n;
    n /= (INF + 1);
    printf("%lld\n", solve(n));
    return 0;
}

Codeforces #361 (Div.2) D. Friends and Subsequences

Codeforces セグメント木 ダブリング SparseTable

問題

問題概要

[l, r]の区間を考えた時に, al, .. , ar の最大値と bl, .. , br の最小値が一致する区間の総数を求める.

解法

区間の左端を固定して, 右端を伸ばしていくと, aの最大値は単調増加, bの最小値は単調減少していくので, 区間を伸ばしていくとどこかで一致する(条件を満たすものがあれば). 単調性を利用すると, 左端を決めた時に, 右端となる場所を二分探索でもとめることができる. ひとつの左端に対して, 右端となりうる場所は連続して複数ある場合があるので, lower_bound と upper_bound みたいな感じで, 2つ求める. またa, bのn+1番目の要素として, 番兵のようなものをいれておかないとすべての値が同じ時になぜかばぐったのでいれた. (よくわからない)
あとは区間の最大値最小値をどのように求めるかだが, segtreeでできる. segtreeの場合, 区間の最大値最小値を計算する際に, lognかかるため, 全体でO(nlognlogn)となりだいぶ危ない感じになる. 実際蟻本の実装方法でやると, TLEしたので, 更新処理を高速化したらAC.
また今回のように, 値の更新が途中でない場合, ダブリングのような感じで,
table[i][k] := [i, i + 2k)の最大値/最小値
というような配列を先にO(nlogn)で構築しておくことで, 区間の最大値/最小値を計算するのがO(1)で可能になり, 全体として, O(nlong)でできるようになる.

ミス

なし.

コード

高速化した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;
int a[200010], b[200010];

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

template <class T> //T : dat[]の中身の型
class segtree_min{
public:
    int n;
    vector<T> dat;
    segtree_min(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){
    scanf("%d", &n);
    rep(i, n)scanf("%d", &a[i]);
    rep(i, n)scanf("%d", &b[i]);
    segtree_max<int> sega(n + 1);
    segtree_min<int> segb(n + 1);

    rep(i, n) sega.update(i, a[i]);
    sega.update(n, INF + 1); //右端を追加
    rep(i, n) segb.update(i, b[i]);
    segb.update(n, -1); //右端を追加

    ll ret = 0;
    rep(i, n){ // 左端
        int l = i, r = n + 1;
        int ansl, ansr;
        while(r - l > 1){ // lower_bound
            int m = (l + r) / 2;
            auto da = sega.query(i, m); //単調増加
            auto db = segb.query(i, m); //単調減少
            if(da < db) l = m;
            else r = m;
        }
        if(sega.query(i, l + 1) == segb.query(i, l + 1))ansl = l;
        else continue;

        l = ansl, r = n + 1;
        while(r - l > 1){ //upper_bound
            int m = (l + r) / 2;
            auto da = sega.query(i, m); //単調増加
            auto db = segb.query(i, m); //単調減少
            if(da < db + 1) l = m;
            else r = m;
        }
        ansr = l;
        //[ansl, anrl], .. , [ansl, ansr - 1] までが答えの区間
        ret += ansr - ansl;
    }
    printf("%lld\n", ret);
    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;
int a[200010], b[200010];

template <class T> //T : table[][]の中身の型
class SparseTable_max{
public:
    int N, M; //table[N][M]
    // table[i][k] := [i, i + 2^k)の最大値
    vector<vector<T>> table;
    template<class S> SparseTable_max(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] = max(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 max(table[l][k], table[r - (1 << k)][k]); // (2) 最大値
    }
};

template <class T> //T : table[][]の中身の型
class SparseTable_min{
public:
    int N, M; //table[N][M]
    // table[i][k] := [i, i + 2^k)の最小値
    vector<vector<T>> table;
    template<class S> SparseTable_min(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){
    scanf("%d", &n);
    rep(i, n)scanf("%d", &a[i]);
    a[n] = INF + 1;
    rep(i, n)scanf("%d", &b[i]);
    b[n] = -1;
    SparseTable_max<int> sega(n + 1, a);
    SparseTable_min<int> segb(n + 1, b);

    ll ret = 0;
    rep(i, n){ // 左端
        int l = i, r = n + 1;
        int ansl, ansr;
        while(r - l > 1){ // lower_bound
            int m = (l + r) / 2;
            auto da = sega.query(i, m); //単調増加
            auto db = segb.query(i, m); //単調減少
            if(da < db) l = m;
            else r = m;
        }
        if(sega.query(i, l + 1) == segb.query(i, l + 1))ansl = l;
        else continue;

        l = ansl, r = n + 1;
        while(r - l > 1){ //upper_bound
            int m = (l + r) / 2;
            auto da = sega.query(i, m); //単調増加
            auto db = segb.query(i, m); //単調減少
            if(da < db + 1) l = m;
            else r = m;
        }
        ansr = l;
        //[ansl, anrl], .. , [ansl, ansr - 1] までが答えの区間
        ret += ansr - ansl;
    }
    printf("%lld\n", ret);
    return 0;
}

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

arc セグメント木 imos法 SparseTable

問題

問題概要

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 - スペース高橋君

arc

問題

問題概要

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

解法

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 - 最短路問題

arc 考察 数え上げ

問題

問題概要

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 - 素数判定

arc

問題

問題概要

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;
}