提出 #625090

---

ソースコード 拡げる

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

struct Room {
    int a, i;
    Room(): a(0), i(0) {}
    Room(int a_, int i_): a(a_), i(i_) {}
    bool operator<( const Room &r ) const {
        if (a == r.a) return i < r.i;
        return a < r.a;
    }
    bool operator==( const Room &r ) const {
        if (a == r.a) return i == r.i;
        return false;
    }

};

int N;

int solve(vector<Room> rooms) {
    int ans = 1;
    for (int i = 1; i < N - 1; ++i) {
        Room prev = rooms[i - 1];
        Room cur = rooms[i];
        if (prev.i > cur.i) ans++;
    }
    return ans;
}

int main() {
    cin >> N;
    vector<Room> rooms;
    int max_a = 0;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        max_a = max(max_a, a);
        rooms.push_back(Room(a, i));
    }
    
    // start と goal を決める
    Room start_room, end_room;
    vector<pair<Room, Room>> start_end;
    for (int i = 0; i < rooms.size(); ++i) {
        if (rooms[i].a == max_a) {
            start_end.push_back({rooms[i % rooms.size()], rooms[i]});
        }
    }
  
    int ans = INT_MAX / 3;
    for (pair<Room, Room> se : start_end) {
        // 周回数を求める
        vector<Room> tmp = rooms;
        for (int ti = tmp.size() - 1; ti >= 0; --ti) {
            if (tmp[ti] == se.first || tmp[ti] == se.second) tmp.erase(tmp.begin() + ti);
        }
        sort(ALL(tmp));
        int res = solve(tmp); 
        res += (se.first.i > tmp[0].i) ? 1 : 0;
        res += (se.second.i > tmp[tmp.size() - 1].i) ? 1 : 0;
        ans = min(res, ans);
    }
    cout << ans << endl;
	return 0;
}

提出情報

ジャッジ結果