読者です 読者をやめる 読者になる 読者になる

Codeforces Good Bye 2016 C. New Year and Rating

問題

codeforces.com

考察

折れ線グラフを書いてみるとわかりやすいです。
なるべくレートを高くしたいので、div2の一番高い状態でのレートが1899になると良さそうです。
その状態で、div1では1900を下回らないようにする必要があります。

これを実現するためには、初期値を決定してゆく(狭めてゆく)方法が簡単です。

Impossible、Infinityなケースとして、

  • div1のレートがdiv2のレートを下回っている
  • div1の変動しかない

という2種類があるので、初期値は[-INF, +INF]とし、以下のような更新を行います。
(最初と比較しx変わった後に)

  • div1である: 左端をmax(左端, 1900 - x)
  • div2である: 右端をmin(右端, 1899 - x)

このような更新をし、「左端 <= 右端」であり、かつ「右端 != INF」であれば題意を満たします。

最後に右端に変動を加え、最終的なレートを出力すればACです。

サンプル

最初のサンプルで見てみると、以下のように範囲が狭まります。

[-INF, INF]
[1900, INF] ... acc:0, 最初はdiv1である
[1900, 1906] ... acc:-7, div2になった
[1900, 1901] ... acc:-2, div2
[1900, 1901] ... acc:+6, 最終的なdivはわからないので放置

1901が右端なので、これに+6をし、1907が答えです。

コード

int main() {
    int n;
    cin >> n;

    int acc = 0;
    int mi = -INF, mx = INF;
    rep(i, n) {
        int c, d;
        cin >> c >> d;

        if(d == 1)
            chmax(mi, 1900 - acc);
        else
            chmin(mx, 1899 - acc);

        acc += c;
    }

    if(mi > mx)
        cout << "Impossible" << endl;
    else if(mx == INF)
        cout << "Infinity" << endl;
    else
        cout << mx + acc << endl;
    
    return 0;
}

感想

最終的にかなりシンプルになる、考察重視な問題でした。
パッと浮かぶようになりたいです。