いくら『1日1問TopCoderの問題を解く!』って意気込んでも、1日じゃ解けない問題とかあるよね。
今回は、自分が初参加したSRM447 DIV2の500点問題を解いてみた。あまりに遅すぎたために点数は150.00点。
問題を一目見たときに「これRedandBlackみたいにやれば解けるな」と思ったのが間違いだった。様々な条件がこの問題には潜んでいたのだ。
それを読み解く読解力・・・というよりも英語力の欠如。これは痛い。
なんにせよ一応解けたので貼っておく。
#include <iostream> #include <algorithm> #include <vector> using namespace std; class KnightsTour { public: char field[12][12]; int cost[12][12]; int count; static int direx[8]; static int direy[8]; int costCul(int x, int y) { int cnt = 0; for(int i = 0; i < 8; i++) { if(field[y+direy[i]][x+direx[i]] != '*') cnt++; } return cnt; } class Cell { public: int x, y, cost; Cell(int dx, int dy, int dc) { x = dx; y = dy; cost = dc; } Cell() {}; bool operator<(const Cell& c) const { if(cost == c.cost) { if(y == c.y) { return x < c.x; } else { return y < c.y; } } else { return cost < c.cost; } } }; void rec(int x, int y) { if(field[y][x] == '*') return; Cell cells[8]; cout << x << ":" << y << endl; count++; field[y][x] = '*'; for(int i = 0; i < 8; i++) { cost[y + direy[i]][x + direx[i]]--; } for(int i = 0; i < 8; i++) { if(field[y + direy[i]][x + direx[i]] == '*') { Cell c(0, 0, 100); cells[i] = c; } else { Cell c(x + direx[i], y + direy[i], cost[y + direy[i]][x + direx[i]]); cells[i] = c; } } sort(cells, cells+8); rec(cells[0].x, cells[0].y); } int visitedPositions(vector<string> board) { int x, y; for(int i = 0; i < 12; i++) { for(int j = 0; j < 12; j++) { field[i][j] = '*'; } } for(int i = 2; i < 10; i++) { string str = board[i-2]; for(int j = 2; j < 10; j++) { field[i][j] = str[j-2]; if(field[i][j] == 'K') { x = j; y = i; } } } for(int i = 0; i < 12; i++) { for(int j = 0; j < 12; j++) { cost[i][j] = 9; } } for(int i = 2; i < 10; i++) { for(int j = 2; j < 10; j++) { cost[i][j] = costCul(j, i); } } count = 0; rec(x, y); return count; } }; int KnightsTour::direx[8] = {2, 1, 2, 1, -2, -1, -2, -1}; int KnightsTour::direy[8] = {1, 2, -1, -2, 1, 2, -1, -2};
各セルに移動可能な場所の数だけの重みをつけ、その重みの少ない方へ移動するという条件。もし重みが同じならば列番号、行番号を見て小さい方へと移動する・・・。
このあたりの移動条件が完全に抜けていたため、本番ではまるで違う答えが出ていたのだ。
それとこの問題ではC++言語に対する理解の低さも浮き彫りにしてくれた。ICPCで使い始めてそのまま使ってきたが、もっと勉強しなきゃスラスラとプログラムを書くのは無理だな。