AtCoder Beginner Contest 325
A - Takahashi san : AC(1:21)
B - World Meeting : AC(7:58)
C - Sensors : AC(15:20)
D - Printing Machine : WA
A - Takahashi san
ある人の名前と苗字が文字列$${S,T}$$として与えられ、苗字に敬称をつけ「(苗字) san」として出力する問題
自分の回答
int main(){
string S;
cin >> S;
printf("%s san", S.c_str());
}そのまま
公式解説
省略
B - World Meeting
ある会社は世界各地に$${N}$$個の拠点があり、各拠点には$${W_{i}}$$人の社員が所属し、世界標準時が$${0}$$時の時$${X_{i}}$$時である
全社で$${1}$$時間の会議を開くとき、各社員は拠点における時刻が9:00-18:00の時間帯に会議の時間が完全に含まれる場合のみ参加できる
最大で何人の社員が会議に参加することができるか求める問題
自分の回答
int main(){
int N;
cin >> N;
vector<int> T(24, 0);
for(int i = 0; i < N; i++){
int w, x;
cin >> w >> x;
for(int j = 9; j < 18; j++){
T[(j + x) % 24] += w;
}
}
int ans = 0;
for(int i = 0; i < 24; i++){
ans=max(ans, T[i]);
}
printf("%d\n", ans);
}拠点ごとに何時開始なら参加できるかを調べてその時間に社員数を追加
公式解説
省略
C - Sensors
$${H}$$行$${W}$$列のマス目の上にセンサが置かれており、文字列$${S_{i,j}}$$が「#」のときマス$${(i,j)}$$にセンサが置かれている
センサは周囲$${1}$$マスにあるセンサと連動していて、連動するセンサを$${1}$$つの大きなセンサとしたとき、それがいくつあるか求める問題
自分の回答
int main(){
int H, W;
cin >> H >> W;
vector<vector<char>> S(H + 2, vector<char>(W + 2, '.'));
for(int i = 1; i <= H; i++){
for(int j = 1; j <= W; j++){
cin >> S[i][j];
}
}
int ans = 0;
vector<int> di = {-1,-1,0,1,1,1,0,-1}, dj = {0,1,1,1,0,-1,-1,-1};
for(int i = 1; i <= H; i++){
for(int j = 1; j <= W; j++){
if(S[i][j] == '.'){
continue;
}
ans++;
queue<pair<int, int>> bfs;
bfs.push({i, j});
S[i][j] = '.';
while(!bfs.empty()){
auto [ni, nj] = bfs.front();
bfs.pop();
for(int k = 0; k < 8; k++){
int gi = ni + di[k], gj = nj + dj[k];
if(S[gi][gj] == '.'){
continue;
}
bfs.push({gi, gj});
S[gi][gj] = '.';
}
}
}
}
printf("%d\n", ans);
}各マスを見て行ってセンサがあったらそこから幅優先探索で大きなセンサを調べていくのを繰り返して終わり
公式解説
省略
D - Printing Machine
$${N}$$個の商品がベルトコンベアを流れており、各商品は$${T_{i}}$$秒後に印字機の範囲に入り、その$${D_{i}}$$秒後に印字機の範囲から出る
印字機は$${1}$$秒間に$${1}$$つ範囲内にある商品に一瞬で印字することができ、入った瞬間や出ていく瞬間にも印字することができる
最大で何個の商品に印字することができるか求める問題
自分の回答
区間スケジューリング問題の要領で、ケツの近い順、ただしそれが入る以前に入っているものがあればそれを、って感じで合ってると思うんだけど実装が上手くいかんかった
公式解説
using ll = long long;
int main() {
int n;
cin >> n;
vector<pair<ll, ll>> v;
for (int i = 0; i < n; i++) {
ll t, d;
cin >> t >> d;
v.emplace_back(t, t + d);
}
sort(v.begin(), v.end());
priority_queue<ll, vector<ll>, greater<>> pq;
int it = 0;
int ans = 0;
for (ll i = 0;; i++) {
if (pq.empty()) {
if (it == n) break;
i = v[it].first;
}
while (it < n and v[it].first == i) {
pq.push(v[it++].second);
}
while (!pq.empty() and pq.top() < i) pq.pop();
if (!pq.empty()) {
pq.pop();
++ans;
}
}
cout << ans << endl;
}https://atcoder.jp/contests/abc325/editorial/7448より
まず入るのが早い順に今見ている時刻に何が入っているかを入れるのか
それでその中でケツの近い順
なるほど