Avoid K Palindrome 2

https://atcoder.jp/contests/abc363/editorial/10481 によると、next_permutationを使うのが想定とのこと。

なんと 私は28言語でnext_permutationを実装しています。

Lua

現時点で私しかACしていません。

#!/usr/bin/lua
reverse=function(a,start,size)
	local end_=start+size-1
	for i=0,size/2-1 do
		z=a[start+i]
		a[start+i]=a[end_-i]
		a[end_-i]=z
	end
end
next_permutation=function(a,n)
	if not n then n=#a end
	if n<0 or #a<n then
		return false
	end
	local i=0
	reverse(a,n,#a+1-n)
	i=#a-1
	while i>=1 do
		if a[i]<a[i+1] then break end
		i=i-1
	end
	if i<1 then
		reverse(a,1,#a)
		return false
	end
	local k=i
	i=#a
	while i>=k+1 do
		if a[k]<a[i] then break end
		i=i-1
	end
	local l=i
	local z=a[k]
	a[k]=a[l]
	a[l]=z
	reverse(a,k+1,#a+1-(k+1))
	return true
end

n=io.read("*n")
k=io.read("*n")
io.read("*l")
s=io.read("*l")
a={}
for i=1,n do
	a[i]=s:byte(i)
end
table.sort(a)
r=0
repeat
	i=n-k+1
	while i>0 do
		x=i
		y=i+k-1
		while x<y do
			if a[x]~=a[y] then
				break
			end
			x=x+1
			y=y-1
		end
		if x>=y then
			break
		end
		i=i-1
	end
	if i<=0 then
		r=r+1
	end
until not next_permutation(a)
print(r)

Fortran

(こちらは数えるぐらいはAC者がいるようですが)

implicit none
interface
subroutine reverse(a_,start_,size_)
	integer a_(*)
	integer start_,size_
end
logical function next_permutation(a_,n_)
	integer a_(:)
	integer n_
end
end interface
integer n,k,r,i,j,x,y
character(:), allocatable :: s
integer, allocatable :: a(:)
read(*,*) n,k
allocate(character(n+1) :: s)
allocate(a(n))
read(*,*) s
do i=1,n
	a(i)=ichar(s(i:i))
enddo
do i=1,n-1
	do j=i+1,n
		if(a(i).gt.a(j)) then
			r=a(i)
			a(i)=a(j)
			a(j)=r
		endif
	enddo
enddo

r=0
do while(.true.)
	i=n-k+1
	do while(i.gt.0)
	 	x=i
		y=i+k-1
		do while(x.lt.y)
			if(a(x).ne.a(y)) exit
			x=x+1
			y=y-1
		enddo
		if(x.ge.y) exit
		i=i-1
	enddo
	if(i.le.0) r=r+1
	if(.not.next_permutation(a,size(a))) exit
enddo
write(*,"(i0)") r
end

subroutine reverse(a_,start_,size_)
	integer a_(*)
	integer start_,size_
	integer end_,i_
	integer z_
	end_=start_+size_-1
	do i_=0,size_/2-1
		z_=a_(start_+i_)
		a_(start_+i_)=a_(end_-i_)
		a_(end_-i_)=z_
	end do
end

logical function next_permutation(a_,n_)
	integer a_(:)
	integer n_
	integer i_,k_,l_
	integer z_
	next_permutation=.false.
	if((0.le.n_).and.(n_.le.size(a_))) then
		call reverse(a_,n_,size(a_)+1-n_)
		i_=size(a_)-1
		do while(i_.ge.1)
			if(a_(i_).lt.a_(i_+1)) then
				exit
			endif
			i_=i_-1
		enddo
		if(i_.lt.1) then
			call reverse(a_,1,size(a_))
		else
			k_=i_
			i_=size(a_)
			do while(i_.ge.k_+1)
				if(a_(k_).lt.a_(i_)) then
					exit
				endif
				i_=i_-1
			enddo
			l_=i_;
			z_=a_(k_)
			a_(k_)=a_(l_)
			a_(l_)=z_
			call reverse(a_,k_+1,size(a_)+1-(k_+1))
			next_permutation=.true.
		endif
	endif
end

Perl (240725追記)

現時点で私しかACしていません。

TLEにかなり苦しめられましたが、N==10かつ重複がない場合は3628800を出力して終了することでなんとかACできました。

#!/usr/bin/perl
use strict;
use List::Util 'uniqint';

sub permute(&@){
	my $code = shift;
	my @a = sort {$a <=> $b} @_;
	for(;;){
		$code->(@a);
		my $i;
		#push(@a,reverse splice @a, $n);  # partial_permutationに使うものだが、Perlの場合どうやって$nを渡すべきなんだろう…
		for($i=$#a-1;$i>=0;$i--){if($a[$i]<$a[$i+1]){last;}}
		if($i<0){return;}
		my $k=$i;
		for($i=$#a;$i>=$k+1;$i--){if($a[$k]<$a[$i]){last;}}
		my $l=$i;
		@a[$k,$l]=@a[$l,$k];
		push(@a, reverse splice @a, $k+1);
	}
}

<>=~$";
my $n=$`;
my $k=$';
my $s_=<>;
chomp($s_);
my @s=map {ord} split('',$s_);
my $count = uniqint @s;
if($n==10 && $count==10) {
  print 3628800;
  exit;
}

my $r=0;
permute {
	my $i=$n-$k;
	for(;$i>=0;$i--){
		my $x=$i;
		my $y=$i+$k-1;
		for(;$x<$y;$x++,$y--){
			last if($_[$x] != $_[$y]);
		}
		last if($x>=$y);
	}
	$r++ if($i<0);
} @s;
print $r."\n";