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

h_nosonの日記

競プロなど

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

問題

Problem - D - Codeforces
3つのクエリに答える.
1. xをmultiset Aに加える
2. xをmultiset Aから取り除く
3. \displaystyle{\max_{y\in A}}(x\oplus y)を出力する

解法1

c++のmultisetを使って二分探索をする.
xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい.xを反転したものがAに含まれていればいいのだが,あるとは限らないので上位のbitからそのbitが1(または0)である値が存在するかどうかをlower_boundを使って調べる.見つかればその後はそのbitはその値に固定して探索を行う.見つからなければ,そのbitは妥協して次のbitに移る.計算量はO(Q\log Q\log X_{max}).
実装しているときに<algorithm>で定義されているlower_boundをsetで使うとO(N)かかってしまうことを知った.

解法2

考え方は解法1と同じなのだがトライ木を使ってO(Q\log X_{max})に抑える.トライ木のノードには1文字格納されており,根から葉までたどることで文字列を高速に検索できる.整数も01の文字列とみなせるのでトライ木を使うことができる.さらに今回は上位bitから探索を行いため非常に相性がいい.あるbitが1(または0)の値が含まれているかはその方向に枝が存在するか確認するだけなので先ほどの解法よりも計算量を抑えられる.

ソースコード1

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

int main(void) {
    int q;
    scanf("%d",&q);
    multiset<unsigned int> st {0};
    while (q--) {
        char op;
        int x;
        scanf("\n%c %d",&op,&x);
        if (op == '+') st.insert(x);
        else if (op == '-') st.erase(st.find(x));
        else {
            int i;
            unsigned int l = 0, r = 1U<<31;
            RREP (i,30,0) {
                if (x & 1<<i) {
                    auto p = st.lower_bound(l);
                    if (*p < (l|1<<i))
                        r = l | 1 << i;
                    else
                        l = l | 1 << i;
                }
                else {
                    auto p = st.lower_bound(l|1<<i);
                    if (p != st.end() && *p < r)
                        l = l | 1 << i;
                    else
                        r = l | 1 << i;
                }
            }
            printf("%d\n",x^l);
        }
    }
    return 0;
}

ソースコード2

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

struct Trie {
    int num;
    struct Trie* parent;
    struct Trie* child[2];
};

struct Trie root;

void add(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = val>>i&1;
        if (node->child[next] == NULL) {
            node->child[next] = new Trie();
            node->child[next]->parent = node;
        }
        node = node->child[next];
    }
    node->num++;
}

void remove(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        node = node->child[val>>i&1];
    }
    if (--node->num) return;
    bool end = false;
    while (node != &root && !end) {
        struct Trie* p = node->parent;
        REP (i,2) {
            if (p->child[i] == NULL || p->child[i] == node) p->child[i] = NULL;
            else end = true;
        }
        delete(node);
        node = p;
    }
}

int query(int val) {
    int i, ret = 0;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = 1 - (val>>i&1);
        if (node->child[next] != NULL) {
            node = node->child[next];
            ret = ret * 2 + next;
        }
        else {
            node = node->child[1-next];
            ret = ret * 2 + 1 - next;
        }
    }
    return ret;
}

int main(void) {
    int q;
    scanf("%d\n",&q);
    add(0);
    while (q--) {
        char op;
        int x;
        scanf("%c %d\n",&op,&x);
        if (op == '+') add(x);
        else if (op == '-') remove(x);
        else printf("%d\n",x^query(x));
    }
    return 0;
}

Codeforces Round #365 (Div. 2) C. Chris and Road

問題

Problem - C - Codeforces
N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題

解法

バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く,そうでなければスタート地点を後ろにずらしていき直線がバスに接するようにすればいい.
移動後の直線をy=U/V*x-bとすると,すべての点に対してb=\max(b,U/V*x-y)を求めればよくなる.下図の緑の直線の場合,待つ必要はなくなる.
f:id:h_noson:20160805150303p:plain

ソースコード

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

