AtCoder Regular Contest 045 C - エックスオア多橋君

競技プログラミング

問題

　N頂点の木が与えられる。各辺に非負整数のコストがついているとき、頂点aとbを結ぶ単純パスにおいて通る辺のコストを全てxor取っていったものがある整数Xになるような(a, b)の組み合わせが何通りあるか求めよ。

解法

　ある頂点xを根と決めたとき、 a \to bという単純パスとa \to x \to bというパスでは通る辺のコストのxorを取っていった値は等しくなる。なぜなら a \to bという単純パスがもともと頂点xを含むなら自明であるし、含まないときはxから見てa,bの近い方へは往復することになるが、xorなので打ち消すことになるからである。

　よって結局頂点x:から見たxorの値に関して、その値となるパスが何個存在するかを数えていけばいい。そして現在のパスに関してxorの値がvならばX xor vとなるパスの個数を答えに加算していけばO(N\log{N})でこの問題が解ける。

反省

　1時間10分(2WA)でAC。今見ている頂点から先で得られるxor値の個数を数えて伝播させる方法で解けると思って提出したがこれはO(N^2)かかるものでありTLEだった。結局1時間過ぎてしまい、違う解法が思い浮かぶ気がしなかったので解説スライドを見たが、発想としては近そうで遠いものだった。xorの性質を上手く使えていないのでもっとそこに注意を向けるべきだった。

　別解として書いてある「データ構造をマージする一般的なテク」とやらを調べて、なんか使えそうな気がしたのでTLE解の方をいろいろいじってやってみたが答えが合わず断念。しかしこれは知っておく価値が大きそうなテクニックだ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, X;
struct Edge {
    ll to, cost;
};
vector<vector<Edge>> edges;
ll ans = 0;
map<ll, ll> mp;

void dfs(ll curr, ll pre, ll value) {
    ans += mp[value ^ X];
    mp[value]++;
    for (Edge e : edges[curr]) {
        if (e.to == pre) {
            continue;
        }

        dfs(e.to, curr, value ^ e.cost);
    }
}

int main() {
    cin >> N >> X;
    edges.resize(N + 1);
    for (ll i = 0; i < N - 1; i++) {
        ll x, y, c;
        cin >> x >> y >> c;
        edges[x].push_back({ y, c });
        edges[y].push_back({ x, c });
    }

    dfs(1, -1, 0);
    cout << ans << endl;
}

AtCoder Regular Contest 044 C - ビーム

競技プログラミング

問題

　H\times W(H, W\le 10^5)のグリッドにビームが飛んでくる。ビームは時刻tに縦方向あるいは横方向についてあるマスを通るように飛ぶ。高橋君は任意のマスからスタートして上下左右のマスについて単位時間に任意の回数移動できる。全てのビームについての情報がわかっているとき、全てのビームを避ける最小の移動回数を求めよ。

解法

　X軸方向とY軸方向はそれぞれ独立に考えて良い。各軸について、それぞれ時刻iに座標jにいるときの最小移動回数を求めればよいが、これは愚直にDPで求めるとO(T(H + W))かかってしまう。

　各時刻でビームが飛んでくる状況を考えると、そのマスから移動することにより左右のマスに配るようなDPをすればよいことがわかる。隣接マスにもビームが飛んできている可能性があるため、まず各時刻におけるビームが来る座標をソートしておいて、小さい方から見ていき大きい方へ避ける移動、大きい方から見ていき小さい方へ避ける移動をそれぞれ遷移させていく必要がある。これによって各時刻について全ての座標を見る必要がなくなり、飛んでくるビームの本数にのみ依存するようになるので計算量はO(W+H+T)でこの問題が解ける。

反省

　1時間54分(4WA)でAC。1時間考えてもさっぱり歯が立たない感じだったので解説スライドを見た。各軸は独立に考えて良いという発想は、それぞれ行と列を考えてminを取れば全ての座標について求まるのか？ くらいには思っていたが、完全に独立に考えて良いというところまでは至っていなかった。

