ABC150-C 備忘録 p.21
itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。
考察の流れ
N進数と考えて、引き算してから 10進数に変換？
いや順列だから N進数ではないのか…
全探索っぽいが、さっぱり分からないので解説を見る
色々と調べた結果、順列を生成しなければならないことが判明
㊗初順列生成
方法①：DFS（深さ優先探索）を使う
方法②：next_permutation 関数を使う（C++にはあるらしい）（そしてprev_permutation 関数もあるらしい）
今回は②を採用し、next_permutation 関数っぽいものを自作してみる
（参考にさせて頂いた記事）
#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 でも解いてみること
引き続き、のんびり精進します。