WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM700 Div1 Easy "FindingFriend"

解法

roomSize = 3
leaders  = {1, 4, 6, 10}

■所在不明者2, 3はどの部屋??
leaderが1の部屋に入っているだろう。
答え = 1

■所在不明者5はどの部屋??
leaderが1, 4のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4の部屋に入っているだろう
答え = 1

■所在不明者7, 8, 9はどの部屋??
leaderが1, 4, 6のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4, 6の部屋に入っているだろう
答え = 2

■所在不明者11, 12はどの部屋??
leaderが1, 4, 6, 10のどれかの部屋に入っているだろう
しかし、leaderが1, 4, 6の部屋は2, 3, 5, 7, 8, 9が入っているだろうから人数パンパンである。
↓
leaderが10の部屋に入っているだろう
答え = 1

ソースコード

class FindingFriend {
    public:
    int find(int roomSize, vector<int> leaders, int friendPlace) {
        int roomCount = leaders.size();

        // リーダーじゃないのか?
        for (int i = 0; i < roomCount; i++) {
            if (leaders[i] == friendPlace) return 1;
        }

        // 順位が高い順にリーダーを並べ替える
        sort(leaders.begin(), leaders.end());

        int emptyCount = 0; // 定員が空いている部屋の数
        int rem = 0;        // 定員の空き
        for (int i = 0; i < roomCount - 1; i++) {
            emptyCount++;
            rem += roomSize;
            if (friendPlace < leaders[i + 1]) return emptyCount;
            rem -= leaders[i + 1] - leaders[i];
            // 部屋がパンパンか?
            if (rem == 0) emptyCount = 0;
        }
        return emptyCount + 1;
    }
};