　解説を読んでからもDPの遷移を書くのが結構大変で、WAをたくさん出してしまった。自分の実装だとソートをする(setを使う)要素があるので計算量はO(W+H+T + Q\log{Q})になっているのかな？ 制約が一段緩くてもこの問題を解けたかどうか……。しかし座標を一つ一つ考えることすらできない制約なわけだから、独立になっていそうと思うのは当たり前なんだろうなぁ。そしてそれを確認するのも上手くできるようにならなくては。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll W, H, Q;
    cin >> W >> H >> Q;

    constexpr ll T_MAX = (ll)1e5 + 1;
    //beams[i][j] := 時刻iに方向jのビームが来る座標
    vector<vector<set<ll>>> beams(T_MAX, vector<set<ll>>(2));
    for (ll i = 0; i < Q; i++) {
        ll T, D, X;
        cin >> T >> D >> X;
        beams[T][D].insert(X);
    }

    constexpr ll INF = INT_MAX;

    ll ans = 0;

    for (ll d = 0; d < 2; d++) {
        //縦方向,横方向それぞれについて考える
        const ll MAX = (d == 0 ? W : H);

        //dp[j] := (時刻iに)座標jにいるときの移動距離の最小値
        vector<ll> dp(MAX + 2, 0);

        //番兵
        dp[0] = dp[MAX + 1] = INF;

        for (ll i = 0; i < T_MAX; i++) {
            //順方向に避ける
            for (auto itr = beams[i][d].begin(); itr != beams[i][d].end(); itr++) {
                dp[*itr + 1] = min(dp[*itr + 1], dp[*itr] + 1);
            }
            //逆向きに避ける
            for (auto itr = beams[i][d].rbegin(); itr != beams[i][d].rend(); itr++) {
                dp[*itr - 1] = min(dp[*itr - 1], dp[*itr] + 1);
            }
            for (ll a : beams[i][d]) {
                dp[a] = INF;
            }
        }

        ans += *min_element(dp.begin() + 1, dp.end() - 1);
    }

    cout << (ans >= INF ? -1 : ans) << endl;
}

AtCoder Regular Contest 043 C - 転倒距離

競技プログラミング

問題

　2つの順列について順序が入れ替わっている数字の組の個数を転倒距離と呼ぶこととする。サイズN(\le 10^5)の順列A, Bが与えられたとき、AともBとも転倒距離が等しい順列があるか判定し、ある場合には1つ挙げよ。

解法

　まず適当な数字の置き換えをしてAが1, 2, \dots, Nという配列になるようにする。これによりAとBがA'( = 1, 2, \dots, N)とB'になったとすると、AとBの転倒距離はB'の転倒数に等しくなる。ある順列の転倒数はマージソートのようなやり方でO(Nlog{N})で求めることができる。( tmaehara氏のスライドなどを参照のこと)

　B'の転倒数が奇数であるとき、AともBとも転倒距離が等しい順列は存在しない。(証明は解説スライドを参照のこと)

　B'の転倒数が偶数であるとき、バブルソートをシミュレーションすればちょうど転倒距離が等しいものを求めることができるが、愚直に行うとO(N^2)かかるため、セグメント木などを使ってO(N\log{N})でシミュレーションできるように高速化することでこの問題が解ける。

反省

　1時間52分(4WA)でAC。転倒数に帰着させて奇数の場合は構築不可というところまでは(感覚的に)わかったが、まず転倒数を高速に求める方法がわからなかったので30分ほど過ぎたあたりで諦めて検索をしてO(N\log{N})で求められることを知った。なんとかそれを30分ほどかけて実装したが、偶数のときに実際に構築する方法がわからず結局解説スライドを見た。

　転倒数はバブルソートと深い関係があるというのはちょっとだけ知っていたが、シミュレーションすればいいという発想に至っていなかった。さらにそれをセグメント木などを使って高速化するということで、コンテストで出されたらなかなか解けそうにない。

　Aを変換したり、最後に答えを変換しなおしたりというのを勘でやってなんか通ってしまったのであまり問題(解法)をしっかり理解できたという気がしない。

　とりあえずセグメント木に加えて転倒数も自作ライブラリに突っ込んでおいた。あまりマージソートを理解していないままなので良いこととは思えないが……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class InversionCount {
public:
    InversionCount(vector<ll> target) : target_(target) {}
    ll count(ll left = 0, ll right = -1) {
        if (right < 0) {
            //rはtarget_.size()で初期化
            right = target_.size();
        }
        if (right <= left + 1) {
            return 0;
        }
        ll mid = (left + right) / 2;
        ll result = 0;
        //左半分を数える
        result += count(left, mid);

        //右半分を数える
        result += count(mid, right);

        //左右またぐ数を数える
        result += merge(left, mid, right);

        return result;
    }
private:
    ll merge(ll left, ll mid, ll right) {
        vector<ll> l, r;
        for (ll i = left; i < mid; i++) {
            l.push_back(target_[i]);
        }
        for (ll i = mid; i < right; i++) {
            r.push_back(target_[i]);
        }
        //番兵
        l.push_back(LLONG_MAX);
        r.push_back(LLONG_MAX);

        ll left_index = 0;
        ll right_index = 0;
        ll result = 0;
        for (ll i = left; i < right; i++) {
            if (l[left_index] <= r[right_index]) {
                target_[i] = l[left_index];
                left_index++;
            } else {
                target_[i] = r[right_index];
                right_index++;
                result += ((mid - left) - left_index);
            }
        }
        return result;
    }

    vector<ll> target_;
};

