ACM-ICPC 2016 Asia Tsukuba Regional, B 解法

B: Quality of Check Digits

問題

一桁の数同士のX演算の定義テーブルが与えられる。iXi = 0が保証されている（i = 0 .. 9）。ある4桁の数 abcd (leading zerosを許す) に対して、e = (((0Xa)Xb)Xc)XdをCheckDigitとして5桁のabcdeについて、書き間違えを判定したい。

• Type1: ある一桁を別の一桁の数に書き間違える (e.g. 20163 -> 00163)
• Type2: 隣り合う異なる数を逆に書き間違える (e.g. 20163 -> 02163)

「上の任意の書き間違えを1回したら検出できる」とは限らないabcdは何通りあるか求めよ。

解法

全探索 DFS
4桁決めて5桁目を求める。全ての書き間違えを試しcheckが機能していないものがあればカウント。

コード

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int X[10][10];

int a[5];

int acc(int len = 5) {
    int ret = 0;
    REP (i, len) ret = X[ret][a[i]];
    return ret;
}

int dfs(int i) {
    if (i == 4) {
	a[4] = acc(4);

	REP (j, 5) {
	    int bak = a[j];
	    REP (k, 10) {
		if (bak != k) {
		    a[j] = k;
		    int ac = acc();
		    a[j] = bak;
		    if (ac == 0) return 1;
		}
	    }
	}

	REP (j, 4) {
	    if (a[j] != a[j+1]) {
		swap(a[j], a[j+1]);
		int ac = acc();
		swap(a[j], a[j+1]);
		if (ac == 0) return 1;
	    }
	}

	return 0;
    } else {
	int ret = 0;
	REP (k, 10) {
	    a[i] = k;
	    ret += dfs(i+1);
	}
	return ret;
    }
}

int main() {

    REP (i, 10) REP (j, 10) scanf("%d", &X[i][j]);
    int ans = dfs(0);
    printf("%d\n", ans);

    return 0;
}

感想

サンプルが強い