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

ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

SRM 700 Div1 Easy FindingFriend

解法

leader[i]がfriendPlaceよりも大きい場合、部屋i以降はleader[i]以上のランクの人だけで調整しなければならないのでleader[i]がfriendPlaceよりも小さいiのみ考えれば良い。

各部屋に収まる人数はroomSizeでそのうちleaderは決まっているので残りのroomSize-1人を埋めればよい。

leaderをソートしておきleaderのランクの小さい順にみる。
もしleader[i]-1 = roomSize*iだった場合、部屋0~i-1に入る人(roomSize*i人)は確定するのでfriendPlaceが入る余地はないので求めるパターンは0~i-1では0になり、部屋iから数え直す。

leader[i]のいる部屋iに対し、ランクがleader[i+1]-1の人までは部屋0~iのどこかに入らなくてはならない。
もし部屋iにleader[i]からleader[i+1]-1のランクの人を埋めてもランクleader[i]~leader[i+1]-1の人が余ったら以前の余っている部分を埋めて、それでも部屋0~iに余裕があるならその余裕の部分にfriendPlaceランクの人を入れることができるので余裕の部分が部屋iにできるようにすれば部屋iにfriendPlaceをいれることができる。

ソースコード

class FindingFriend{
public:
    int find(int roomSize, vector<int> leaders, int friendPlace) {
        int roomCount=leaders.size();
        if(roomCount==1 or roomSize==1) return 1;
        rep(i,roomCount) if(leaders[i]==friendPlace) return 1;
        sort(ALL(leaders));

        int ret=0;
        int rem=0;
        rep(i,roomCount){
            if(leaders[i]>friendPlace) break;
            if(rem==0) ret=0;
            if(i==roomCount-1){
                ret++;
                break;
            }
            assert(leaders[i]<=roomSize*i+1);
            int rs=roomSize-1;
            int diff=leaders[i+1]-leaders[i]-1;
            rem += rs-diff;
            ret++;
        }
        return ret;
    }
};

感想

自分で解けなくて他の人のコードを見て理解した。なんか気がつけば当然の問題だけど全く気が付けない。。。friendPlaceの移動によりそれ以降の部分にも影響が出てしまうような気がしてしまうので難しかった。次に似た問題を見ても解けない気がする。。。