//1点更新,区間和
class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = v;
        for (ll i = (x + n_ - 2) / 2; i > 0; i = (i - 1) / 2) {
            nodes_[i] = nodes_[2 * i + 1] + nodes_[2 * i + 2];
        }
    }

    ll getSum(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return 0;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll left  = getSum(a, b, 2 * k + 1, l, (l + r) / 2);
        ll right = getSum(a, b, 2 * k + 2, (l + r) / 2, r);
        return left + right;
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    vector<ll> pos(N + 1, 0), B2(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
        pos[A[i]] = i + 1;
    }
    for (ll i = 0; i < N; i++) {
        cin >> B[i];
        B2[i] = pos[B[i]];
    }

    InversionCount ic(B2);
    ll inversion_count = ic.count();

    if (inversion_count % 2 == 1) {
        cout << -1 << endl;
    } else {
        inversion_count /= 2;
        SegmentTree st(N + 1, 0);
        vector<ll> ans;
        for (ll i = 0; i < N; i++) {
            ll sum = st.getSum(B2[i] + 1, N + 1);
            st.update(B2[i], 1);

            //移動量
            ll v = min(sum, inversion_count);

            inversion_count -= v;
            ans.insert(ans.end() - v, B2[i]);
        }
        assert(inversion_count == 0);

        for (ll i = 0; i < N; i++) {
            cout << A[ans[i] - 1] << " \n"[i == N - 1];
        }
    }
}

AtCoder Regular Contest 042 C - おやつ

競技プログラミング

問題

　N種類のおやつについてそれぞれ値段と満足度が設定されており、各種類について多くとも1つ持っていくことができる。どの1つのおやつについてもそのおやつがなければ合計でP円以下になるとき持っていくことが可能である場合に、満足度の最大値を求めよ。

解法

　あるおやつ集合の中で一番値段が小さいもの一つを除いた値段の和sを考えると、他のおやつを除いた場合は必ずs以下になるため、sがP以下であるかどうかを考えればよい。

　(あるおやつを除いたとして)残りのおやつから値段がP以下となるように満足度を最大化することはDPでできる。

　値段を降順にソートしてからDPテーブルを作れば、答えを求めるときに各おやつに対して同じテーブルを使うことができる。よってO(N\log{N} + NP)でこの問題が解ける。

反省

　1時間28分(6WA)でAC。最初考えた方針がかなり想定解に近かったが、O(N\log{N} + NP\times (\max{a}))というような最悪で100倍遅いものを考えていたし、実装も間違っていてWA。その後もmapを使って高速化できるんじゃないかとか意味不明なことを考え出してTLEやWAなどを次々出していく。結局1時間経ってしまったので解説スライドを見た。1ページ。超短い。見た後も実装にちょっと苦労してしまったがなんとかAC。終わってみれば簡単な問題で、なんでこれが解けないのか。もっと考察で簡単に書けるコードを思い浮かべれれるようにならなければ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, P;
    cin >> N >> P;

    struct Snack {
        ll a, b;
    };

    vector<Snack> snacks(N);
    for (ll i = 0; i < N; i++) {
        cin >> snacks[i].a >> snacks[i].b;
    }

    sort(snacks.begin(), snacks.end(), [&](Snack& lhs, Snack& rhs){
        return lhs.a != rhs.a ? lhs.a > rhs.a : lhs.b > rhs.b;
    });

    //dp[i][j] := i番目まで見てj円以下の場合の最大幸福度
    vector<vector<ll>> dp(N, vector<ll>(P + 1, 0));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= P; j++) {
            //i番目を持っていかない
            dp[i][j] = max(dp[i][j], (i == 0 ? 0 : dp[i - 1][j]));

            //i番目を持っていく
            ll p = j + snacks[i].a;
            if (p > P) {
                continue;
            }
            dp[i][p] = max(dp[i][p], (i == 0 ? 0 : dp[i - 1][j]) + snacks[i].b);
        }
    }

    ll ans = (snacks[0].a <= P ? snacks[0].b : 0);
    for (ll i = 1; i < N; i++) {
        ans = max(ans, dp[i - 1][P] + snacks[i].b);
    }

    cout << ans << endl;
}

