はまやんはまやんはまやん

hamayanhamayan's blog

Awkward Pairs [CodeChef ProCon 2018 D]

Contest: https://www.codechef.com/PROC2018/problems/PROC18C
Practice: https://www.codechef.com/problems/PROC18C

1≦L≦R≦10^18が与えられる。
以下の条件を満たすペアの組み合わせ数mod(10^9+7)でを答えよ。

ペア(x,y)が以下の条件を満たす

  • xもyも[L,R]にある
  • xとyのそれぞれの桁の総和を取ったものをxx, yyとするとxxとyyは互いに素

前提知識

考察過程

1. 桁の総和の最大は9*17位なので小さい
2. [L,R]の中で「総和がiとなる数の個数」を数えれば答えるのは簡単そう
3. よくあるテクで[L,R]の計算ではなく[0,R]-[0,L-1]で計算するようにしよう
4. [0,x]の中で「総和がiとなる数の個数」を数えるにはどうすればいいか
5. 桁DPの典型問題

解法

https://www.codechef.com/viewsolution/19758961

solve関数から説明するが、まずはcnt配列を作る。
cnt[i] := [L,R]の中で桁総和がiとなる数が何通りあるか。
これが分かれば、総和の(i,j)を全探索して、gcd(i,j)=1となるi,jについてcnt[i]*cnt[j]の総和を取れば答え。
 
cnt配列を作る部分が問題である。
[L,R]について考えるのではなく、[0,R]-[0,L-1]と言い換えて、[0,x]で問題を考えるようにする。
f(x) := [0,x]の範囲におけるcnt配列を返す
 
最終的に問題となるのは「[0,x]の中で桁総和がiとなる数が何通りあるか」という問題である。
これは桁DPで解決しよう。
dp[dgt][sm][isless] := dgt桁まで確定していて、桁総和がsm、数xよりも小さいかがislessである数の個数
※ isless = 0でここまでxと上位桁が等しい、=1で既にxより小さいことが確定
遷移はよくある桁DPなので、頑張って書く。

ll L, R;
ll dp[22][250][2]; // dp[dgt][sm][isless]
string S; int N;
//---------------------------------------------------------------------------------------------------
vector<ll> f(ll x) {
    rep(dgt, 0, 22) rep(sm, 0, 250) rep(isless, 0, 2) dp[dgt][sm][isless] = 0;
    dp[0][0][0] = 1;
 
    S = to_string(x);
    N = S.length();
 
    rep(dgt, 0, N) rep(sm, 0, 200) rep(isless, 0, 2) {
        int c = S[dgt] - '0';
        rep(i, 0, 10) {
            if (isless == 0 and c < i) continue;
            if (c == i) dp[dgt + 1][sm + i][isless] += dp[dgt][sm][isless];
            else dp[dgt + 1][sm + i][1] += dp[dgt][sm][isless];
        }
    }
 
    vector<ll> res(200);
    rep(sm, 0, 200) rep(isless, 0, 2) res[sm] += dp[N][sm][isless];
    return res;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> L >> R;
 
    auto a = f(R);
    auto b = f(L - 1);
 
    vector<ll> cnt(200);
    rep(i, 0, 200) cnt[i] = a[i] - b[i];
 
    mint ans = 0;
    rep(i, 1, 200) rep(j, i + 1, 200) if(gcd(i,j) == 1) ans += mint(cnt[i]) * mint(cnt[j]);
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
} 

Algebra Score [CodeChef ProCon 2018 C]

https://www.codechef.com/problems/PROC18D

N(≦200)個の数とN-1個の+,-演算子が順番に並んでいる。
適切に括弧をつけることで計算結果を最大化せよ。

前提知識

考察過程

1. そもそもyukicoderで似た問題を見た これ
2. この問題の解法のエッセンスはmaxとminを持ってDPをするというところ
3. この問題もそのように取り組んでいこう
4. 括弧を作るとその部分がひとまとまりになる
5. 区間DPすればいいのでは?

解法

https://www.codechef.com/viewsolution/19758928

区間DPする。
rec(l,r) := [l,r]の区間の計算結果として得られる(最大値,最小値)
区間DPの中身は、l≦c<rとなるcを全探索し、rec(l,c)とrec(c+1,r)を使って計算する。
メモ化でO(N^3)なので間に合う。

