平方分割のバケット法で区間の和を効率的に求める (UVa 12086 Potentiometers)

問題

個の可変抵抗が直列に繋がれている。

• 番目の抵抗を に変更
• 区間 の合成抵抗を出力(直列だから足すだけ)

という指示が来るので順番に処理せよ。

平方分割

抵抗もクエリも多いので普通に足すだけだとTLEする。
以前にあり本のFenwick Treeをコピペして解いたけど、平方分割のバケット法というテクニックを知ったので、その練習のためにやり直した。

このスライドが参考になった。 http://www.slideshare.net/iwiwi/ss-3578491
FenwickTreeは更新が ,出力も 、平方分割による 分木だと更新に ,出力に かかる。実際に掛かった時間はFenwickTreeは約0.21sec、平方分割は約0.43secくらいだった。更新が なのが優秀。

実装していてこれは賢いなーと思った。 バケット内の各要素に二分探索木を生やしたり、一般に 次元でやったりもするらしい。(だからtemplate<typename T> にしてある。) そういえば弾幕STGの本で、当たり判定の部分で16分割くらいにして別々に処理していた気がする。

template<typename T>
struct sqrt_tree{
    vector<T> data, baqet;
    T sq;
    sqrt_tree(vector<T> const& v) :data(v){
        sq = sqrt(data.size());
        baqet.assign((data.size() + sq - 1) / sq, 0);
        rep(i, data.size()) baqet[i / sq] += data[i];
    }
    T sum(int l, int r){
        T res = 0;
        // 同じバケット内にある
        if (l / sq == r / sq){
            loop(i, l, r) res += data[i];
        } else {
            int e = r / sq;
            // 完全に被っているバケット
            loop(i, (l + sq - 1) / sq, e) res += baqet[i];
            // 中途半端な左側のバケット
            if (l%sq){
                int e = sq*(l / sq + 1);
                loop(i, l, e)res += data[i];
            }
            // 中途半端な右側のバケット
            if (r%sq){
                loop(i, r - r%sq, r)res += data[i];
            }
        }
        return res;
    }
    void update(int i, T x){
        baqet[i / sq] -= data[i];
        data[i] = x;
        baqet[i / sq] += x;
    }
};

int main(){
    int t = 1;
    int n;
    while (scanf("%d", &n), n){
        if (t != 1) puts("");
        printf("Case %d:\n", t);
        t++;
        vl v(n);
        rep(i, n) scanf("%lld", &v[i]);
        sqrt_tree<ll> s(v);
        while (1){
            char op[8];
            scanf("%s", op);
            if (op[0] == 'M'){
                int l, r;
                scanf("%d %d", &l, &r);
                l--;
                printf("%lld\n", s.sum(l, r));
            }
            else if (op[0] == 'S'){
                int i; ll x;
                scanf("%d %lld", &i, &x);
                s.update(i - 1, x);
            }
            else{
                goto end;
            }
        }
    end:;
        /*cout << "DEBUG" << endl;
        rep(i, v.size())loop(j, i + 1, v.size() + 1){
        cout << i << " " << j << " " << s.sum(i, j) << endl;
        }*/
    }

}

TopCoder SRM #629 Div2

ooo 911->1089(+178) 11th とかなり調子が良かった。

Easy(250)

配列の連続な部分列の総和、の総和を求めよ。

nは小さいので愚直に足し算する。

