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 の変化量以下である」に含まれるものである。
サンプルに合わせてコードを書いてしまうと、こういうことが起こる。。。 もうやらないと思っていたのだが...
#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;
}