int N, A[202]; char O[202];
//---------------------------------------------------------------------------------------------------
int vis[202][202];
pair<ll, ll> memo[202][202];  // (max,min)
pair<ll, ll> rec(int l, int r) { // [l,r]
    if (vis[l][r]) return memo[l][r];
    vis[l][r] = 1;
 
    if (l == r) return memo[l][r] = { A[l], A[r] };
 
    pair<ll, ll> res = { -infl, infl };
    rep(c, l, r) { // [l,c], (c,r]
        auto x = rec(l, c);
        auto y = rec(c + 1, r);
 
        vector<ll> xx = { x.first, x.second };
        vector<ll> yy = { y.first, y.second };
 
 
        rep(i, 0, 2) rep(j, 0, 2) {
            if (O[c] == '+') {
                chmax(res.first, xx[i] + yy[j]);
                chmin(res.second, xx[i] + yy[j]);
            }
            else {
                chmax(res.first, xx[i] - yy[j]);
                chmin(res.second, xx[i] - yy[j]);
            }
        }
    }
 
    return memo[l][r] = res;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    cin >> A[0];
    rep(i, 1, N) cin >> O[i-1] >> A[i];
 
    rep(i, 0, N) rep(j, 0, N) vis[i][j] = 0;
    auto p = rec(0, N - 1);
    printf("%lld\n", p.first);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
} 

DigitRotation [SRM 736 Div1 Easy]

http://community.topcoder.com/stat?c=problem_statement&pm=14958

とても大きい数Xがある。
この数に対して、以下の操作を行う。
 

  • a<b<cを用意し、a桁目をb桁目に、b桁目をc桁目に、c桁目をa桁目に数を移動させる
  • このとき、leading-zeroとなるのは不正な操作である

 
異なるa,b,cについて以上の操作を行うとき、有効な操作によって得られる数の総和をmod 998244353で求めよ。

解法

|X|=nとする。
本当はO(n^3)で解けるのだが、以下はO(n^2)で解いてある。
 
a,cを固定して、bをまとめて計算することにする。
不正な操作はa=0であり、X[c]が'0'の場合はleading-zeroとなってしまうので、この場合はスキップしよう。
それ以外の場合を考える。
 
m=c-a-1としておく。これはbの組み合わせ数である。
sm[i] := i桁目の数そのもの
P[i] := i桁目の基数の累乗(最下位桁から1, 10, 100, ...)
A[i] := sm[i] * P[i]
これを全て累積和を取れるようにしておく。
getsm, getPP, getA(l, r) := [l,r]での累積和
各計算の簡単な説明を以下に残しておく。
 
ans += getA(0, a - 1) * m;
m通りの数に対して、[0,a)の部分は同じ数になる。
 
ans += mint(X[c] - '0') * P[a] * m;
操作によりc桁目の数がa桁目に移動する。
c桁目の数はa桁目にm回現れることになる。
 
ans += getsm(a + 1, c - 1) * P[c];
操作によりb桁目の数がc桁目に移動する。
b桁目の数としてありえるのが、[a+1,c)の数全てであるため、その総和を取ってc桁目として足しておく。
 
ans += mint(X[a] - '0') * getPP(a + 1, c - 1);
a桁目の数はb桁目に移動する。
b桁目はa+1桁目、a+2桁目、..., c-1桁目になりうるので、この全パターンを足す。
[a+1,c)桁目の基数の累乗の総和より、計算しておこう。
 
ans += getA(a + 1, c - 1) * (m - 1);
[a,c)の間のb桁目以外の数はそのまま残る。各桁m-1回同じ位置に現れることになる。
 
ans += getA(c + 1, n - 1) * m;
m通りの数に対して、[c+1,n)の部分は同じ数になる。

mint P[505], PP[505];
mint getPP(int l, int r) {
    if (l > r) return 0;
    mint res = PP[r];
    if (l) res -= PP[l - 1];
    return res;
}
mint sm[505];
mint getsm(int l, int r) {
    if (l > r) return 0;
    mint res = sm[r];
    if (l) res -= sm[l - 1];
    return res;
}
mint A[505];
mint getA(int l, int r) {
    if (l > r) return 0;
    mint res = A[r];
    if (l) res -= A[l - 1];
    return res;
}
struct DigitRotation {
    int sumRotations(string X) {
        int n = X.length();

        P[0] = 1;
        rep(i, 1, n) P[i] = P[i - 1] * 10;
        reverse(P, P + n);

        PP[0] = P[0];
        rep(i, 1, n) PP[i] = PP[i - 1] + P[i];

        sm[0] = X[0] - '0';
        rep(i, 1, n) sm[i] = sm[i - 1] + mint(X[i] - '0');

        A[0] = mint(X[0] - '0') * P[0];
        rep(i, 1, n) A[i] = A[i - 1] + mint(X[i] - '0') * P[i];

        mint ans = 0;
        rep(a, 0, n) rep(c, a + 2, n) {
            if (a == 0 and X[c] == '0') continue;
            int m = c - a - 1;

            ans += getA(0, a - 1) * m;
            ans += mint(X[c] - '0') * P[a] * m;
            ans += getsm(a + 1, c - 1) * P[c];
            ans += mint(X[a] - '0') * getPP(a + 1, c - 1);
            ans += getA(a + 1, c - 1) * (m - 1);
            ans += getA(c + 1, n - 1) * m;
        }

        return ans.get();
    }
};