AtCoder Regular Contest 041 C - ウサギ跳び

競技プログラミング

問題

　L(\le 10^9)個のマスが横一列に並んでおり、マスの上にはN(\le10^5)匹のウサギが右か左を向いている。ウサギは向いている方向の一つ前のマスに他のウサギがいなければジャンプしてそのマスへ移動できる。ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を求めよ。

解法

　二匹のウサギが向き合っているとき、後ろに連続して同じ向きで待っているウサギがいる数の多い方のみがジャンプするのが最善となる。その数を数えて貪欲に動かせばO(N)でこの問題が解ける。

反省

　19分59秒(0WA)でAC。理屈から言って解けそうなのはすぐわかったが、何に注目して考えると考えやすい/実装しやすいかというのがちょっとわからなかった。結局i番目のウサギが動くべきかどうかというのを全部最初に求めてしまうのがわかりやすいかと思ったが、コードは結構長くなってしまった。解説スライドでは区間に分けて考えるとあり、これはなかなか実践的な思考法なんだろうなと感じた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, L;
    cin >> N >> L;

    struct Usagi {
        ll x, follow_num;
        char d;
        bool move;
    };
    vector<Usagi> usa(N);
    for (ll i = 0; i < N; i++) {
        cin >> usa[i].x >> usa[i].d;
        usa[i].move = true;
    }
    

    //右向きウサギについて数える
    ll num = 0;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //左向きウサギについて数える
    num = 0;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //i番目のウサギが動くかどうかについて考える
    //前にいるウサギがこちらを向いており
    //向こうの方が後ろに続くウサギが多かったらこっちは動かない
    for (ll i = 0; i < N - 1; i++) {
        if (usa[i].d == 'R' && usa[i + 1].d == 'L') {
            if (usa[i].follow_num < usa[i + 1].follow_num) {
                usa[i].move = false;
            } else {
                usa[i + 1].move = false;
            }
            i++;
        }
    }

    ll ans = 0;

    //右向きウサギを限界まで動かす
    //行ける一番右のマス
    ll limit = L;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L' || !usa[i].move) {
            limit = usa[i].x - 1;
        } else {
            ans += limit - usa[i].x;
            usa[i].x = limit;
            limit--;
        }
    }

    //左向きウサギを限界まで動かす
    limit = 1;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R' || !usa[i].move) {
            limit = usa[i].x + 1;
        } else {
            ans += usa[i].x - limit;
            usa[i].x = limit;
            limit++;
        }
    }

    cout << ans << endl;
}

AtCoder Regular Contest 040 C - Z塗り

競技プログラミング

問題

　N\times N(N \le 100)のマス目状になっている床を一色に塗ることを考える。一回の塗る操作で、ある整数r,cに対して「i=rかつj\le c」または「i=r + 1かつj \ge c」を満たすような全てのマス(i, j)を塗ることができる。部分的に塗られている初期状態が与えられるので、全てのマスを塗る最小の操作回数を求めよ。

解法

　各行に対して右側からみてまだ塗られていないマスがあったらそこを(r, c)として塗る貪欲法で計算量はO(n^3)でありこの問題が解ける。

反省

　9分4秒(0WA)でAC。特に難しいところもなく。昨日一昨日に比べてこの難易度の差。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<string> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = N - 1; j >= 0; j--) {
            if (S[i][j] == '.') {
                //(i, j)で一回塗る
                ans++;

                //i段目が塗られる
                for (ll k = 0; k <= j; k++) {
                    S[i][k] = 'o';
                }

                //i + 1段目が塗られる
                if (i != N - 1) {
                    for (ll k = j; k < N; k++) {
                        S[i + 1][k] = 'o';
                    }
                }
            }
        }
    }

    cout << ans << endl;
}

SRM515 Div1 Easy - RotatedClock

問題

　時計の長短針の角度を与えるので時刻として正当なものを出力せよ。

解法

