Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

http://codeforces.com/contest/983

A
えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。
B
dpしてまたdp
C
dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,nである時の最小コストとやると、2*10^8となって辛いです。しかし、i番目の人が乗った場合行き先がbiの人が必ずいるので、それを利用するとnを10試す必要がなくなって2で大丈夫になります。これで2*10^7*2で通ります。2*10^8/(4!)が通ってしまうのは少し解せない…。コードがだいぶエグい。

int N;
int A[MAX_N], B[MAX_N];
int dp[2010][9][10][10][10][2]; //i,at j,floor at; k, l, m floor to visit, B[i], visited?

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}
	rep(i, 0, N + 1) {
		rep(j, 0, 9) {
			rep(k, 0, 10) {
				rep(l, 0, 10) {
					rep(m, 0, 10) {
						rep(n, 0, 2) {
							dp[i][j][k][l][m][n] = inf;
						}
					}
				}
			}
		}
	}
	dp[0][A[0]][9][9][9][0] = A[0];
	//i, j, k, l, m, n
	rep(i, 0, N) {
		rep(k, 0, 10) {
			rep(l, 0, 10) {
				rep(m, 0, 10) {
					rep(n, 0, 2) {
						rep(j, 0, 9) {
							if(dp[i][j][k][l][m][n] == inf) continue;
								// debug(i, j, k, l, m, n);
							if(k == 9) { //visited
								MIN(dp[i + 1][A[i + 1]][B[i]][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][k][9][l][m][n], dp[i][j][k][l][m][n] + abs(k - j));
							}

							if(l == 9) {
								MIN(dp[i + 1][A[i + 1]][k][B[i]][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][l][k][9][m][n], dp[i][j][k][l][m][n] + abs(l - j));
							}

							if(m == 9) {
								MIN(dp[i + 1][A[i + 1]][k][l][B[i]][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][m][k][l][9][n], dp[i][j][k][l][m][n] + abs(m - j));
							}

							if(n == 1) { //visited
								MIN(dp[i + 1][A[i + 1]][k][l][m][0], dp[i][j][k][l][m][n] + abs(A[i + 1] - j));
							}
							else {
								MIN(dp[i][B[i]][k][l][m][1], dp[i][j][k][l][m][n] + abs(B[i] - j));
							}
						}
					}
				}
			}
		}
	}
	int res = inf;
	rep(i, 0, 9) {
		MIN(res, dp[N - 1][i][9][9][9][1]);
	}
	cout << res + 2 * N << "\n";
}