int main(void) {
    int i, N, W;
    double V, U;
    cin >> N >> W >> V >> U;
    double x = 0;
    bool go = true;
    REP (i,N) {
        int X, Y;
        cin >> X >> Y;
        x = max(x,U/V*X-Y);
        if (X / V < Y / U) go = false;
    }

    if (go) x = 0;
    cout << fixed << setprecision(7);
    cout << (W + x) / U << endl;
    return 0;
}

AtCoder Grand Contest 002 D - Stamp Rally

問題

D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder
N頂点,M辺からなるグラフがあり,Q組の兄弟がスタンプラリーを行う.i番目の兄弟はそれぞれXi,Yiにいて合わせてZiのスタンプを集めたいと思っている.通ることになる辺の最大の番号を最小にする問題

解法

まず,クエリ1つずつに対して最小値を求めることを考える.Union-Findを使って,頂点の個数の合計がZiを超えるまで順番に辺を加えていけばいい.しかし,この解法の計算量はO(MQ)になってしまう.そこでクエリをまとめて計算をすることを考える.Union-Findで辺をM/2まで追加し,その時点でそれぞれのクエリがZiを超えているか判定し,超えたものの集合と超えていない集合に分ける.これを図のようにlogM回繰り返すと,最終的にj番目まで辺を加えたときにZiを超えるクエリの集合を求められる.図でいうと行ごとにO(M+Q)かかるので全体でO((M+Q)logM)に抑えられる.
コードを書く際はMを2のべき乗まで広げると実装しやすくなる.
f:id:h_noson:20160801020530p:plain
永続Union-Findを使っても解けるらしい

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

typedef long long ll;

constexpr int INF = 1e8;
constexpr int MOD = 1e9+7;

int par[100000];
int cnt[100000];
vector<int> bs[262143];
int A[100000], B[100000];
int X[100000], Y[100000], Z[100000];
int ans[100000];

void init(int n) {
    int i;
    REP (i,n) par[i] = i;
    REP (i,n) cnt[i] = 1;
}

int find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) cnt[y] += cnt[x];
    par[x] = y;
}

int count(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return cnt[x];
    else return cnt[x] + cnt[y];
}

int main(void) {
    int i, N, M;
    scanf("%d%d",&N,&M);
    REP (i,M) {
        scanf("%d%d",&A[i],&B[i]);
        A[i]--; B[i]--;
    }
    int Q;
    scanf("%d",&Q);
    REP (i,Q) {
        scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
        X[i]--; Y[i]--;
    }

    REP (i,Q) bs[0].push_back(i);
    int size = 1;
    while (M > size) size <<= 1;
    for (int j = 0, k = 0; 1 << k < size; k++) {
        init(N);
        int s = 0, e = size / (1<<k);
        REP (i,size) {
            if (i == (s + e) / 2) {
                for (auto a: bs[j]) {
                    if (count(X[a],Y[a]) >= Z[a])
                        bs[j*2+1].push_back(a);
                    else
                        bs[j*2+2].push_back(a);
                }
                j++;
                s = e; e += size / (1<<k);
            }
            if (i < M) unite(A[i],B[i]);
        }
    }
    REP (i,M) for (auto x: bs[i+size-1]) {
        ans[x] = i+1;
    }
    REP (i,Q) printf("%d\n",ans[i]);
    return 0;
}

天下一プログラマーコンテスト2016予選A C

トポロジカルソートを初めて書いた気がするので記事に残そうと思う

問題

C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder
文字列Ai,BiがN個ずつ与えられる.Ai<=Biとなるようにアルファベット"abc...z"の順序を並び替えたとき,辞書順最小となるアルファベットの順序を出力する問題

解法

トポロジカルソートを使う.AiとBiを左の文字から比較して初めて異なる文字a,bが見つかったときa < bとなるようにアルファベットの順序を並び替えればいい.a→bとしてグラフにするとトポロジカルソートのうち辞書順最小となるものを求めればよくなる.
トポロジカルソートのアルゴリズムは知る限りではDFSとBFSの2種類ある.