　回して12通り試す。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class RotatedClock {
public:
    string getEarliest(int hourHand, int minuteHand) {
        for (int i = 0; i < 12; i++) {
            int h = hourHand, m = minuteHand;
            while (h < i * 30) {
                h += 30;
                m += 30;
                m %= 360;
            }
            while (h >= (i + 1) * 30) {
                h -= 30;
                m -= 30;
                m += 360;
                m %= 360;
            }

            if ((h % 30) * 360 == m * 30) {
                string ans;
                if (i < 10) {
                    ans += "0";
                }
                ans += to_string(i);
                ans += ":";
                m /= 6;
                if (m < 10) {
                    ans += "0";
                }
                ans += to_string(m);
                return ans;
            }
        }
        return "";
    }
};

SRM514 Div1 Easy - MagicalGirlLevelOneDivOne

解法

　各nに対して、nが偶数なら適当に式をいじると必ず可能であることがわかる。奇数だけのときはx + yが0であるかどうかで判定できる。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class MagicalGirlLevelOneDivOne {
public:
    string isReachable(vector <int> jumpTypes, int x, int y) {
        x = abs(x);
        y = abs(y);
        for (int n : jumpTypes) {
            if (n % 2 == 0) {
                return "YES";
            }
        }
        return ((x + y) % 2 == 0 ? "YES" : "NO");
    }
};

AtCoder Regular Contest 039 C - 幼稚園児高橋君

競技プログラミング

問題

　無限に広がる二次元格子について最初(0, 0)から出発し、以下のような行動を繰り返す。

  • 上下左右のうち好きな方向を決めてその方向に今まで訪問したことのない格子に到達するまで直進し、止まる

　直進した回数とそれぞれの方向を与えるので最終的に止まる格子の座標を求めよ。

解法

　二次元座標は無限に広いため各点について情報を保持することはできない。よって到達する格子K個の周囲についてハッシュマップや平衡二分探索木を用いて、次にある方向へ進んだ時に止まる格子を保持することを考える。必要な分だけ情報を更新していくことで計算量はO(K\log{K})となり、この問題が解ける。

反省

　1時間54分(1WA)でAC。20分くらい考えた時点で、到達済みのマスは行および列に関して必ず連続だと勘違いして、各行や列に対して到達した上下限を持っておけばよいというコードを提出してWA。これはちょっと考えれば間違っていることはすぐわかって、たとえばRUDLLUUとかでy = 1において飛び地が形成される。

　結局その後計一時間になるまで考えてわからなかったので解説スライドを見た。mapを使うという発想が頭から飛んでいたのは完全にダメ。行と列についてそれぞれ情報を持つことにしか意識が行っていなかった。

　しかし解説を見た後も実装がよくわからず苦労した。遅延評価というのが何を指していてどう実装するものかピンと来なくて、結局人の提出を写したような感じになってしまった。mapのKey側にどこまで情報を持たせるかというのが結構本質的で、方向をValue側に持たせてしまうとどうしても使わない部分についての初期化が混ざってしまい上手くいかなかった。

　ハッシュを使った提出も見てみたが、うーん、理解ができない……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

#include<array>

int main() {
    ll K;
    string S;
    cin >> K >> S;

    enum Dir {
        UP, RIGHT, DOWN, LEFT, DIR_NUM
    };
    ll dx[DIR_NUM] = { 0, 1, 0, -1 };
    ll dy[DIR_NUM] = { 1, 0, -1, 0 };

    using Point = pair<ll, ll>;

    //next[{x, y}][i] = (x, y)からiの方向に行くとき次に止まるマス
    map<pair<Point, ll>, Point> next;

    auto update = [&](Point curr) {
        //(x, y)の情報について更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            if (next.find({ curr, i }) == next.end()) {
                next[{curr, i}] = { curr.first + dx[i], curr.second + dy[i] };
            }
        }

        //(x, y)の上下左右について情報を更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            next[{next[{curr, i}], (i + 2) % 4}] = next[{curr, (i + 2) % 4}];
        }
    };

    Point curr(0, 0);

    for (char c : S) {
        update(curr);
        if (c == 'U') {
            curr = next[{curr, UP}];
        } else if (c == 'R') {
            curr = next[{curr, RIGHT}];
        } else if (c == 'D') {
            curr = next[{curr, DOWN}];
        } else if (c == 'L') {
            curr = next[{curr, LEFT}];
        } else {
            assert(false);
        }
    }

    cout << curr.first << " " << curr.second << endl;
}

