競プロerキャンプ in 関東

8/17~18の間に行われた競プロerキャンプ in 関東。達也さん(@tatuyan_edson)、迷路さん(@pazzle1230)を中心に私含め5名の少数人数ながら、楽しい時間を過ごすことが出来ました。

さて、今回はその合宿初日に行われたVirtualContest(https://vjudge.net/contest/178834)の解説を行います。といっても最後の1問が解けていないのですが…

A - Nearly Lucky Number

問題概要

Lucky Numberとは数字の各桁が4か7のみの数字のことです。与えられた数字のLucky Numberである桁数がLucky Numberであるか判定しなさい。

http://codeforces.com/problemset/problem/110/A

解説

愚直に10で割った剰余が4か7か判定し、元の数を10で割る、ということを繰り返します。しかし、そんな気も起らなかったので、入力を文字列として受け取ることで1桁ずつ丁寧に見ています。

n = input()
cnt = 0
for i in n:
    if i == '4' or i == '7':
        cnt += 1
flag = True
if cnt == 0:
    flag = False
while cnt > 0:
    i = cnt % 10
    cnt //= 10
    if i != 4 and i != 7:
        flag = False
        break
if flag:
    print("YES")
else:
    print("NO")

B - Lucky Sum of Digits

問題概要

各桁の和がnに等しい最小のLucky Numberを求めよ。

http://codeforces.com/problemset/problem/110/C

解説

各桁に使えるのは4と7のみなので、使えるだけ7を使うと桁数を小さく出来ます。また、7の個数が決まれば4の個数は自然と求まり、求めるLucky Numberは出来るだけ4を先に出力したものとなります。

int main() {
    int n; cin >> n;
    for (int i = n/7; i>=0; i--) {
        if ((n - i * 7) % 4 == 0) {
            int j = (n - i * 7) / 4;
            string s = "";
            rep(k, j)   s+="4";
            rep(k, i)   s+="7";
            cout << s << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

C - Lucky String

問題概要

各アルファベットがLucky Numberだけ離れている文字列で、辞書順最小の長さnのものを求めよ。

http://codeforces.com/problemset/problem/110/B

解説

基本はなるべくaを使いたいです。すると、aの間隔は4です。

a〇〇〇a〇〇〇a…のようになるのですが、これはabcdabcda…とするのが最適、というのはすぐ浮かぶのではないでしょうか。

int main() {
    int n; cin >> n;
    string ret = "";
    rep(i, n)   ret += 'a' + (i % 4);
    cout << ret << endl;
}

D - Lucky Tree

問題概要

木の各枝に重みが与えられている。頂点iと頂点j、頂点iと頂点kを結ぶパス上にそれぞれ1つ以上のLucky Numberの重みを持つ枝が存在する(i,j,k)の組(i,j,kはそれぞれ異なる)の個数を求めよ。

http://codeforces.com/problemset/problem/110/E

解説

取り敢えず木DPで考える→どう頑張っても1回のDFSじゃ根しか求まらない→あ、これ†全方位木DP†だ…→過去に解いたこと無いのでパス

という流れでスルーを決め込みました。

さて、全方位木DPですが、1回DFSを行って根の答えを求めます。これには「見ている頂点より下に頂点がいくつあるか」「見ている頂点から下って行ったとき、Lucky Numberを持つ枝を通る頂点の数」を記録していれば求まります。これを解くと、根をiとする答えが得られます。

その後、他の頂点をiとした答えを求めるのですが、これはLucky Numberの重みを持つ枝でつながっているならそこより下のLucky Numberの重みでない枝で繋がっている頂点のみがj,kの対象から外れ、それ以外はすべて対象になります。また、Lucky Numberで繋がっていないなら、これは親の通り数と同じです。

後はそれらを足すだけです。

bool isLuckyNumber(int n) {
    if (n == 0)  return false;
    while (n > 0) {
        if (n % 10 != 4 && n % 10 != 7)   return false;
        else  n /= 10;
    }
    return true;
}

int n;

vector<pair<int, bool>> edge[100010];
ll node[100010];
ll cnt[100010];
ll ret[100010];

void solve1(int pos, int parent) {
    cnt[pos] = 0;  node[pos] = 1;
    rep(i, edge[pos].size()) {
        int to = edge[pos][i].fst;
        if (to == parent) continue;
        solve1(to, pos);
        node[pos] += node[to];
        if (edge[pos][i].scn) {
            cnt[pos] += node[to];
        }
        else {
            cnt[pos] += cnt[to];
        }
    }
}

void solve2(int pos, int parent) {
    rep(i, edge[pos].size()) {
        int to = edge[pos][i].fst;
        if (to == parent) continue;
        if (edge[pos][i].scn) {
            ll unode = n - (node[to] - cnt[to]);
            ret[to] = unode*(unode - 1);
            solve2(to, pos);
        }
        else {
            ret[to] = ret[pos];
            solve2(to, pos);
        }
    }
}

int main() {
    cin >> n;
    srep(i, 1, n) {
        int u, v, w;   cin >> u >> v >> w;
        bool t = isLuckyNumber(w); u--;    v--;
        edge[u].push_back(mp(v, t));
        edge[v].push_back(mp(u, t));
    }
    solve1(0, -1);
    ret[0] = cnt[0] * (cnt[0] - 1);
    solve2(0, -1);
    ll ans = 0;
    rep(i, n)   ans += ret[i];
    cout << ans << endl;
    return 0;
}

E - Lucky Probability

問題概要

[pl,pr]の中から1つランダムに数を選び、それをaとします。[vl,vr]の中から1つランダムに数を選び、それをbとします。[min(a,b),max(a,b)]にあるLucky Numberの個数が丁度k個になる確率を求めよ。

http://codeforces.com/problemset/problem/110/D

解説

区間ごとに区切って尺取り法やれば解けます。という発想が一瞬で浮かぶのですが、実装に苦労しました。

少し考えてみると、Lucky Numberって109までに1024回程度しか出てこないと気づきました。適当に配列に保持しておくと、k個先が簡単に求まるので楽でした。
後は上手く区間を区切るのと、左右逆にして成り立つ場合があることに気を付けることぐらいです。

ll getNextLNumber(ll i) {
    ll ret = 7;
    ll cnt = 1;
    while (ret <= i)   ret = ret * 10 + 7, cnt *= 10;
    while (cnt > 0) {
        if (ret - cnt * 3 > i)    ret -= cnt * 3;
        cnt /= 10;
    }
    return ret;
}

bool isLuckyNumber(ll a) {
    if (a == 0)  return false;
    while (a > 0) {
        ll i = a % 10; a /= 10;
        if (i != 4 && i != 7)   return false;
    }
    return true;
}

vector<ll> llist;
ll k;

ll solve(ll pl, ll pr, ll vl, ll vr) {
    pl--;   vr++;
    int s = 0;
    while (llist[s] < pl)  s++;
    while (llist[s + k +1] <= vl) pl = llist[s++];
    vl = min(vr, max(vl, llist[s + k]));
    ll ret = 0;
    while (vl < vr&&pl < pr) {
        ll top = min(pr, llist[s]), tov = min(vr, llist[s + k + 1]);
        ret += (top - pl)*(tov - vl);
        pl = top;   vl = tov;
        s++;
    }
    return ret;
}

int main() {
    llist.push_back(4);
    rep(i, 3000)   llist.push_back(getNextLNumber(*llist.rbegin()));
    ll pl, pr, vl, vr;  cin >> pl >> pr >> vl >> vr >> k; k--;
    ll ret = solve(pl, pr, vl, vr) + solve(vl, vr, pl, pr);
    if (k == 0 && max(vl, pl) <= min(vr, pr)) ret -= upper_bound(all(llist), min(vr, pr)) - lower_bound(all(llist), max(vl, pl));
    printf("%.15Lf\n", (ld)ret / (ld)((pr - pl + 1)*(vr - vl + 1)));
    return 0;
}

感想

アルゴリズムは分かりましたが、実装できないということが多い(昨夜のARCでもそうでした)ので、これを克服するために問題をどんどん解かなきゃですね…