SRM 700 Div1 Easy FindingFriend - ちゃっくのメモ帳

問題

解法

(2017/4/29:解き直したので下にちょっと付け足す.解法を確認するなら下に追記した部分を読んだほうがよい)

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の移動によりそれ以降の部分にも影響が出てしまうような気がしてしまうので難しかった。次に似た問題を見ても解けない気がする。。。

2017/4/29追記

解き直した.ソースコードがシンプルになったのであげ直す.

class FindingFriend{
    public:
        int find(int roomSize,vector<int> leaders,int friendPlace){
            int roomCount = leaders.size();
            sort(all(leaders));
            auto itr = std::find(all(leaders),friendPlace);
            if(itr!=leaders.end()){
                return 1;
            }
            ll ans=0;
            for(int i=0;i<roomCount;i++){
                if(leaders[i]>friendPlace) break;
                if(leaders[i]==i*roomSize+1){
                    ans=0;
                }
                ans++;
            }
            return ans;
        }
};

解法は変わらないが,frindPlaceがleadersに含まれていないときに,
1.leaders[i]がfriendPlaceよりも大きければfrindPlaceをその部屋に追加するとleaders[i]よりfrindPlaceが小さくなり矛盾が生じるので考えなくて良い.
2.leaders[i]==i*roomSize+1の場合,部屋[0,i)は全て確定するのでfriendPlaceが追加される余地がない.ここでfriendPlaceはleaders[i]よりも小さいことが保証されているのでfriendPlaceは部屋iには入れる.
3.その他.普通に入れる.

2,3の場合は部屋iには入れるので前からカウント(+1)していけば部屋0~iは入れないが,i+1からjは入れるみたいな状況のときにi+1のときにカウントが0から再カウントされるので大丈夫.