Skip to content

Instantly share code, notes, and snippets.

@mumumu

mumumu/1334a_editorial.md

Last active Apr 12, 2020
Embed
What would you like to do?

https://codeforces.com/contest/1334/problem/A

解説

ゲームの2つの stats - number of play (np) と number of clear (nc) は、以下の条件を すべて 満たさなければならない

  • A) np は単調増加である
  • B) nc は単調増加である
  • C) nc の変化量 は np の変化量以下である

A) と B) は容易にわかるだろう。問題は C) である。

なぜ C) が言えるのか。それは問題文に以下のようにあるからである。

**Note that both of the statistics update at the same time** 
(so if the player finishes the level successfully then the number of plays will increase at the same time as the number of clears).

ある1人のプレイヤーの状態は、1回しか更新されない。つまり1回しか現れないのである。 つまり、以下のような時系列はありえない。あるプレイヤーが、ある時点はクリアできなかったが、別の時点でクリアできた、とはならないのである。

1 0
1 1

上記の状態は、下記でなければならない

1 0
1 0

このことから、プレイヤーが増えれば、クリアの数もその増えた数以下しか増えない。よって、3) が言えるのである。

何を間違ったのか?

自分は C) を勘違いし、あるプレイヤーは別の時点でも状態が更新できる、と思いこんでしまった。そこで、np >= nc が言えれば十分だと思いこんでしまったのだ。nc <= np は、「nc の変化量 は np の変化量以下である」に含まれるものである。

サンプルに合わせてコードを書いてしまうと、こういうことが起こる。。。 もうやらないと思っていたのだが...

AC コード

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int n;
        cin >> n;
        vector<pair<int, int>> arr;
        for (int j = 0; j < n; j++) {
            int p, c;
            cin >> p >> c;
            arr.push_back(make_pair(p, c));
        }

        int pp = 0;
        int pc = 0;
        bool yes(true);
        for (int k = 0; k < n; k++) {
            int p = arr[k].first;
            int c = arr[k].second;
            int subp = p - pp;
            int subc = c - pc;
            if (subp >= 0 && subc >= 0 && subp >= subc) {
            } else {
                yes = false;
                break;
            }
            pp = p;
            pc = c;
        }
        cout << ((yes) ? "YES" : "NO") << endl;
    }
    return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment