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

srupのメモ帳

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

ABC 029 D - 1

問題

問題概要

1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか?

解法

脳死しているので桁dpをする.
dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数
という状態を決めてやればいい. 漸化式の遷移はすでにNより小さいのかどうかで場合分けした後, 今見ている桁が0, 1またはそれ以外で場合分けして丁寧にj, kの値を決めていけば大丈夫.

ミス

dpの状態を決めるのに悩んだ.
求めたいものが数字1の総数なので, dp[i][j]:= (上記)ijの時の1を使った数 という状態としてしまった.
状態数に求めたいものをいれることだってあるので注意. 桁dpは決めた状態を満たす数字の総数をメモっていくと考えておこう.

コード

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

string N;
ll dp[12][2][12];
// dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる 数字の総数

int main(void){
    cin >> N;
    rep(i, 12)rep(j, 2)rep(k, 12) dp[i][j][k] = 0;
    dp[0][0][0] = 1;

    rep(i, N.size()){
        rep(j, 2)rep(k, 12){
            if(dp[i][j][k] == 0) continue;
            if(j == 1){ // N より小さい
                dp[i + 1][1][k + 1] += dp[i][j][k]; // 1を選ぶ
                dp[i + 1][1][k] += dp[i][j][k] * 9; // 0,2, .. 9 を選ぶ
            }else{
                if(N[i] == '1'){
                    dp[i + 1][0][k + 1] += dp[i][j][k]; //1を選ぶ
                    dp[i + 1][1][k] += dp[i][j][k]; //0を選ぶ
                }else if(N[i] == '0'){
                    dp[i + 1][0][k] += dp[i][j][k]; //0を選ぶ
                }else{//2 <= N[i] <= 9
                    dp[i + 1][0][k] = dp[i][j][k]; // N[i]を選ぶ
                    dp[i + 1][1][k] = dp[i][j][k] * ((N[i] - '0') - 1); //2 ~ N[i]-1
                    dp[i + 1][1][k + 1] += dp[i][j][k]; //1を選ぶ
                }
            }
        }
    }
    ll ans = 0;
    rep(j, 2)rep(k, 12){
        if(dp[(int)N.size()][j][k]){
            ans += k * dp[(int)N.size()][j][k];
        }
    }
    cout << ans << endl;
    return 0;
}

CODE THANKS FESTIVAL 2015 G - カメレオン

問題

問題概要

頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である.

解法

拡張ダイクストラをすればいい.
dist[i][j]として 頂点0からiまで, iへ色jで来た時の最小コストとして ダイクストラで計算していけばいい. ただし, 今回の問題で普通に2次元配列を取るとMLEしてしまう. しかし, 頂点iで可能性のある色は, iと隣接する辺で指定される色のみなので, dist[i][j]のjは実際は全種類の色の総数分の空間を用意しなくて良いことになる.
ではどうするかだが, dist[i]を必要な分だけ拡張すればよいかなと考えたが, めんどくさいので, map<int, ll> dist[] とすることで, dist[i][j]のjが必要な分だけ用意できることになる.

ミス

2次元配列が欲しくて, そのままではMLEしてしまうが, 2つめの要素がまばらな時, mapを使えば楽に空間を減らせる.

mapの使い方に注意
dist[v]にkey=ncが登録されていないか, 登録されていたとしても, ncostより大きかを調べる場合に,

if(dist[v][nc] > ncost || dist[v].count(nc) == 0)

ではだめ.

if(dist[v].count(nc) == 0 || dist[v][nc] > ncost)

としなければならない.
std::mapは[]演算子で存在しない要素にアクセスすると自動的に追加されるしまうので, 左側に(先に評価される方)dist[v][nc]とすると, key=ncの要素がないのに作られてしまい, 右側の評価が意味のないものになってしまった.

std::map - C++入門

コード

#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 a[80010], b[80010], c[80010], t[80010];

using tup = tuple<ll, int, int>;
vector<tuple<int, int, int>> G[40010]; // G[i] := i->j color time
//dist[i][j] := 頂点iへcolor jでつくときのコストの最小値
map<int, ll> dist[40010];
void dijkstra(int start){
    priority_queue<tup, vector<tup>, greater<tup>> que; // コスト 位置 color
    dist[start][1] = 0;
    que.push(make_tuple(0, start, 1));
    while(!que.empty()){
        ll cost; int u, color;
        tie(cost, u, color) = que.top(); que.pop();
        if(dist[u][color] < cost) continue; // これでTLE回避
        if(u == N - 1) break;
        for(auto tm : G[u]){
            int v, nc, nt;
            tie(v, nc, nt) = tm;
            ll ncost = cost + abs(nc - color) + nt;
            // if(dist[v][nc] > ncost || dist[v].count(nc) == 0){ // dist[v][nc]の要素ができてしまう
            if(dist[v].count(nc) == 0 || dist[v][nc] > ncost){
                dist[v][nc] = ncost;
                que.push(make_tuple(ncost, v, nc));
            }
        }
    }
}

int main(void){
    scanf("%d %d", &N, &M);
    rep(i, M) scanf("%d %d %d %d", &a[i], &b[i], &c[i], &t[i]);
    rep(i, M){
        a[i]--; b[i]--;
        G[a[i]].pb(make_tuple(b[i], c[i], t[i]));
        G[b[i]].pb(make_tuple(a[i], c[i], t[i]));
    }
    dijkstra(0);
    ll ans = INFF;
    for(auto u : dist[N - 1]){
        chmin(ans, u.se);
    }
    printf("%lld\n", ans);
    return 0;
}

yukicoder No.492 IOI数列

問題

問題概要

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と回文

問題

問題概要

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

問題

問題概要

[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 - ドキドキデート大作戦高橋君

問題

問題概要

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