class SumOfPower {
public:
    int findSum(vector<int> v) {
        int n = v.size();
        int ans = 0;
        rep(i, n)loop(j, i + 1, n + 1){
            ans += accumulate(v.begin() + i, v.begin() + j, 0);
        }
        return ans;
    }

Med(500)

1～aの目が出るサイコロAと、1～bの目が出るサイコロBを振ったとき、Aの目のほうが大きかった。Aの目の期待値を求めよ。

目の出方全ての場合に対して分母と分子を別々に求めて足してゆき、最後に分子/分母を返す。

class FixedDiceGameDiv2 {
public:
    double getExpectation(int a, int b) {
        double ans = 0;
        int c = 0;
        for (int aa = 1; aa <= a; aa++){
            for (int bb = 1; bb <= b; bb++){
                if (aa <= bb) continue;
                c++;
                ans += aa;
            }
        }

        return ans / c;
    }

Hard(1000)

解けた！！！(が、昔解いたこれ↓とほぼ同じだったので運が良かっただけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212 )

有向グラフが与えられる。v[1]からv[n]までの最短経路を求めよ。ただしそれぞれの経路で最大changes回だけグラフの重みをマイナスにできる。同じ辺の往復も可能で、自己ループもあるかもしれない。

changesが高々i回だけ使えるという制限で求めた最短距離の情報d[i][]が分かっているとき、さらにもう一回changesを使って良いことにしたらどうなるか考えると d[i] = min(d[a][v] + e.cost, d[a - 1][v] - e.cost) という漸化式が立つ。これでi=changesまで順番に更新していく。ダイクストラ以外だと少し工夫しないとTLEするらしい？

はじめ、戻り値がlong longになっているのに気づかずに全部intにしてsubmitする。その後慌てて直したけど結局間に合わず絶望する。が、よく考えたらintで普通に収まるじゃないか…

結局はAOJ0212で重みを1/2倍にできたのを-1倍に置き換えただけだけど、それを思いつき、ググって問題を特定するまでに結構時間を使ってしまった。(「最短距離 回数 半額」とかでググったけどなかなか見つからなかった)

const int inf = 1 << 29;
struct Edge { 
    int src, dst, cost;
    Edge(int src, int dst, int cost) : src(src), dst(dst), cost(cost){}
};
struct State {
    int cost, v;
    State(int cost, int v) :cost(cost), v(v){}
    bool operator<(const State& r) const{
        return cost > r.cost;
    }
};

typedef vector<vector<Edge>> Graph;

class NegativeGraphDiv2 {
public:
    long long findMin(int N, vector <int> s, vector <int> t, vector <int> w, int c) {
        Graph g(N + 1);
        int const E = s.size();
        rep(i, E) g[s[i]].emplace_back(Edge(s[i], t[i], w[i]));
        vi prev(N + 1, inf);
        rep(i, c + 1){
            vi cur(N + 1, inf);
            dijk(g, i, cur, prev);
            swap(cur, prev);
        }
        return prev[N];
    }

