TopCoder SRM 575 Div2 解説
こんにちは。
以前からずっとやろうと思っていてできていなかったTopCoderに先日はじめて参加してみました。事前に574回のを見ていったのですが、雰囲気楽勝そう？とか思ったら、本番全然できなくて泣きそうになりました。
自己分析してみると574回はグラフ探索系の問題が中心で僕が得意なのが多かったのですが、575回は深さ優先探索中心の問題でぱっと解法が思いつきませんでした。まだまだ精進が足りないようです。
これが初挑戦だったので、とりあえず、何度かやるうちには少なくとも青コーダーくらいにはなりたいと思いますw
注) 記事で紹介してある正解コードはライブラリのインクルードなどの部分は含んでいないので、適宜追加してください。
250点問題
この問題は、与えられた文字列の任意の2文字を入れ替えたときにできる文字列の種類の数を答える問題です。与えられる文字列の長さはそれほど長くなく、新しく作られる文字列の数は最大でも
メモリの使用量を少なくしたければ、実はもっと簡単にできます。ある文字列を入れ替えたときにこれまでに見つけていない文字列が現れる場合というのは、実は次のような場合です。
- 今、入れ替えようとしているi文字目とj文字目が異なる文字である
- 今、入れ替えようとしているi文字目とj文字目は同じ文字であるが、同じ文字同士の入れかえを行うのは初めてである
1番目は直観的に理解できると思います。2番目はどうして出てくるのかというと、同じ文字同士を入れ替えると、最初の文字列と同じ文字列が出てきます。ということは、1回目に同じ文字同士を入れ替えたときには、数を増やす必要があります。ところが2回目以降は、すでに見つけてしまった最初と同じ文字列が再び現れることになるので、ここでは数を増やす必要はありません。
方針が分かったところで、以下が正解のコードです。
class TheSwapsDivTwo {
public:
int find(vector <int> sequence) {
int a = 0;
bool s = false;
int length = sequence.size();
for(int i=0; i<length; i++) {
for(int j=i+1; j<length; j++) {
if(sequence[i] != sequence[j]) {
a++;
continue;
} else if(!s) {
a++;
s = true;
}
}
}
return a;
}
};
500点問題
この問題では、ある数字Cに対してJohnとBrusが交互に次の操作を行います。
- Cの1とC以外の約数を1つ選ぶ
- 選んだ数をCから引いて順番を交代
そして、1とC以外の約数を選べなくなった方が負けというゲームです。つまり、Cが素数になったら負けというわけです。
曲者は問題文にある「the optimal strategy」がどんな戦略なのかがよく分からないという点です。ただ、それほど難しい戦略は必要なく、Cから遷移できる数のうち自分が確実に勝利できる数が1つでも存在すれば、自分にCが回ってきたときに勝利できる、という条件です。与えられる数字は高々1000ですので、メモ化しておいて、重複探索をなくせば難なく解答を得ることができます。
これさえわかれば、あとは深さ優先探索で、手番の交代を考慮しつつ、探索を行うだけです。以下が正解のコードになります。
class TheNumberGameDivTwo {
public:
int memo[1001];
string find(int n) {
memset(memo, -1, sizeof(int) * 1001);
return f(n) == 1 ? "John" : "Brus" ;
}
int f(int n) {
if(memo[n] != -1) return memo[n];
for(int i=2; i<n; i++) {
if(n % i == 0) {
if(f(n-i) == 0) {
memo[n] = 1;
return 1;
}
}
}
memo[n] = 0;
return 0;
}
};
1000点問題
最後の問題はチェスボードに対してL字型のタイルが最大何個並ぶかを答えるプログラムを作る問題です。ただし、L字型タイルの置き方には次の制限があります。
- タイルは角になるマスが必ず黒マスに重ならなくてはならない
- タイルはチェスボード上に配置されたコマや、すでに置いたタイルと重なってはいけない
これもよく見る深さ優先探索の問題のように思えるのですが、ある黒マスにタイルを置くとすると、そこだけで最大4通りの置き方があり、なおかつ黒マスは概算で最大100くらいはあるので、全体を探索すると、とても計算量が足りません。
ポイントはこの問題は、タイルを置く順番はどうでもよく、タイルの向きだけが置ける数に関係しているという点です。したがって、あるタイルの置き方を最大4通り試したら、次に探索するタイルで、わざわざ置き方を試してあるタイルの置き方をもう一度試す必要はないのです。
ですので、深さ優先探索の中で今注目しているタイルのマスより右もしくは下にあるタイルについてだけ置き方を考えればよいということになります。こうすると、最大のテストケースである48×4のボードの場合には少し実行を待ちますが、おおむね目標値の2秒以内には収まるはずです。
以下が正解のコードになります。
class TheTilesDivTwo {
public:
void dfs(vector<string>& board, int r, int c, int depth, int& M) {
int h = board.size();
int w = board[0].size();
bool locate = false;
for(int i=r; i<h; i++, c = 0) {
for(int j=c; j<w; j++) {
if((i+j) % 2 == 0) {
for(int k=0; k<4; k++) {
int i1 = i + ofs[k][0];
int j1 = j + ofs[k][1];
if(i1 < 0 || j1 < 0 || i1 >= h || j1 >= w) continue;
int i2 = i + ofs[k+1][0];
int j2 = j + ofs[k+1][1];
if(i2 < 0 || j2 < 0 || i2 >= h || j2 >= w) continue;
if( board[i][j] == '.' &&
board[i1][j1] == '.' &&
board[i2][j2] == '.') {
board[i][j] = 'O';
board[i1][j1] = 'O';
board[i2][j2] = 'O';
int a = M;
dfs(board, i, j, depth+1, a);
if(a > M) {
M = a;
}
board[i][j] = '.';
board[i1][j1] = '.';
board[i2][j2] = '.';
locate = true;
}
}
}
}
}
if(!locate) {
M = depth;
}
}
int find(vector <string> board) {
int a = 0;
dfs(board, 0, 0, 0, a);
return a;
}
};
感想
これだけしたり顔で答えを載せておきながら、本番の最中は全く良い解法が思いつきませんでした・・・。
僕はどちらかというとグラフ探索系の問題が得意なのですが、今回は深さ優先中心でいろいろやられました。
偏った勉強ではダメですね。次はもっと良い結果を出せるようにがんばります。