[Java]AGC022-A next_permutation

問題

atcoder.jp

提出したやつ

atcoder.jp

next_permutation使うだけの覚えゲー

javaにはこの関数ないので死に覚えた

 c++やpythonには配列等を渡してその各要素を並べ替えた時のすべての列を辞書順に並び替えた時の次の配列をnext_permutation関数で持ってくることができる。

（まあアルゴリズム知ってりゃいいだけの話かも）

（C++の上位提出者のコード見てると半分強くらいしかこの関数使ってない...（残りは配列だったりsetだったり））

なのでjavaでもこの関数持っておきたい

自分じゃ到底かけないのでlewinさんのコードを拝借して自分なりに書き直した。
（書き直したのでバグってるかも）

    public static class Permutation {
        public static int startIndexOfDescendingOrder(int[] p){
            //return i
            //mean p[i-1]<p[i]&&p[i]>p[i+1]>p[i+2]>...>p[p.length]
            for(int i=p.length-2;i>=0;i--){
                if(p[i]-p[i+1]>=0)continue;
                return i+1;
            }
            return 0;
        }
        public static <T> int startIndexOfDescendingOrder(List<T> list,Comparator<T> comparator){
            //return i
            //mean p[i-1]<p[i]&&p[i]>p[i+1]>p[i+2]>...>p[p.length]
            for(int i=list.size()-2;i>=0;i--){
                if(comparator.compare(list.get(i),list.get(i+1))>=0)continue;
                return i+1;
            }
            return 0;
        }
        public static boolean nextPermutation(int[] p) {
            int firstIndex=startIndexOfDescendingOrder(p);
            if(firstIndex==0)return false;
            int ng=p.length;
            int ok=firstIndex;
            firstIndex--;
            while(Math.abs(ng-ok)>1){
                int mid=(ng+ok)/2;
                if(p[mid]>p[firstIndex]){
                    ok=mid;
                }else{
                    ng=mid;
                }
            }
            int t = p[firstIndex];
            p[firstIndex] = p[ok];
            p[ok] = t;
            //p[firstIndex+1]以降のものを逆にする
            firstIndex++;
            int[] reverseTmpArr=new int[p.length-firstIndex];
            for(int i=0;i<reverseTmpArr.length;i++){
                reverseTmpArr[i]=p[p.length-i-1];
            }
            for(int i=0;i<reverseTmpArr.length;i++){
                p[firstIndex+i]=reverseTmpArr[i];
            }
            return true;
        }
        public static <T> boolean nextPermutation(List<T> list,Comparator<T> comparator) {
            int firstIndex=startIndexOfDescendingOrder(list,comparator);
            if(firstIndex==0)return false;
            int ng=list.size();
            int ok=firstIndex;
            firstIndex--;
            //MGR式
            while(Math.abs(ng-ok)>1){
                int mid=(ng+ok)/2;
                if(comparator.compare(list.get(mid),list.get(firstIndex))>0){
                    //真に大きいならokの領域
                    ok=mid;
                }else{
                    ng=mid;
                }
            }
            T t = list.get(firstIndex);
            list.set(firstIndex,list.get(ok));
            list.set(ok,t);
            //インデックスがfirstIndex+1以降のものを逆にする
            firstIndex++;
            List<T> reverseTmpList=list.subList(firstIndex,list.size());
            Collections.reverse(reverseTmpList);
            for(int i=0;i<reverseTmpList.size();i++){
                list.set(firstIndex+i,reverseTmpList.get(i));
            }
            return true;
        }
        public static <T> boolean prevPermutation(List<T> list,Comparator<T> comparator){
            return nextPermutation(list,comparator.reversed());
        }
    }

再帰じゃなくてループにしてるので名前空間を汚染しない。

元のから書き直したところであまり早くなってる印象はない。まあ嫌がらせみたいなテストケースが来た時用。

所感

static class使って名前空間を分けてる人自分以外に初めて見た。
このやり方正しかったのか。