ABC150-C 備忘録 p.21

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

C - Count Order

考察の流れ

N進数と考えて、引き算してから 10進数に変換？
いや順列だから N進数ではないのか…

全探索っぽいが、さっぱり分からないので解説を見る

色々と調べた結果、順列を生成しなければならないことが判明
㊗初順列生成

方法①：DFS（深さ優先探索）を使う
方法②：next_permutation 関数を使う（C++にはあるらしい）（そしてprev_permutation 関数もあるらしい）

今回は②を採用し、next_permutation 関数っぽいものを自作してみる

next_permutationがイマイチよくわからなかったのでまとめてみた - Qiita

（参考にさせて頂いた記事）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ABS(x)		((x)<0 ? -(x):(x))
void int_swap(int*a, int*b){ int tmp=(*a); (*a)=(*b); (*b)=tmp; }
void int_switch(int* n, int d){ int x,i,j; for(i=0,j=d-1; i<d/2; i++,j--){ x=n[i]; n[i]=n[j]; n[j]=x; } }

int next_int_permutation(int arr[], unsigned int n){
	int i;
	for(i=n-2; i>=0; i--){
		if( arr[i] < arr[i+1] ){
			int j = n;
			do{
				j--;
			}while( arr[i] >= arr[j] );

			int_swap( &arr[i], &arr[j] );
			int_switch( arr+i+1, n-(i+1) );	// i+1から末尾までを反転
			return 1;
		}
	}
	return 0;
}

int main(){
	int i, j, n, p[16]={0}, q[16]={0}, arr[16]={0}, a=1, b=1, cnt=1, flag=0;
	scanf("%d",&n);

	for(i=0; i<n; i++){ scanf("%d", &p[i]); p[i]--; }	// 1~ を 0~ にする
	for(i=0; i<n; i++){ scanf("%d", &q[i]); q[i]--; }	//
	for(i=0; i<n; i++){ arr[i]=i; }						// 初期順列 { 0, 1, …, n-1 } を生成 

	do{
		if( !memcmp(p, arr, sizeof(p)) ){ a=cnt; flag++; }	// arr[]とp[]が一致
		if( !memcmp(q, arr, sizeof(p)) ){ b=cnt; flag++; }	// arr[]とq[]が一致
		if( flag==2 ){ break; }								// aとbが両方判明した
		cnt++;
	}while(next_int_permutation(arr, n));					// 次の順列を生成
	printf("%d\n", ABS(a-b));
	return 0;
}

まとめ

・長い戦いだった…
・他言語では標準ライブラリにある関数を自作する作業、つらいけど達成感がすごい
・後で prev_permutation 関数も作ってみること
・後で DFS でも解いてみること

引き続き、のんびり精進します。

#note初心者 #備忘録 #AtCoder #ABC #競技プログラミング #競プロ #C言語 #数学 #順列