agc044_bの解き方の解説 Joker メモ化すれば十分幅優先探索(bfs)で間に合う
2020/05/25 13:05
感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。
AGC の B 問題 Joker、本番中に残り 30 分くらいで普通に幅優先探索すれば解けると気づいたが、30 分で書けずに敗退。悔しいからそのまま参考サイトを見ずに書いたら解けて更に悔しい・・
幅優先探索(bfs)
bfs は近い順に探索するアルゴリズムです。次のマスがチェック済みか確認し、未チェックだったらチェックする予定をキューメモしておきます。チェック時、更に次の前後左右のマスがチェック済みか確認して更にメモします。キューが空＝すべてチェック済みになるまでチェックしつづけます。
すべてのマスを探索する必要がない
今回の問題だと、1 人が席を立つたびに探索する必要があります。すべてのマスを毎回探索してしまうと最大 250,000 * 250,000 となり、10^11 程度で TLE してしまいます。
席を立つたびに全探索するのではなく、すべての席を先に探索しておく戦略を取ります。
初期値
6*6 マスの場合、初期値はこうなります。縦横に突っ切って席を立つのが最小となります。
0 0 0 0 0 0
0 1 1 1 1 0
0 1 2 2 1 0
0 1 2 2 1 0
0 1 1 1 1 0
0 0 0 0 0 011,12 マス目の人が席を立った場合
真ん中 4 マスの初期値が 2 だったところの右上のマスまで影響があります。他のマスは影響がありません。
0 0 0 0 0 0
0 1 1 0 * *
0 1 2 1 0 0 // ←ここの右から3マス目まで
0 1 2 2 1 0
0 1 1 1 1 0
0 0 0 0 0 0影響がなかったマスのまわりは探索しなくていい
探索した結果、値が更新されないマスが出てきます。このマスは既に探索済みとマークしてしまいます。そうると探索するマスが限定され、計算量が相当減ります。
できあがり
#include <bits/stdc++.h>
using namespace std;
int t;
vector<vector<int>> seats; // 人が座っているか管理する
vector<vector<int>> memo; // 席を立つコストを先にメモしておく
void bfs(int _y, int _x) {
queue<pair<int,int>> q;
q.push({_y,_x});
while(!q.empty()) {
auto&& yx = q.front(); q.pop();
int y = yx.first, x = yx.second;
// 隣のマスのコストは、min(計算済みコスト, チェックしているマスのコスト + 人が座っていたら)となる
if(y > 0 && memo[y - 1][x] > memo[y][x] + seats[y - 1][x]) {
memo[y - 1][x] = memo[y][x] + seats[y - 1][x];
q.push({y - 1, x}); // 値を更新したときだけ、探索対象にする
}
if(y < t - 1 && memo[y + 1][x] > memo[y][x] + seats[y + 1][x]) {
memo[y + 1][x] = memo[y][x] + seats[y + 1][x];
q.push({y + 1, x});
}
if(x > 0 && memo[y][x - 1] > memo[y][x] + seats[y][x - 1]) {
memo[y][x - 1] = memo[y][x] + seats[y][x - 1];
q.push({y, x - 1});
}
if(x < t - 1 && memo[y][x + 1] > memo[y][x] + seats[y][x + 1]) {
memo[y][x + 1] = memo[y][x] + seats[y][x + 1];
q.push({y, x + 1});
}
}
}
int main() {
cin >> t;
for(int y = 0; y < t; y++) {
vector<int> row;
for(int x = 0; x < t; x++) {
// 初期値は簡単に計算可能
row.push_back(min({x, t - x - 1, y, t - y - 1}));
}
memo.push_back(row);
vector<int> humanRow(t, 1);
seats.push_back(humanRow);
}
int result = 0;
for(int i = 0; i < t * t; i++) {
int number;
cin >> number;
number--;
int x = number % t; // 列は割った余り
int y = number / t; // 行は割った答え
result += memo[y][x]; // 席を立つコストは計算済みなので、そのまま足す
seats[y][x]--; // 席を立ったことをマーク
memo[y][x]--; // 席を立ったので、メモ済コストを減らす
bfs(y, x); // メモを更新したのでbfs
}
cout << fixed << result;
}