入次数(その頂点に入る矢印の数)が0の頂点からDFSを行う.一番深いところまでたどったら,stackに頂点をpushしていきながら戻ってくる.このようにすることでstackの先頭からトポロジカルソートされた列になっている.

入次数が0の頂点をすべてqueueに入れBFSを行う.queueから取り出したらその頂点の子の入次数を1減らし,入次数が0になった頂点をqueueに入れる.queueを優先度付きqueueに変えることで辞書順最小のトポロジカルソートを行える.この問題ではこれを使う.

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

vector<char> e[256];
int indeg[256];

int main(void) {
    int i, j, n;
    cin >> n;
    REP (i,n) {
        string a, b;
        cin >> a >> b;
        REP (j,min(a.size(),b.size())) if (a[j] != b[j]) {
            e[a[j]].push_back(b[j]);
            indeg[b[j]]++;
            break;
        }
        if (j == b.size() && j < a.size()) {
            cout << -1 << endl;
            return 0;
        }
    }
    priority_queue<char,vector<char>,greater<char>> q;
    for (char c = 'a'; c <= 'z'; c++) if (indeg[c] == 0) {
        q.push(c);
    }
    string ans;
    while (!q.empty()) {
        char c = q.top();
        q.pop();
        for (auto x: e[c]) {
            indeg[x]--;
            if (indeg[x] == 0) q.push(x);
        }
        ans.push_back(c);
    }
    if (ans.size() == 26)
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}

Codeforces Round #363 (Div. 2) E. LRU

問題

Problem - E - Codeforces
N個のデータと容量Kのキャッシュがある.キャッシュのアルゴリズムにLRUが使われていて,無限のクエリが飛んできたとき,最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか.

解法

簡単に言うと,キャッシュの最後の状態をすべて挙げてそれが起こる確率をbitDPで計算する.最後から逆戻りして考える.
集合Sの要素がすでにキャッシュに入っているときの,Sに含まれない要素eがキャッシュに入る確率はp[e]/(Sに含まれない要素の確率の和)になる.よって
dp[S\cup\{e\}]=dp[S]*p[e]/(Sに含まれない要素の確率の和)
という漸化式が得られる.
コンテスト中は,Sがキャッシュに入っているときでもSの要素を追加しようとすることがあるのでその確率をどう考えればいいか悩んでいたが,上のようにS以外の要素についてだけ考えられるようにすることでうまくできる.また,(Sに含まれない要素の確率の和)は0になることもあり得るので,それにも対処する必要がある.

ソースコード

#include <iostream>
#include <iomanip>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

double p[20], ans[20];
double dp[1<<20];

int main(void) {
    int i, j, n, k;
    cin >> n >> k;
    REP (i,n) cin >> p[i];

    int zero = 0;
    REP (i,n) if (p[i] < 1e-9) zero++;
    if (zero >= n - k) {
        REP (i,n) ans[i] = p[i] >= 1e-9;
    }
    else {
        dp[0] = 1;
        REP (i,1<<n) {
            if (__builtin_popcount(i) >= k) continue;
            double total = 0;
            REP (j,n) if (!(i&1<<j)) total += p[j];
            REP (j,n) if (!(i&1<<j)) {
                dp[i|1<<j] += dp[i] * p[j] / total;
            }
        }
        REP (i,1<<n) if (__builtin_popcount(i) == k) REP (j,n) if (i&1<<j) {
            ans[j] += dp[i];
        }
    }

    REP (i,n) cout << fixed << setprecision(8) << ans[i] << (i < n-1 ? ' ' : '\n');
    return 0;
}

yukicoder No.23 技の選択

問題

No.23 技の選択 - yukicoder
体力がHの敵を

  1. 攻撃力Aの通常攻撃(必ず当たる)
  2. 攻撃力Dの必殺技(2/3の確率で当たる)

の二つの攻撃を使って倒したい.最小の攻撃回数の期待値はいくつか.

解法

