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

h_nosonの日記

競プロなど

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

問題を見てまず考えること

問題を見て,まず考えるべきことを問題の種類別にまとめていく.
これから追加していくつもり.また,当たり前になってきたものは消していくかも.

クエリ

  • クエリを先読みしてソートしたりする

勝ち負けゲーム

  • 対称性を作れないか

探索系

  • 一度全探索の解法を考える

幾何

  • 点がたくさん与えられてそれらすべてに操作を行い何かする

→凸包を使って最遠点のみ処理を行ったり,分割統治法を使って最近点のみ処理を行う

最大値・最小値

  • 何かの条件を満たす最大値・最小値

→二分探索

組み合わせの数

  • 包除原理

yukicoder No.103 素因数ゲーム リターンズ

問題
No.103 素因数ゲーム リターンズ - yukicoder
N個の整数M_1,M_2,...,M_Nが与えられる.
一度の操作で任意の整数M_iをその素因数で割ることができる.同じ素因数ならば2回まで同時に割れる.
AliceとBobが交互に操作を行うとき,すべての整数を1にできるのはどちらか.

解法
M_igrundy数を求める.0を負けの状態,1,2を勝ちの状態とすると
1=(状態0),2=(状態1),2^2=(状態2),2^3=(状態0),2^4=(状態1),...
としてルールに従うと,(状態0)から(状態0)にすることはできず,(状態1),(状態2)からは(状態0)にすることができるということが分かる.つまり,指数部\bmod3を状態にすればよくなる.
M_i=\prod p_j^{a_j}と表すとき,grundy数はすべての a_j\bmod3排他的論理和となる.後はすべてのM_igrundy数について排他的論理和をとれば勝敗がわかる.

ソースコード

#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, j, n;
    int m[100], grundy[100];
    cin >> n;
    rep (i,n) cin >> m[i];
    rep (i,n) {
        map<int,int> mp;
        int x = m[i];
        for (j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                mp[j]++;
                x /= j;
                j--;
            }
        }
        mp[x]++;
        grundy[i] = 0;
        for (auto p : mp)
            grundy[i] ^= p.second % 3;
    }
    int ans = 0;
    rep (i,n) ans ^= grundy[i];
    if (ans == 0)
        cout << "Bob" << endl;
    else
        cout << "Alice" << endl;
    return 0;
}