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

AOJ2409 Power

解法
二重ループの全探索。
必ず左端から詰めるという制約の元、できるだけ右端まで到達できる権力を持つものを選ぶ。右端がNまで辿り着かない場合は"Impossible"と出力する。

反省
D問題だし特殊な貪欲のようなものが有るのではないかという余計な考え方から頭が働いてしまい、30分くらい要してしまった。オーダーを考えて二重ループは余裕なので、普通に全探索だろうと考え出せばもっとずっと早く解けたのかもしれない。作ったバグは"Impossible"判定がされていないバグと、制限の中の可能な右端の最大の更新条件が甘かったバグ。問題の難易度的にサンプルが通ればWAはなかった。

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int main() {
  int N, M; cin >> N >> M;
  vector<PII> vec(M);
  for(int i=0; i<M; i++) {
    int a, b; cin >> a >> b;
    vec[i] = make_pair(a, b);
  }
   
  int lim_a = 1;
  int ans = 0;
  int const size = vec.size();
  int ok = 0;
  for(int i=0; i<size; i++) {
    int mx = 0;
    for(int j=0; j<size; j++) {
      if(vec[j].first <= lim_a) {
        if(mx <= vec[j].second && lim_a <= vec[j].second) {
          mx = vec[j].second;
        }
      }
    }
    ans ++;
    if(mx>=N) {
      ok = 1;
      break;
    }
    lim_a = mx+1;
  }
   
  if(ok) { cout << ans << endl; }
  else   { cout << "Impossible" << endl; }
   
  return 0;
}