解説を見たら全部DPで解いていたが,通常攻撃の使う回数でループを回しても解ける.
必殺技は2/3の確率で当たるので,必殺技が全部当たって倒す回数の3/2が必殺技で倒せる回数の期待値である.通常攻撃をi回使った時の,必殺技を使う回数の期待値は
(\max(H-A*i,0)+b-1)/b*1.5
となる.

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int main(void) {
    int i, h, a, d;
    double ans = 1e5;
    cin >> h >> a >> d;
    rep (i,(h+a-1)/a+1)
        ans = min(ans,i+(max(0,h-a*i)+d-1)/d*1.5);
    cout << ans << endl;
    return 0;
}

CodeChef July Challenge 2016 Chef and Rectangle Array

問題

https://www.codechef.com/problems/CHSQARR
N\times Mの行列が与えられる.Q個のクエリに対して以下の操作を行う.

  • a,bが与えられてa\times bの範囲の数がすべて等しくなるように行列の要素の数字を増やすとき,増やす数の最小値を出力する

解法

範囲の和Sと範囲の最大値maxを使って,a*b*max-Sが最小になるようにすればいい.
範囲の和は累積和を使って求められる.
範囲の最大値はdequeを使って,最大となる数字がある位置を先頭にくるようにすれば,すべての範囲の最大値はO(NM)で求められる.
一次元の場合を考えると

2 5 4 7 1 3

という数列があって範囲の大きさが3となる範囲の最大値を求めたい.
まず初めの3つを見ているときのdequeの中身は{1,2}となる(順に5のindex,4のindex).

2 5 4 7 1 3

次の3つを見ているときのdequeの中身は{3}となる(7のindex).

2 5 4 7 1 3

このようにdequeの値を持つとしゃくとり法の要領で最大値を保持しながら範囲をずらすことができる.
今回はこれを二次元の場合に落としこめばいい.

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e9
#define MOD (int)(1e9+7)

typedef long long ll;

int A[1000][1000];
int sum[1000][1000];

int value(pair<int,int> p) {
    return A[p.first][p.second];
}

int main(void) {
    int i, j, N, M, Q;
    scanf("%d%d",&N,&M);
    rep (i,N) rep (j,M) scanf("%d",A[i]+j);
    rep (i,N) {
        sum[i][0] = A[i][0];
        REP (j,1,M) sum[i][j] = sum[i][j-1] + A[i][j];
    }
    rep (j,M) rep (i,N-1) sum[i+1][j] += sum[i][j];

    scanf("%d",&Q);
    while (Q--) {
        int a, b;
        scanf("%d%d",&a,&b);
        int ans = INF;
        deque<int> cm[1000];
        for (j = 0; j < M; j++) {
            for (i = 0; i < a; i++) {
                while (!cm[j].empty() && A[i][j] >= A[cm[j].back()][j])
                    cm[j].pop_back();
                cm[j].push_back(i);
            }
        }
        for (; i <= N; i++) {
            deque<pair<int,int>> sq;
            for (j = 0; j < b; j++) {
                while (!sq.empty() && A[cm[j].front()][j] >= value(sq.back()))
                    sq.pop_back();
                sq.push_back(make_pair(cm[j].front(),j));
            }
            for (; j <= M; j++) {
                int mx = value(sq.front());
                int s = sum[i-1][j-1];
                if (i > a)
                    s -= sum[i-a-1][j-1];
                if (j > b)
                    s -= sum[i-1][j-b-1];
                if (i > a && j > b)
                    s += sum[i-a-1][j-b-1];
                ans = min(ans,mx*a*b-s);

                if (j == M) break;
                if (sq.front().second == j-b)
                    sq.pop_front();
                while (!sq.empty() && A[cm[j].front()][j] >= value(sq.back()))
                    sq.pop_back();
                sq.push_back(make_pair(cm[j].front(),j));
            }
            if (i == N) break;
            for (j = 0; j < M; j++) {
                if (cm[j].front() == i-a)
                    cm[j].pop_front();
                while (!cm[j].empty() && A[i][j] >= A[cm[j].back()][j])
                    cm[j].pop_back();
                cm[j].push_back(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}