    void dijk(Graph const& g, int c, vi& cur, vi const& prev){
        priority_queue<State> q;
        q.push(State(0, 1));
        cur[1] = 0;
        while (q.size()){
            State p = q.top(); q.pop();
            int v = p.v;
            if (cur[v] < p.cost) continue;
            rep(i, g[v].size()){
                Edge const& e = g[v][i];
                int t = cur[v] + e.cost;
                if (c) t = min(cur[v] + e.cost, prev[v] - e.cost);
                if (cur[e.dst] > t){
                    cur[e.dst] = t;
                    q.push(State(t, e.dst));
                }
            }
        }
    }

AtCoder Beginner Contest #011

ooooで総合18th．やったぜ！

http://abc011.contest.atcoder.jp/
公式解説 http://www.slideshare.net/chokudai/abc011
解説ニコ生 http://live.nicovideo.jp/watch/lv183702185

A

C++03で提出してコンパイラエラーをもらう．ペナルティにはならないらしい．

int main(){
    int n;
    while (cin >> n){
        if (n == 12) cout << 1 << endl;
        else cout << n + 1 << endl;
    }
}

B

#include<cctype>が便利．Rubyにはcapitalizeというまんまそれなメソッドがあるが本番ではC++脳が先に回った

int main(){
    string s;
    cin >> s;
    s[0] = toupper(s[0]);
    rep(i, s.size())if (i){
        s[i] = tolower(s[i]);
    }
    cout << s << endl;
}

puts gets.chomp.capitalize

C

問題にかかれているのとは逆に0から初めて足し算してもよい． 0から始めて1,2,3を足していき、NG数を踏まずにi回以内の足し算でjを作るための足し算の最小回数をdp[i][j]とおく．

dp[i][]の更新に必要なのはdp[i-1][]だけなので，下のソースコードではdp[i+1]をnext，dp[i]をcurとおいている． i=0～350，j=1～3で，cnt[i + j] = min(cnt[i + j], cnt[i] + 1)の漸化式でcur[n]までの最短手数を求め，最終的にcur[n]が100以下になるか判定する．

貪欲でも解けるらしい．

typedef vector<int> vi;
typedef vector<bool> vb;
int main(){
    int n;
    while (cin >> n){
        vi cnt(400, inf);
        vb ng(400);
        rep(i, 3){
            int x; cin >> x;
            ng[x] = true;
        }
        bool ok;
        if (ng[0]) ok = false;
        else {
            cnt[0] = 0;
            rep(i, 350){
                if (cnt[i] == inf) continue;
                loop(j, 1, 4){
                    if (!ng[i + j]){
                        cnt[i + j] = min(cnt[i + j], cnt[i] + 1);
                    }
                }
            }
            if (cnt[n] <= 100) ok = true;
            else ok = false;
        }

        if (ok) cout << "YES";
        else cout << "NO";
        cout << endl;
    }
}

D

まずxもyもDで割れない時は答えはNOで，割れるときはx,y,Dを全てDで割り，D=1で考える． 漸化式を立てて普通にDPだが，DPテーブルの大きさをWHとしたとき，O(NH*W)だと微妙な定数倍高速化をしないと通らない．

• doubleの誤差を考え，答えの許容誤差の10^-9に影響しないような値は切る
• 同様に誤差を考えてDPテーブルを縮める
• ループ展開する

で通った．個人的にはあまり好きではないけど，こういうテクニックを使わせる点で教育的なのかなと思った．

→これは想定解法ではないらしく、公式解説にもっと賢い方法があります．

int main(){
    int n, d, x, y;
    while (cin >> n >> d >> x >> y){
        double p;
        if (x%d == 0 && y%d == 0){

            const int w = 350;
            const int h = 350;

            x /= d; y /= d;
            x += w / 2; y += h / 2;

            if (!in(x, y, w, h)) p = 0;
            else {

                vvd cur(h, vd(w, 0));
                cur[h / 2][w / 2] = 1;

                int const dx[] = { 1, 0, 0, -1 };
                int const dy[] = { 0, 1, -1, 0 };

                rep(i, n){
                    vvd next(h, vd(w, 0));
                    rep(y, h)rep(x, w){
                        // ループ展開(dx[],dy[]をループで回るとTLE)
                        int nx, ny;
                        nx = x + 0;
                        ny = y + 1;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto aaa;
                        next[ny][nx] += cur[y][x] / 4;

                    aaa:;

                        nx = x + 0;
                        ny = y + -1;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto bbb;
                        next[ny][nx] += cur[y][x] / 4;

                    bbb:;

                        nx = x + 1;
                        ny = y + 0;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) goto ccc;
                        next[ny][nx] += cur[y][x] / 4;

                    ccc:;

                        nx = x + -1;
                        ny = y + 0;
                        if (!in(nx, ny, w, h) || cur[y][x] < 1e-10) continue;
                        next[ny][nx] += cur[y][x] / 4;
                    }
                    swap(next, cur);
                }
                p = cur[x][y];
            }
        }
        else {
            p = 0;
        }

        cout << fixed << setprecision(30) << p << endl;
    }
}

Codeforces Round #253 (Div. 2)

http://codeforces.com/contest/443

だめだった oo--- 1570 (-44), expert Rank: 401

A

パーサの手書きもいいけどstringstreamが楽？

int main(){
    int n;
    string s;
    while (getline(cin,s)){
        rep(i,s.size()){
            if (isalpha(s[i])) continue;
            s[i] = ' ';
        }
        stringstream ss(s);
        string k;
        set<string> ans;
        while (ss >> k){
            ans.insert(k);
        }

        cout << ans.size() << endl;
    }
}

B

tandem repeat(日本語でなんて言うんだろう)とは結局、長さが偶数で前半と後半が等しい文字列。前半をt1、後半をt2とする。t1を入力文字列のi番目から始まる長さwの文字列、t2がi+w番目から始まる長さwの文字列として、t1=t2となるように取れる場合にwを更新していった。

int main(){
    string s;
    int n;
    while (cin >> s >> n){
        int ans = 0;
        string t1, t2;
        for (int i = 0; i < s.size(); i++){
            for (int w = 1; w <= s.size() + n; w++){
                if (i + w < s.size()){ // t1がはみ出ない
                    if (i + w + w < s.size()){ // t2がはみ出る
                        t1 = s.substr(i, w);
                        t2 = s.substr(i + w, w);
                        if (t1 == t2){
                            ans = max<int>(ans, w);
                        }
                    }
                    else { // t2がはみ出ない
                        t1 = s.substr(i, w);
                        t2 = s.substr(i + w);
                        bool f = t1.substr(0, t2.size()) == t2;
                        if (f && i + w + w <= s.size() + n){
                            ans = max<int>(ans, w);
                        }
                    }
                }
                else { // t1がはみ出る(t2も必ずはみ出る)
                    t1 = s.substr(i);
                    if (w + w <= t1.size() + n){
                        ans = max<int>(ans, w);
                    }
                }
                //cout << t1 << " " << t2 << " " << ans << endl;
            }
        }
        cout << ans*2 << endl;
    }
}

C以降のあらすじ

Cの実装意外と面倒くさそうだなあ…他の問題見るか →DがDPっぽいなあ(大嘘) →Dにはまる →D分からなさそうだしEも無理っぽい →C間に合わない →絶望

CodeforcesのAPIを使ってratingの度数分布図を作った

最近CodeforcesにAPIが実装されました。めでたい。

例えば http://codeforces.com/api/user.ratedList?activeOnly=trueにアクセスすると全てのアクティブなユーザーの情報が返ってくる。(ブラウザだと少し重いので注意) これをrubyでパースして、エクセルで度数分布図を描いてみた。

僕は現時点で1614なので平均より少し上くらいですね。div1に上がりたいですがCを安定して解けない現状だときついですね…

AtCoder Regular Contest #025

放置してましたが久しぶりに書きます http://arc025.contest.atcoder.jp/

結果はoox-でしたがシステムのミスでノーゲームになったのでレーティングの変動はありません。悲しい。

A

大きい方を貪欲にとっていく。#include <algorithm>し忘れて一回CEする。(VisualStudioではコンパイルが通ってしまう)

int main(){
    vi a(7), b(7);
    rep(i, 7) cin >> a[i];
    rep(i, 7) cin >> b[i];
    int ans = 0;
    rep(i, 7) ans += max(a[i], b[i]);
    cout << ans << endl;
}

B

グリッドのマスに値があって累積和をとるやつ。典型問題らしい。白黒の市松模様になっていて、部分長方形の黒い部分の和と白い部分の和が等しくない場合は無視する。白黒別々に配列に持ってDPした。いつかのABCで書いた気がしたのでそれを探してきてコピペする。

公式解説の、白いところに-1を掛けると1回だけDPして和が0になる所を探すだけでOKというの賢いなあ。

int main(){
    int h, w;
    while (cin >> h >> w){
        vvi vb(h, vi(w));
        vvi vw(h, vi(w));
        rep(i, h)rep(j, w){
            if ((i + j) & 1) cin >> vw[i][j];
            else cin >> vb[i][j];
        }

        vvi dpw(h + 1, vi(w + 1));
        vvi dpb(h + 1, vi(w + 1));

        rep(i, h)rep(j, w){
            dpw[i + 1][j + 1] = dpw[i + 1][j] + dpw[i][j + 1] - dpw[i][j] + vw[i][j];
            dpb[i + 1][j + 1] = dpb[i + 1][j] + dpb[i][j + 1] - dpb[i][j] + vb[i][j];
        }

        int ans = 0;
        rep(i, h)rep(j, w){
            for (int tw = 1; tw <= h - i; ++tw) {
                for (int th = 1; th <= w - j; ++th) {
                    int P = tw*th;
                    int ww = dpw[i + tw][j + th] - dpw[i][j + th] - dpw[i + tw][j] + dpw[i][j];
                    int bb = dpb[i + tw][j + th] - dpb[i][j + th] - dpb[i + tw][j] + dpb[i][j];
                    if (bb == ww) ans = max(ans, P);

                }
            }
        }
        cout << ans << endl;
    }
}

C

どちらも最適に動くので最短経路をとる。また、無向グラフなので先にゴールを決めてスタートを地点を目指してもよい。まずゴールから他の全ての頂点までの最短路を求める。カメの速さをt, うさぎの速さをrとおく。カメの頂点の距離がd1のとき、カメはtt = d1/tの時間がかかる。これよりも多くの時間がかかる頂点の数を数える。ウサギの頂点の距離をd2とおくと、tr = d2/rの時間がかかる。tr < tt ⇔ d2 > r/t * d1となるような頂点の数を足せばいいが、二分探索か尺取じゃないとTLEする。

r<cの場合と答えがintに入らないこともあるのに気づかなくてWAしまくる。結局とけず…

int main(){
    int n, m, r, t;
    while (cin >> n >> m >> r >> t){
        Graph g(n);
        rep(i, m){
            int a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            g[a].eb(a, b, c);
            g[b].eb(b, a, c);
        }
        ll ans = 0;
        rep(i, n){
            vi hoge;
            vi d(n);
            dijk(g, i, d, hoge); // グラフgでiから各頂点までの最短距離をdに入れる
            sort(all(d));
            rep(j, n)if (j){
                int tt = d[j];
                int tr = tt * r / t + 1;
                int k = lower_bound(all(d), tr) - d.begin();
                int c = -(k <= j);
                c += n - k;
                ans += c;
            }
        }
        cout << ans << endl;
    }
}

lower_boundとupper_bound

基本的なことが分かってなかった

これら2つはC++のalgorithmヘッダに含まれている関数です。ここよりしっかりした多くの解説サイトに書かれている思いますが、ソート済みの配列で

• std::lower_bound(begin, end, val)は、区間[begin,end)でval以上の最小の値を指すイテレータ
• std::upper_bound(begin, end, val)は、区間[begin,end)でvalより大きいの最小の値を指すイテレータ

を返します。二分探索で区間を移る時の条件分岐が<か<=かの違いです。

つまり

ソート済みのコンテナのvmin以上vmax以下の範囲を走査したいときは、次のように書けばよいということになります。

vector<int> v(10);
for(int i = 0; i < 10; i++) v[i] = i/2;
int vmin = 1, vmax = 3;
vector<int>::iterator lb = lower_bound(v.begin(), v.end(), vmin);
vector<int>::iterator ub = upper_bound(v.begin(), v.end(), vmax);
for(vector<int>::iterator it = lb; it != ub; ++it){
    cout << *it << ' ';
}
cout << endl;
// 1 1 2 2 3 3 

この使い方を知らなかったわけです。だからupper, lower(上下の)bound(境界)っていうのか...

equal_range

追記

equal_rangeで、第3引数に渡した値と等しい領域の両端のイテレータのペアが返ってきます。 second-firstでコンテナ内のその要素を数えられます。

auto range = equal_range(v.begin(), v.end(), 4)
for(vector<int>::iterator it = range.first; it != range.second; ++it){
    cout << *it << ' ';
}
cout << endl;
// 4 4 

cout << range.second - range.first << endl; // 2 (vに含まれる'4'の個数)