結果
2完 [A(300), B(600)] 139:48 ペナルティ: 7 (139:48 -> 174:48)
・順位: 817位 (Rated)
・パフォーマンス: 1482
・Rating変化: 1246 -> 1272 (+26) [Rating最高値]
各問題の解法
A問題 (300点)
提出詳細
計算量 O(HW)
初期の黒いマスから隣接する4マスにBFSの要領で、距離を埋めていく。
2手以降前の黒マスは既に埋められているため、見る必要がない(対象のリストから消す)
int H, W;
bool InMap(const int h, const int w)
{
return h >= 0 && w >= 0 && h < H && w < W;
}
int main()
{
int dx[4] = { -1, 0, 0, 1 }, dy[4] = { 0, -1, 1, 0 };
const int INF = 1000000010;
cin >> H >> W;
vector<pair<int, int>> black;
black.reserve(H * W);
//INF = 初期の黒からの最短距離がまだ不明なマス
vector<vector<int>> value(H, vector<int>(W, INF));
for (int i = 0; i < H; i++)
{
string s;
cin >> s;
for (int j = 0; j < W; j++)
{
if (s[j] != '#')continue;
black.emplace_back(i, j);
//初期値で黒マスのところは0にする
value[i][j] = 0;
}
}
int black_count = black.size(), cur = 1;
//すべてが黒のマスになる（距離が計算される）まで繰り返す
while(black_count < H * W) {
vector<pair<int, int>> next_black;
for(auto& b : black) {
int nowH = b.first, nowW = b.second;
for(int i = 0; i < 4; i++) {
//みるマス
int nextH = nowH + dy[i], nextW = nowW + dx[i];
//範囲外なら無視
if (!InMap(nextH, nextW)) continue;
//未計算のマスだったら、黒のマスのカウントを増やす
//次の計算に使うため、nextにマスを追加する
if(value[nextH][nextW] == INF) {
black_count++;
next_black.emplace_back(nextH, nextW);;
value[nextH][nextW] = cur;
}
}
}
//今回計算に使った黒マスは、次以降は必要ないので、blackをnextにする
black.swap(next_black);
//手数を増やす
cur++;
}
cout << cur - 1 << endl;
}
B問題 (600点)
提出詳細
計算量 O(N)
上、下、左、右、それぞれ独立して計算を行う、
高橋くんの手番では、それぞれのカウントを1増やす。
青木くんの手番では、高橋くんの逆（上なら下、右なら左）のカウントを1減らす。ただし、その操作を行うことによって盤面から落ちる可能性があるときは、操作を行わない。
高橋くんの操作の直後、上下左右でいずれかが盤面から落とせる場合はNO、そうでない場合はYESを出力。
int H, W, N, sr, sc;
string S, T;
cin >> H >> W >> N >> sr >> sc >> S >> T;
bool flag = true;
int l = 0, r = 0, u = 0, d = 0,
l_ok = sc, r_ok = W - sc + 1,
u_ok = sr, d_ok = H - sr + 1;
for (int i = 0; i < N; i++) {
//各方向へのカウントを増やす
if (S[i] == 'R') r++;
else if (S[i] == 'L') l++;
else if (S[i] == 'U') u++;
else if (S[i] == 'D') d++;
if (r >= r_ok || l >= l_ok || u >= u_ok || d >= d_ok) {
flag = false;
break;
}
//逆方向に引き戻す(ただし盤面から出ない範囲で)
if (T[i] == 'R' && (l > 0 || abs(l + 1) < r_ok)) l--;
else if (T[i] == 'L' && (r > 0 || abs(r) + 1 < l_ok)) r--;
else if (T[i] == 'U' && (d > 0 || abs(d) + 1 < u_ok)) d--;
else if (T[i] == 'D' && (u > 0 || abs(u) + 1 < d_ok)) u--;
}
cout << (flag ? "YES" : "NO") << endl;
感想
AGCでは過去最高のパフォーマンス、過去問を含めて初めて600点に正解しました。
最初の1回（0完、パフォ29で24→44）を除いて、初めてAGCでレートを上げました。
600は嘘解法が通るみたいで、想定しているより通している人が多く、結果として（想定より）パフォが500程度低かったのかなーと思います。まあ仕方ないですね。
おそらく私の解き方は嘘解法ではないので、実力的にはperf2000程度でしょうか…？
次回のAGCでも冷やさないようにがんばります。
