TopCoder SRM 576 Div2 解説
こんにちは。
前回は苦杯をなめたSRMですが、今回はHard以外通して青に昇格しました。Hardは剰余を取るのを忘れるという凡ミスでテストケースが通らず時間切れ。あと少し早く気付ければ・・・。
さて解説に行きたいと思いますが、今回の問題はMiddleが簡単なグラフ探索を用いる以外はEasyもHardも割とごり押しで解けました。では、実際に問題ごとに解説していきたいと思います。
Easy (256点)
この問題は天井から1分ごとに滴り落ちる水滴が、地面にレイヤー状に並べたスポンジに何滴落ちるかを数える問題です。
いろいろな人の解答を見ると、天井の各位置から滴り落ちる滴が何番目のレイヤーに落ちるかをわざわざ判定している人がいるのですが、そんな面倒なことをしなくても、一回あるスポンジに滴った水滴はより下のレイヤーのスポンジに落ちることはないわけですから、vectorに格納されている値を0にしてしまえばよいのです。
そうすれば、いちいちどの滴がどのスポンジに落ちるかという面倒な判定をせず適当にforループを回してあげるだけで正解にたどり着けます。
以下が正解のコードです。
class TheExperimentDiv2 {
public:
vector <int> determineHumidity(vector <int> intensity, int L, vector <int> leftEnd) {
int N = leftEnd.size();
vector <int> result(N, 0);
for(int i=0; i<N; i++) {
for(int j=leftEnd[i]; j<leftEnd[i]+L; j++) {
result[i] += intensity[j];
intensity[j] = 0;
}
}
return result;
}
}
Middle (576点)
この問題はマリオみたいなキャラクター(Manao)がある位置にあるコインを取るために必要なハシゴの最短の長さを求めるという問題です。
最初は一塊のブロックをノードとしてグラフを作るのかな？と思いましたが、ブロック1つ1つをノードとみる方が実装はずっと簡単ですね。
具体的には、
- 横移動は隣のブロックのみ移動可能。移動コストは0(高さが変わらないのでハシゴはいらない)
- 縦移動は同じ列にあるブロックのいずれにも移動可能。移動コストは高さの差分。
というグラフを作ってあげます。
このグラフ上を幅優先探索し、各ノードに至るのに必要な最低のハシゴの長さを求めます。最後にコインのある場所にあるノードが持っているハシゴの長さを返してあげればOKです。
以下が正解のコードになります。
class ArcadeManao {
public:
int shortestLadder(vector <string> level, int coinRow, int coinColumn) {
int N = level.size();
int M = level[0].size();
vector<vector<block> > B(N, vector<block>(M));
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(level[i][j] == 'X') {
if(j-1 >= 0) {
B[i][j].to.push_back(pii(i, j-1));
B[i][j].cost.push_back(0);
}
if(j+1 < M) {
B[i][j].to.push_back(pii(i, j+1));
B[i][j].cost.push_back(0);
}
for(int k=0; k<N; k++) {
if(i == k) continue;
if(level[k][j] == 'X') {
B[i][j].to.push_back(pii(k, j));
B[i][j].cost.push_back(abs(k-i));
}
}
}
}
}
queue<pii> que;
vector<vector<int> > lad(N, vector<int>(M, 100000));
for(int j=0; j<M; j++) {
que.push(pii(N-1, j));
lad[N-1][j] = 0;
}
while(!que.empty()) {
pii p = que.front();
que.pop();
int r = p.first;
int c = p.second;
int neighbor = B[r][c].to.size();
for(int k=0; k<neighbor; k++) {
int r1 = B[r][c].to[k].first;
int c1 = B[r][c].to[k].second;
int cost1 = max(lad[r][c], B[r][c].cost[k]);
if(cost1 < lad[r1][c1]) {
lad[r1][c1] = cost1;
que.push(pii(r1, c1));
}
}
}
return lad[coinRow-1][coinColumn-1];
}
}
(別のやり方)
他の人の解答を見ていて、なるほどこういうのもありか、と思ったので、そのやり方も紹介します。
基本的な方針は上のやり方と同じですが、すべてのブロックについて、そのブロックに行くための最短のハシゴの長さを求めるのではなく、与えられたハシゴの長さに対して、コインの場所までいけるのかいけないのかを幅優先探索で判定します。
その判定結果を用いて二分探索し、最終的なハシゴの長さを求めるというものです。どっちの方が計算コストが少ないかは微妙な気がしますが、雰囲気こっちのほうが賢そうです。
コードは書くのが面倒なので載せません。すみません。
Hard (1024点)
最後の問題は、アルファベットの小文字で与えられた部分行列を含むような幅Wの行列を生成するための入力文字列を求めるというものです。
入力文字列から行列を生成する方法は、一見難しそうですが、左上から右下に向かって、入力文字列に含まれる文字を順に充填していくだけというシンプルなものです。
ということは、ある部分行列を含む行列を生成するような長さLの文字列が存在するのかどうかは、次のやり方で判定ができます。
- 部分行列の文字が実際の行列の中でどの位置に現れるのかに注意しながら、入力文字列の何文字目から与えられるのかを求める
- 入力文字列の各位置が異なる文字を与えなければならないときには、その長さで目的の文字列は存在しない
- もし部分行列の文字すべてをうまく入れられる入力文字列があるなら、その長さで目的の文字列が存在
ある長さで目的を果たせる文字列が見つかったら、次はその文字列のうち、任意の文字を与えてもよい文字の数を数えます。その数の分だけ26の累乗を計算して、それを文字列数の合計に加えます。ここで注意しなくてはならないのは、答えはintの範囲を一時的に超えることがあるのでlong longを用いて数を数えておくことと、累乗を計算するときは必ず100,000,009の剰余を取りながら行うということです。僕はここで凡ミスをしました。
以下が正解のコードになります。
class CharacterBoard2 {
public:
int countGenerators(vector <string> fragment, int W, int i0, int j0) {
char S[10011];
int r = fragment.size();
int c = fragment[0].size();
int n = r * c;
ull total = 0;
for(int l=1; l<=W; l++) {
fill(S, S+l+1, '.');
int cnt = 0;
bool suc = true;
while(cnt < n) {
int nr = cnt / c;
int nc = cnt % c;
int m = ((nr + i0) * W + (nc + j0)) % l;
if(S[m] == '.') {
S[m] = fragment[nr][nc];
} else {
if(S[m] != fragment[nr][nc]) {
suc = false;
break;
}
}
cnt++;
}
if(suc) {
ull add = 1;
for(int i=0; i<l; i++) {
if(S[i] == '.') add = (add * 26) % 1000000009;
}
total += add;
}
}
return (int)(total % 1000000009);
}
}
感想
今回は方針さえ立てば、簡単にとける問題が多かったです。実装さえ間違えなければHardの方がMiddleよりも簡単なのではないでしょうか？
ともあれ、次回はDiv1なので、少し勉強してから望みたいと思います。