Codeforces #281 (Div.2 only)

Tatsuya Yatagawa

2014-12-04

昨日のCodeforcesはめずらしく良くできた気がするのでざっくり解説しておきます。

A. Vasya and Football

問題

サッカーのようなゲームが行われていて、90分間の間にホーム側の選手、アウェイ側の選手でどの番号の選手がイエローカード、レッドカードをもらったのかが与えられる。なお、イエローカードを2枚もらうと自動的にレッドカードとなる。このとき、各選手が初めてレッドカードをもらった時間を出力せよ。

解法

どうやら、問題の設定的に、イエローカード3枚とかレッドカード2枚とかをもらうことがあるようなので、それに注意して普通にシミュレーションする。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

struct Card {
    int m;
    int t;
    int num;
    int color;
    bool operator<(const Card& c) const {
        return m < c.m; 
    }
};

string team[2];
int n;
vector<Card> cards;

void coding() {
    int mm, nn;
    char tt[2], cc[2];

    cin >> team[0] >> team[1];
    scanf("%d", &n);
    cards.clear();
    REP(i,n) {
        scanf("%d %s %d %s", &mm, tt, &nn, cc);
        int t = tt[0] == 'h' ? 0 : 1;
        int c = cc[0] == 'y' ? 1 : 2;
        Card card = { mm, t, nn, c };
        cards.push_back(card);
    }

    sort(ALL(cards));
    map<int,int> amap;
    map<int,int> hmap;
    REP(i,n) {
        map<int,int>& mp = cards[i].t == 0  ? amap : hmap;
        mp[cards[i].num] += cards[i].color;
        if(mp[cards[i].num] >= 2) {
            printf("%s %d %d\n", team[cards[i].t].c_str(), cards[i].num, cards[i].m);
            mp[cards[i].num] = -1000000;
        }
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("a.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

B. Vasya and Wrestling

問題

2人の選手がレスリングの試合を行っていて、互いに技を繰り出している。現在2人の繰り出した技のリストが時系列順にならんでいるので、どちらの選手が勝ったのかを判断してほしい。2人の点数が異なる場合には、点数が多い方がかつ。もし同じときには、技のならびが辞書順に大きい方が勝つ。もしそれも同じなら最後に技を繰り出した方が勝ちとする。

解法

Aよりめんどくさくない気がする。普通にシミュレーションをすればいい。ただし、合計がintの範囲に収まらないことがあるので、それだけ注意する。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

int n;
vector<lint> a;
vector<lint> b;

void coding() {
    lint sa, sb, w, last;
    while(scanf("%d", &n) != EOF) {
        sa = 0;
        sb = 0;
        a.clear();
        b.clear();
        REP(i,n) {
            scanf("%I64d", &w);
            last = w;
            if(w > 0) {
                sa += w;
                a.push_back(w);
            } else {
                w = abs(w);
                sb += w;
                b.push_back(w);
            }
        }

        if(sa != sb) {
            printf("%s\n", sa > sb ? "first" : "second");
        } else if(a != b) {
            printf("%s\n", a > b ? "first" : "second"); 
        } else {
            printf("%s\n", last > 0 ? "first" : "second");
        }
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("b.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

C. Vasya and Basketball

問題

現在2つのチームがバスケットボールのようなゲームを行っていて、チームAとチームBがゴールを決めたときに、何メートル離れたところからシュートを打ったかが与えられている。このときシュートがある距離d以下であれば2点が、それより大きければ3点が与えられる。dを適当に調節して、AとBの点数差がAにとって最も有利になるようにせよ。

解法

問題の大きさはシュートの本数が$ 2 \times 10^9$となっている。単純に考えると全ての距離にたいして、点数差がどうなるのかを調べれば良いのだが、それだと時間が足りない。

ここでポイントは各チームがシュートを打った距離だけが答えになりうるということで、それを調べるだけなら$2 \times 10^5$個を調べれば良いだけなので、時間が足りる。

あとは各チームについてシュートを距離順にソートしておいて、何本が2点シュートで何本が3点シュートなのかを二分探索で求められるようにしておく。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

int n, m;
lint as[200011];
lint bs[200011];

void solve() {
    sort(as, as+n);
    sort(bs, bs+m);
    vector<lint> vs;
    vs.push_back(0);
    vs.push_back(1ll<<60);
    REP(i,n) vs.push_back(as[i]);
    REP(i,m) vs.push_back(bs[i]);
    sort(ALL(vs));
    vs.erase(unique(ALL(vs)), vs.end());

    int ma = -1<<30;
    int mpa = -1<<30;
    int id = 0;
    REP(i,vs.size()) {
        int ta = upper_bound(as, as+n, vs[i]) - as;
        int tb = upper_bound(bs, bs+m, vs[i]) - bs;
        int pa = 2 * ta + 3 * (n - ta);
        int pb = 2 * tb + 3 * (m - tb);
        if(ma < pa - pb) {
            ma = pa - pb;
            mpa = pa;
            id = i;
        } else if(ma == pa - pb && mpa < pa) {
            mpa = pa;
            id = i;
        }
    }

    int ta = upper_bound(as, as+n, vs[id]) - as;
    int tb = upper_bound(bs, bs+m, vs[id]) - bs;
    int pa = 2 * ta + 3 * (n - ta);
    int pb = 2 * tb + 3 * (m - tb);
    printf("%d:%d\n", pa, pb);
}

void coding() {
    while(scanf("%d", &n) != EOF) {
        REP(i,n) scanf("%I64d", as+i);
        scanf("%d", &m);
        REP(i,m) scanf("%I64d", bs+i);
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("c.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

D. Vasya and Chess

問題

2人が横nマス縦nマスの盤面でクイーンを動かすゲームをしている。初期状態ではプレイヤーAのクイーンが(1, 1)に、プレイヤーBのクイーンが(1, n)に置かれており、それ以外のマスには緑色のチップが置かれている。各プレイヤーは自分のターンの時にクイーンの動ける範囲でチップが置いてある場所か、相手のクイーンが置いてある場所に移動できる。もしチップと相手のクイーンが置いてある位置に移動できなくなればそのプレイヤーの負けとなる。また、相手にクイーンを取られても負けとなる。このとき盤面の大きさnが与えられるので、互いに最適な手を打った時にどちらが勝つのかを判定せよ。またプレイヤーAが勝つときには、その第1手を出力せよ。

解法

なぜかここからスポーツの問題ではなくなる。

それはともかく、この問題はnの最大値が$2 \times 10^9$なので、grundy数とかを計算してがんばるのは難しそうなことに気づく。

となれば何か法則があるはず。結論からいうと、その法則とはnが偶数のときはプレイヤーAが右に1マス動けば勝利できる。その後の手は、プレイヤーBが打った手と線対称になるように打っていけば必ず勝利できる。

逆に、盤面の大きさnが奇数の時は、プレイヤーBがプレイヤーAの打った手と線対称になる手を打ち続けることで必ず勝利できる。

これにさえ気づければコードはせいぜい数行程度。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

void coding() {
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n % 2 == 0) {
            printf("white\n");
            printf("1 2\n");
        } else {
            printf("black\n");
        }
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("d.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

E. Vasya and Polynomial

問題

係数が正のn次多項式P(x)(nは任意)が与えられている。このときP(t) = a, P(P(t)) = bであることが分かっている。このような等式を満たす多項式の個数をすべて数え上げて10^9+7で割った余りを答えよ。

解法

まず一般的な観察としてP(t) = aなので、2つ目の式をP(a) = bと書き直すことができます。この気づきが以外に重要(?)だと思います。

では特殊なケースから考えます。t=a=b=1の時にはx^nが任意のnについてP(x)の条件を満たすので、答えはinfになります。

次に、t=aであるときは、a=bならばP(x)=aと、P(x)=xの1通りが答えになります。もしa!=bであれば、それはあり得ないので答えは0です。

次に、t!=aであるときは、a=bならばP(x)=aだけが答えになります。

で、上の場合以外のものが一般ケースとしてがんばって計算しないといけないものになります。

ポイントとして多項式の係数が全て正であるのでP(x)はx>0の範囲では単調増加です。なので、t, a, bも全て正であることからt < a < bが満たされなければいけません。そうでなければ答えは0です。

次にP(x) = a_0 + Q(x)xという風にn-1次式Q(x)をつかって書き直せることを利用します。

これを使うと

a = a_0 + Q(t)t

b = a_0 + Q(a)a

が同時に成り立たなければならず、またQ(t)とQ(a)がどちらも整数であることからa_0としてありうるものは

(a – a_0) % t = 0

(b – a_0) % a = 0

を満たさなければならないことになります。

これを満たすものは上の2式を満たす最小のa_0にtとaの最小公倍数を足していったものになりますので、それを全て列挙します。

そうしたらa_0が決まるので、同時にQ(t)およびQ(a)がいくつになるのかも決まります。

あとはQ(x)をP(x)のようにみなして上記の計算を再帰的に繰り返していくだけです。

で、最後にaもbも0となるようなケースが出てきたら、その時は1を返してあげます。


#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<lint,lint> pll;

const lint mod = 1000000007;
lint t, a, b;

lint gcd(lint x, lint y) {
    if(x > y) swap(x, y);
    while(x != 0) {
        lint t = y % x;
        y = x;
        x = t;
    }
    return y;
}

lint lcm(lint x, lint y) {
    return x / gcd(x, y) * y;
}

lint dfs(lint d1, lint d2, lint g, lint a, lint b) {
    // printf("%I64d %I64d %I64d %I64d %I64d n", d1, d2, g, a, b);
    if(a == 0 && b == 0) return 1;
    else if(a == 0 || b == 0) return 0;

    if(d1 != 1 && a % d1 != b % d2) return 0;
    lint base = b % d2;
    lint ret = 0;
    while(base <= a && base <= b) {
        lint na = (a - base) / d1;
        lint nb = (b - base) / d2;
        ret = (ret + dfs(d1, d2, g, na, nb)) % mod;
        base += g;
    }
    return ret;
}

void solve() {
    printf("%I64d\n", dfs(t, a, lcm(t, a), a, b));
}

void coding() {
    while(scanf("%I64d %I64d %I64d", &t, &a, &b) != EOF) {
        if(t == 1 && a == 1 && b == 1) printf("infn");
        else if(t == a) {
            printf("%d\n", a == b ? 2 : 0);
        }
        else if(a == b) {
            printf("1\n");
        }
        else if(t > a || a > b) printf("0\n");
        else {
            solve();
        }
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("e.in", "r", stdin);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cout << "This is local test" << endl;
    cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}

まとめ

今回は初めて5問ともPretestを通すことができました。結果的に言うとCを定数の間違えで、Eを条件判定のミスで落としたので3問しか当たりませんでしたが、立てた方針は間違っていなかったので、今まででは一番良い結果だったと思います。

特にEの問題はコンテスト直後に僕がSubmitしなおしたときには、まだ11人しかできてなかったので、結構難しかったのかな？と思います。はい、ただの自慢です。

それでは、今回の解説を終わります。最後までお読みいただきましてありがとうございました。