The hat [Codeforces Round #503 (by SIS, Div. 1) B]

http://codeforces.com/contest/1019/problem/B

インタラクティブ問題。
N要素(Nは偶数)の配列Aがある。
この配列は以下のような特徴がある。

  • 隠されている
  • 円状である。つまり、1番目とN番目は隣接していると考える
  • 隣接している要素の数はちょうど1だけ離れている

行えるクエリは2種類
質問クエリ「? i」i番目の要素の数を聞く
回答クエリ「! i」i番目の要素が答えであると答える。このクエリ後は即座に終了する必要がある
 
60回以下の質問でi番目の数とi+N/2番目の数が等しいようなiを答えよ。
存在しないなら-1と答える。

考察過程

1. 60回以下なので二分探索系なのは確定
2. 隣接要素はちょうど1だけ離れているというのをうまく使えないか
3. 天啓「B[i] = A[i+N/2] - A[i]」を使えばいいのでは?
4. B[i]とB[i+1]の差を考えてみると0, +2, -2のどれかになっている
5. B[i]=0であれば、答えの条件を満たす
6. しかもB[i+N/2] = -B[i]となっている
7. 中間値の定理のような雰囲気を感じる
8. これを考えるとB[i], B[i+1], ... , B[i + N/2]はB[i], B[i+1], ..., -B[i]なので中間値の定理的に答えが必ず存在しそう
9. B[i]がもともと奇数なら答えが無い(これはN/2が奇数の場合は奇数となる)
10. それ以外なら答えがあるので、中間値の定理と二分探索を使って、答えを導いていく
 

解法

http://codeforces.com/contest/1019/submission/41484240

答えが無い場合はN/2が奇数の場合なので、このときは除いておこう。
N/2が偶数であれば答えは必ず存在する。

B[i] = A[i+N/2] - A[i]とする。
それに伴って、質問をするときは、いつもA[i + N/2]とA[i]を聞くことにする。
diff(i) := A[i+N/2]-A[i]を返す
 
二分探索をする。
L=0, R=N/2が初期状態である。
するとLx = B[L], Rx = B[R] = -B[L]。
二分探索をするが、LxとRxの符号が異なるように維持しながら二分探索をしていく。
LxとRxの符号が異なるようにしていれば、その間に中間値の定理より、0となる要素の存在を維持できる。
あとは、0となる要素が出てくるまで頑張る。

int N;
//---------------------------------------------------------------------------------------------------
int test = 0;
int testcase[8] = { 1,2,1,2,3,4,3,2};
int ask(int i) {
    if (test) return testcase[i];

    printf("? %d\n", i + 1);
    fflush(stdout);

    int x; cin >> x;
    return x;
}
void ans(int i) {
    printf("! %d\n", i + 1);
    fflush(stdout);
}
int diff(int i) {
    if (test) return testcase[i + N / 2] - testcase[i];

    int a = ask(i);
    int b = ask(i + N / 2);
    return b - a;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    if ((N / 2) % 2 == 1) {
        ans(-2);
        return;
    }

    int L = 0, R = N / 2;
    int Lx = diff(L);
    int Rx = -Lx;
    if (Lx == 0) {
        ans(0);
        return;
    }
    while (L + 1 != R) {
        int md = (L + R) / 2;
        int x = diff(md);

        if (x == 0) {
            ans(md);
            return;
        }

        if (Lx < 0 and x < 0) {
            Lx = x;
            L = md;
        } else if(Rx < 0 and x < 0) {
            Rx = x;
            R = md;
        }
        else if (0 < Lx and 0 < x) {
            Lx = x;
            L = md;
        }
        else if (0 < Rx and 0 < x) {
            Rx = x;
            R = md;
        }
    }
}

Elections [Codeforces Round #503 (by SIS, Div. 1) A]

http://codeforces.com/contest/1019/problem/A

N人の有権者とM種類の政党がある。
i番目の人はもともとP[i]番目の政党に投票しているが、C[i]円支払うことで別の政党に投票してくれる。
1番目の政党が選挙で勝つには最小でいくら必要か。
※選挙で勝つには他の政党よりも多くの票を集める必要がある(同じ票数は駄目)

考察過程

1. 3*10^3なので、2乗くらいなら間に合う感じがある
2. なにか全探索するものを考える→1番目の政党が最終的に集めた票数で全探索が良いのでは?
3. 1番目の政党が集めた票数が分かれば、それ以上の票数を持っている他の政党から票を何票奪えばいいか分かる
4. 奪う場合はコストが小さい人から説得すればよい(priority_queue)
5. 最後にまだ票数が足りてない場合は全体を見て、小さい人から説得する(priority_queue)

解法

http://codeforces.com/contest/1019/submission/41487872

この解法はO(NMlogM)解法であるが、かなりギリギリである。
うまくやればlogが取れるらしい(O(N(N+M))があるとTLで見た気がする)。
 
solve(win) := 1番目の政党がwin票だけ集めて選挙に勝った場合に必要な最小コスト
これを1~N/2くらいまで回して最小コストが答えになる。
 
solve関数内では、政党毎に以下の処理を行う
1. priority_queueを使って、コストが小さい順に取り出せるようにしておく
2. 票数がwin以上であれば、win未満になるように、コストが小さい順に説得していく
3. win未満になったら、残りは全体のpriority_queueに入れておく
これで全ての政党はwin未満にすることができた。
場合によっては、これをしただけでは1番目の政党の獲得票数がwin以上になっていない場合があるので、
手順3で作った全体のpriority_queueを使って、1番目の政党の各得票数がwin以上になるように取っていく。

int N, M, P[3010], C[3010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
ll solve(int win) {
    ll res = 0;

    map<int, min_priority_queue<int>> que;
    min_priority_queue<int> all;
    rep(i, 0, N) que[P[i]].push(C[i]);

    int me = que[1].size();
    fore(p, que) {
        int party = p.first;
        auto cost = p.second;

        if (party == 1) continue;

        while (win <= cost.size()) {
            res += cost.top();
            cost.pop();
            me++;
        }

        while (!cost.empty()) {
            all.push(cost.top());
            cost.pop();
        }
    }

    

    while (me < win) {
        me++;
        res += all.top();
        all.pop();
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> P[i] >> C[i];

    ll ans = infl;
    rep(win, 1, min(N + 1, N / 2 + 5)) chmin(ans, solve(win));
    cout << ans << endl;
}

Candy Distribution [AtCoder Beginner Contest 105 D]

https://beta.atcoder.jp/contests/abc105/tasks/abc105_d

考察過程

1. よくあるテクを使う
2. 「右側を固定して、条件を満たす左端を高速に数え上げる」
3. 区間和に関する問題なので、先頭からの累積和を使って条件を考える
4. [l,r]の区間和がMの倍数 ↔ [0,l)と[0,r]のそれぞれの累積和がmodMで等しい
5. mapを使ってこれまでの累積和modMの個数をカウントしておけば解ける

解法

https://beta.atcoder.jp/contests/abc105/submissions/2994810

「右側を固定して、条件を満たす左端を高速に数え上げる」テクを使う。
「[l,r]の区間和がMの倍数 ↔ [0,l)と[0,r]のそれぞれの累積和がmodMで等しい」ことが言える。
よって、rを固定した時に上の条件を満たすlを数え上げて総和を取ればいい。
「cnt[i] := 今までの累積和の中でmodMがiであるものの個数」を用意する。
あとは、累積和であるsmを使いながら答えを求めていく。

int N, M, A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
 
    map<int, int> cnt;
    cnt[0] = 1;
    ll ans = 0, sm = 0;
    rep(i, 0, N) {
        sm += A[i];
        ans += cnt[sm%M];
        cnt[sm%M]++;
    }
    cout << ans << endl;
}

Cakes and Donuts [AtCoder Beginner Contest 105 B]

https://beta.atcoder.jp/contests/abc105/tasks/abc105_b

解法

https://beta.atcoder.jp/contests/abc105/submissions/2994762

4ドルと7ドルで支払うパターンを全探索する。
合計が100ドル以下なので、4,7ドルも100個を上限として良い。
yes,no問題は関数を分けるのがオススメ。

int N;
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    rep(d4, 0, 101) rep(d7, 0, 101) if (d4 * 4 + d7 * 7 == N) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cout << solve() << endl;
}