AtCoder Regular Contest 038 C - 茶碗と豆

競技プログラミング

問題

　N個の茶碗が横一列に並んでいる。各茶碗iには整数C_iが書かれており、中にはA_i個の豆が入っている。これらを用いて次のゲームを行う。

  • プレイヤーは自分のターンに茶碗0以外の茶碗に入っている豆を1つ選んで取り出す。
  • 茶碗iから豆を取り出したとき、茶碗i - C_i,茶碗i - C_i + 1, \dots, 茶碗i - 1のいずれかの茶碗に豆を入れなければならない。
  • 交互にターンを繰り返し、自分のターンに選べる豆がなくなったプレイヤーの負けとなる。

　両プレイヤーが最適な戦略をとったとき、先手と後手のどちらが勝つか判定せよ。

解法

　Grundy数を考える。i個目の茶碗に入っている豆を遷移させられるのはi - C_iからi - 1までなので、この区間のGrundy数に含まれない最小の整数がi番目についてのGrundy数となる。

　これを単純に数えるとO(N^2)以上かかるが、セグメント木を利用して高速化することでO(N(\log{N})^2)で求めることができる。

　具体的な方法としては、まずi番目のGrundy数を求める状況を考えることとする。セグメント木には各Grundy数に対して、そのGrundy数がi - 1番目までで最後にどこで出てきたかを記録しておく。

　このセグメント木を利用して、「i番目のGrundy数としてxが可能かどうか」という二分探索をしていく。セグメント木に[0, x]の範囲でクエリを投げ、x以下のGrundy数として最小の出現位置を得る。これがi - C_iより大きかったらつまりx以下がi - C_iからi - 1の範囲に全て詰まっているということなのでxはi番目のGrundy数にはなれない。逆に小さかったらx以下のどれかがi番目のGrundy数として選べる。この判定をもとに二分探索を行うことでこの問題が解ける。

反省

　2時間41分(2WA)でAC。眠気と格闘しながら1時間20分ほど考えたが、そもそもGrundy数という発想がなく全然ダメな考察をしていた。

　そこから解説スライドを見てまず100点分の部分点解法を得る。Grundy数、言われるとなるほどなんだがこれを思いつける気はしない。

　さらに満点を得るためにはセグメント木を実装しなければならず、また他人の提出をいろいろ見てみたところ二分探索部分がセグメント木の中に埋め込まれている？ ような感じでよくわからなかった。多少効率は悪いのかもしれないが、セグメント木を用いた値の取得でO(\log{N})、それを使った二分探索でさらにO(\log{N})かかる実装とした。これでも十分間に合う(222msec)。

　セグメント木として確保する範囲が大きすぎて一度REを出してしまった。理解が浅いのでこういうミスが出るという面もあるのだと思う。

　Grundy数とこのセグメント木による高速化は相性が良さそうに思えるが、典型と言えるんだろうか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = v;
        for (ll i = (x + n_ - 2) / 2; i > 0; i = (i - 1) / 2) {
            nodes_[i] = min(nodes_[2 * i + 1], nodes_[2 * i + 2]);
        }
    }

    ll getMin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return INT_MAX;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll left  = getMin(a, b, 2 * k + 1, l, (l + r) / 2);
        ll right = getMin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(left, right);
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> C(N), A(N);
    C[0] = A[0] = 0;
    ll sum = 0;
    for (ll i = 1; i < N; i++) {
        cin >> C[i] >> A[i];
        sum += A[i];
    }

    constexpr ll MAX = 1e5 + 1;
    SegmentTree st(MAX, -1);

    vector<ll> grundy(N);
    grundy[0] = 0;
    st.update(0, 0);
    for (ll i = 1; i < N; i++) {
        //取り得るgrundy数について2分探索をする
        ll ng = -1, ok = MAX;
        while (ng + 1 != ok) {
            ll mid = (ng + ok) / 2;

            //0からmidまでのgrundy数について,今まで出てきた位置の最小値を求める
            ll min_index = st.getMin(0, mid + 1);
            (min_index >= i - C[i] ? ng = mid : ok = mid);
        }
        grundy[i] = ok;
        st.update(grundy[i], i);
    }

    ll xor_value = 0;
    for (ll i = 1; i < N; i++) {
        if (A[i] % 2) {
            xor_value ^= grundy[i];
        }
    }

    cout << (xor_value == 0 ? "Second" : "First") << endl;
}