AtCoder abc312 参加メモ

UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) - AtCoder

B - TaK Code

制約が小さいので、すべての (i,j) から 9x9 マスを条件に沿っているか全探索すればいい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  // 座標(x,y) から 3x3マスの領域がすべて黒 かつ 8方位隣接マスが全て白か？
  auto f = [&](int x, int y, vector<vector<int>> v) -> bool {
    REP(i,5) REP(j,5) {
      int nx = x-1+i, ny = y-1+j;
      if (nx < 0 || ny < 0 || nx >= 9 || ny >= 9) continue;
      // 3x3の外
      if (nx < x || ny < y || nx > x+2 || ny > y+2) {
        if (v[nx][ny] == '#')  return false;
      } else {
        if (v[nx][ny] == '.')  return false;
      }
    }
    return true;
  };

  REP(i,n-8) REP(j,m-8) {
    vector v(9, vector<int>(9));
    REP(k,9) REP(l,9) v[k][l] = s[i+k][j+l];
    if (f(0,0,v) && f(6,6,v)) cout << i+1 << " " << j+1 << endl;
  }
  return 0;
}

C - Invisible Hand

単調性があるため二分探索できる。 金額が x のときの売り手、買い手の数を求め方に注意する。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());

  int ok = 1e9+5, ng = 0;
  while(abs(ok - ng) > 1) {
    int mid = (ok+ng)/2;
    int seller = upper_bound(a.begin(),a.end(),mid) - a.begin();
    int buyer = m - (lower_bound(b.begin(),b.end(),mid) - b.begin());
    if (seller >= buyer) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
  return 0;
}

D - Count Bracket Sequences

DP がうまく書けず、ACできず。悔しすぎる。

成績

緑落ち

tic40さんのユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)での成績：3502位
パフォーマンス：840相当
レーティング：1207→1175 (-32) :(
#AtCoder #ユニークビジョンプログラミングコンテスト2023夏(ABC312) https://atcoder.jp/users/tic40/history/share/abc312?lang=ja 

AtCoder abc311 参加メモ

Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder

B - Vacation Together

全探索。d 日目まで見ていき、全員が暇ならカウント+1, 一人でも暇でなければカウントリセットする。 カウントが最大の値が答え

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,d; cin >> n >> d;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  int ans = 0, now = 0;
  REP(i,d) {
    bool ok = true;
    REP(j,n) if (s[j][i] == 'x') ok = false;
    if (ok) now++;
    else now = 0;
    ans = max(ans,now);
  }
  cout << ans << endl;
  return 0;
}

C - Find it!

強連結成分分解で解いた。 dfs を 2 回行うことで閉路のグループに分解できる( 参考: https://manabitimes.jp/math/1250 )

ちなみに ACL にも SCC ライブラリがあるが、得られる頂点の順序がバラバラなため順序は正しく出力する必要がある。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<vector<int>> g(n),gr(n);
  REP(i,n) {
    int a; cin >> a; a--;
    g[i].push_back(a);
    gr[a].push_back(i);
  }

  vector<int> dir;
  vector<bool> used(n);
  auto dfs = [&](auto self, int i) -> void {
    if (used[i]) return;
    used[i] = true;
    for(auto v: g[i]) self(self,v);
    dir.push_back(i);
  };

  REP(i,n) dfs(dfs,i);
  auto dir1 = dir;
  reverse(dir1.begin(), dir1.end());

  swap(g,gr);
  used = vector<bool>(n);
  for(int i: dir1) {
    dir = vector<int>();
    dfs(dfs,i);
    if (dir.size() == 1) continue;
    cout << dir.size() << endl;
    for(auto v: dir) cout << v+1 << " ";
    break;
  }
  return 0;
}

D - Grid Ice Floor

dfs で到達可能なすべてのマス x 4 方向への移動 を調べる。通常の dfs に 4 方向の移動を拡張した形。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

const vector<pair<int,int>> moves = { {-1,0}, {0,1}, {1,0}, {0,-1} };

int main() {
  int n,m; cin >> n >> m;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  // [i][j][k] := i,j マスで k 方向 への移動を試したかどうか
  vector seen(n,vector(m,vector<bool>(4)));
  // [i][j] := i,j マスを通過したかどうか
  vector visited(n,vector<int>(m));

  auto dfs = [&](auto self, int x, int y) -> void {
    REP(k,4) {
      if (seen[x][y][k]) continue;
      seen[x][y][k] = true;
      auto [dx,dy] = moves[k];
      int nx = x, ny = y;
      // 岩にぶつかるまで進む
      while(s[nx+dx][ny+dy] == '.') {
        nx += dx; ny += dy;
        visited[nx][ny] = 1;
      }
      self(self,nx,ny);
    }
  };

  visited[1][1] = true;
  dfs(dfs,1,1);
  int ans = 0;
  REP(i,n) REP(j,m) ans += visited[i][j];
  cout << ans << endl;
  return 0;
}

E - Defect-free Squares

DP。 dp[i][j] := i,j マスまでで、i,j マスを含んで作れる穴のない正方形の総数。 i,j マスが穴でない場合、左、左上、上のマスで min を取ったもの + 1(i,jマスのみで正方形を作る分) となる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int h,w,n; cin >> h >> w >> n;
  vector g(h,vector<bool>(w));
  REP(i,n) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a][b] = true;
  }

  // dp[i][j] := i,j マスまでで、i,j を含んで作れる穴のない正方形の総数
  vector dp(h,vector<ll>(w));
  REP(i,h) REP(j,w) {
    if (g[i][j]) continue;
    dp[i][j] = 1;
    if (i-1 >= 0 && j-1 >= 0) dp[i][j] += min({ dp[i-1][j-1], dp[i-1][j], dp[i][j-1] });
  }

  ll ans = 0;
  REP(i,h) REP(j,w) ans += dp[i][j];
  cout << ans << endl;
  return 0;
}

今回の成績

tic40さんのトヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)での成績：1472位
パフォーマンス：1357相当
レーティング：1189→1207 (+18) :)
Highestを更新し、4 級になりました！
#AtCoder #トヨタ自動車プログラミングコンテスト2023#4(ABC311) https://atcoder.jp/users/tic40/history/share/abc311?lang=ja 

AtCoder abc310 参加メモ

freee Programming Contest 2023（AtCoder Beginner Contest 310） - AtCoder

B - Strictly Superior

全探索。p[i] == p[j] の場合など条件がややこしいため注意する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<int> p(n),c(n);
  vector f(n,vector<bool>(m));
  REP(i,n) {
    cin >> p[i] >> c[i];
    REP(j,c[i]) {
      int x; cin >> x; x--;
      f[i][x] = true;
    }
  }

  REP(i,n) REP(j,n) {
    if (i == j) continue;
    if (p[i] > p[j]) continue;
    bool ok = true;
    int cnt = 0; // i のみにある機能の個数
    REP(k,m) {
      if (f[j][k] && !f[i][k]) ok = false;
      if (f[i][k] && !f[j][k]) cnt++;
    }
    if (p[i] == p[j]) ok = ok && cnt > 0;
    if (ok) { cout << "Yes" << endl; return 0; }
  }

  cout << "No" << endl;
  return 0;
}

C - Reversible

set を使って通常と逆順両方がまだ集合になかったら追加する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  unordered_set<string> st;

  REP(i,n) {
    string s; cin >> s;
    if (st.count(s)) continue;
    reverse(s.begin(),s.end());
    if (st.count(s)) continue;
    st.insert(s);
  }

  cout << st.size() << endl;
  return 0;
}

D - Peaceful Teams

DFS。

チームは区別されないので、まだ誰もいないチームに人を入れるときには、一つのチームだけで良い(この場合どの空のチームに入れても区別されないため)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,t,m; cin >> n >> t >> m;
  vector c(n,vector<int>(n)); // c[i][j] := i,j の相性が悪いかどうか
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    c[a][b] = c[b][a] = 1;
  }

  vector g(t,vector<int>()); // チームに所属しているメンバー情報
  auto dfs = [&](auto self, int i) -> int {
    if (i == n) {
      REP(j,t) if (g[j].size() == 0) return 0;
      return 1;
    }

    int res = 0;
    REP(j,t) {
      bool ok = true; // j チームに i を追加可能かどうか
      for(auto v: g[j]) if (c[i][v]) ok = false;
      if (!ok) continue;

      g[j].push_back(i);
      res += self(self,i+1);
      g[j].pop_back();
      if (g[j].size() == 0) break;
    }
    return res;
  };

  cout << dfs(dfs, 0) << endl;
  return 0;
}

今回の成績

tic40さんのfreee プログラミングコンテスト2023（AtCoder Beginner Contest 310）での成績：1772位
パフォーマンス：1315相当
レーティング：1174→1189 (+15) :)
Highestを更新しました！
#AtCoder #freeeプログラミングコンテスト2023（ABC310） https://atcoder.jp/users/tic40/history/share/abc310?lang=ja 

AtCoder abc309 参加メモ

Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder

B - Rotate

愚直に時計回りへずらしていった。もっと簡単な方法あるかな。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<string> a(n);
  REP(i,n) cin >> a[i];

  auto b = a;
  REP(j,n-1) b[0][j+1] = a[0][j];
  REP(i,n-1) b[i+1][n-1] = a[i][n-1];
  for(int j = n-1; j > 0; j--) b[n-1][j-1] = a[n-1][j];
  for(int i = n-1; i > 0; i--) b[i-1][0] = a[i][0];

  REP(i,n) {
    REP(j,n) cout << b[i][j];
    cout << endl;
  }
  return 0;
}

C - Medicine

累積和で何日目に何錠飲むかを求めて、k 以下になった日が答え。

$ a_i $ の制約が大きいため map で座標圧縮した。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,k; cin >> n >> k;
  map<int,ll> mp;
  REP(i,n) {
    int a,b; cin >> a >> b;
    mp[1] += b; mp[1+a] -= b;
  }

  ll p = 0;
  for(auto [i,v]: mp) {
    mp[i] += p;
    if (mp[i] <= k) { cout << i << endl; return 0; }
    p = mp[i];
  }

  return 0;
}

D - Add One Edge

頂点1 と 頂点 N1+N2 からそれぞれ bfs で最短経路を求めて、それぞれの最大の距離の地点同士を連結させると d が最大値となる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
const int INF = numeric_limits<int>::max();

int main() {
  int n1,n2,m; cin >> n1 >> n2 >> m;
  int n = n1+n2;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  auto bfs = [&](int i) {
    vector<int> dist(n,INF);
    queue<int> q;
    q.push(i);
    dist[i] = 0;
    while(q.size()) {
      int v = q.front(); q.pop();
      for(auto nv: g[v]) {
        if (dist[nv] != INF) continue;
        q.push(nv);
        dist[nv] = dist[v]+1;
      }
    }
    return dist;
  };

  auto d1 = bfs(0);
  auto d2 = bfs(n-1);
  int ans1 = *max_element(d1.begin(), d1.begin() + n1);
  int ans2 = *max_element(d2.begin() + n1, d2.end());
  int ans = ans1 + ans2 + 1;
  cout << ans << endl;
  return 0;
}
}

E - Family and Insurance

親から子へ dfs する。 引数に最大何世代先まで補償できるかを持っておき、今の人が保険に入っていたら親からの補償と自身の保険の補償との最大の世代数を次へ渡していけばいい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector g(n,vector<int>());
  for(int i = 1; i < n; i++) {
    int p; cin >> p; p--;
    g[p].push_back(i);
  }

  vector<int> d(n);
  REP(i,m) {
    int x,y; cin >> x >> y; x--;
    d[x] = max(d[x],y);
  }

  auto bfs = [&](auto self, int i, int p) -> int {
    int res = 0;
    if (p > 0 || d[i] > 0) res++;
    int np = max(p-1,d[i]);
    for(auto v: g[i]) res += self(self,v,np);
    return res;
  };

  cout << bfs(bfs,0,0) << endl;
  return 0;
}

今回の成績

tic40さんのデンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）での成績：1541位
パフォーマンス：1285相当
レーティング：1161→1174 (+13) :)
Highestを更新しました！
#AtCoder #デンソークリエイトプログラミングコンテスト2023（ABC309） https://atcoder.jp/users/tic40/history/share/abc309?lang=ja 

AtCoder abc308 参加メモ

AtCoder Beginner Contest 308 - AtCoder

B - Default Price

D のいずれとも異なる色の皿の料理は一皿 $ P_0 $ 円ということに注意する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n,m; cin >> n >> m;
  vector<string> c(n),d(m);
  vector<int> p(m+1);
  REP(i,n) cin >> c[i];
  REP(i,m) cin >> d[i];
  REP(i,m+1) cin >> p[i];

  map<string,int> mp;
  REP(i,m) mp[d[i]] = p[i+1];

  int ans = 0;
  REP(i,n) ans += mp.count(c[i]) ? mp[c[i]] : p[0];
  cout << ans << endl;
  return 0;
}

C - Standings

double でそのまま計算すると誤差で wa となる。long double を使えば通るが、解説 のように分母を取って整数で比較したほうが安全かもしれない

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<pair<long double,int>> vp;
  REP(i,n) {
    long double a,b; cin >> a >> b;
    long double r = a / (a+b);
    vp.emplace_back(r,-i);
  }
  sort(vp.rbegin(),vp.rend());
  for(auto [_,v]: vp) cout << (-v+1) << " ";
  return 0;
}

D - Snuke Maze

H,W <= 500 という制約のため DFS で間に合う

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

const vector<pair<int, int>> moves = { {1,0},{0,1},{-1,0},{0,-1} };
const string target = "snuke";
const int sz = 5;

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  vector visited(h,vector<bool>(w));
  auto dfs = [&](auto self, int x, int y, int i) -> void {
    if (s[x][y] != target[i % sz]) return;
    if (x == h-1 && y == w-1) { cout << "Yes" << endl; exit(0); }

    visited[x][y] = true;
    for(auto [dx,dy]: moves) {
      int nx = x + dx, ny = y + dy;
      if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
      if (visited[nx][ny]) continue;
      self(self,nx,ny,i+1);
    }
  };

  dfs(dfs,0,0,0);
  cout << "No" << endl;
  return 0;
}

E - MEX

数は3通りしかない。頭から見て言って M, ME について Mの数字 x Eの数字 の組み合わせでそれぞれ何通りあるか記録していく。

X が来たときは上記で記録しておいた ME に対応する数字と X の数字で mex を取り、 mex * MEの合計数 を答えに加算していく

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  string s; cin >> s;

  auto mex = [](int x, int y, int z) {
    vector<bool> mex(3);
    mex[x] = mex[y] = mex[z] = true;
    REP(i,3) if (!mex[i]) return i;
    return 3;
  };

  vector<int> m(3);
  vector e(3,vector<ll>(3));
  ll ans = 0;
  REP(i,n) {
    if (s[i] == 'M') m[a[i]]++;
    if (s[i] == 'E') REP(j,3) e[j][a[i]] += m[j];
    if (s[i] == 'X') {
      REP(j,3) REP(k,3) ans += mex(j,k,a[i]) * e[j][k];
    }
  }
  cout << ans << endl;
  return 0;
}

F - Vouchers

値引き金額が最も大きいクーポンから優先して使っていけば最も合計金額を小さくできる。

値引き金額が最も大きいクーポンから順に、二分探索でクーポンを使うことができる最も価格の低い商品を貪欲に選んでいけばよい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
using P = pair<int,int>;

int main() {
  int n,m; cin >> n >> m;
  vector<int> p(n),l(m),d(m);
  multiset<int> st;
  REP(i,n) { cin >> p[i]; st.insert(p[i]); }
  REP(i,m) cin >> l[i];
  REP(i,m) cin >> d[i];

  vector<P> pc(m);
  REP(i,m) pc[i] = {d[i],l[i]};
  sort(pc.rbegin(),pc.rend());

  ll ans = accumulate(p.begin(),p.end(),0LL);
  for(auto [nd,nl]: pc) {
    auto it = st.lower_bound(nl);
    if (it == st.end()) continue;
    ans -= nd;
    st.erase(it);
  }
  cout << ans << endl;
  return 0;
}

今回の成績

F 問題まで解けたけどもそれでも 3 桁位は厳しかった。今回は全体的に簡単だったかもしれない

tic40さんのCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)での成績：1117位
パフォーマンス：1446相当
レーティング：1124→1161 (+37) :)
Highestを更新しました！
#AtCoder #CodeQUEEN2023予選(ABC308) https://atcoder.jp/users/tic40/history/share/abc308?lang=ja 

AtCoder abc307 参加メモ

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307) - AtCoder

B - racecar

全探索

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  auto f = [](string s) {
    string t = s;
    reverse(t.begin(),t.end());
    return t == s;
  };

  bool ok = false;
  REP(i,n) REP(j,n) if (i != j && f(s[i]+s[j])) ok = true;
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Ideal Sheet

10 x 10 マスという制約のため、シート A, B の平行移動を全探索しても間に合う。

透明マスは関係ないので、黒マスだけを比較すれば良い。A, B の黒マスの集合が X の黒マス集合と一致すれば Yes。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;

int main() {
  vector b(3,vector<P>());
  REP(i,3) {
    int h,w; cin >> h >> w;
    REP(j,h) {
      string s; cin >> s;
      REP(k,w) if (s[k] == '#') b[i].emplace_back(j,k);
    }
  }

  set<P> ideal;
  for(auto [x,y]: b[2]) ideal.emplace(x,y);

  REP(i,20) REP(j,20) REP(k,20) REP(l,20) {
    set<P> st;
    for(auto [x,y]: b[0]) st.emplace(x+i-10,y+j-10);
    for(auto [x,y]: b[1]) st.emplace(x+k-10,y+l-10);
    if (st == ideal) { cout << "Yes" << endl; return 0; }
  }
  cout << "No" << endl;
  return 0;
}

D - Mismatched Parentheses

stack で括弧マッチングを管理する。 括弧が閉じていたら開始と終了位置メモしておき、最終的に累積和で括弧が閉じている範囲を集計する。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<char,int>;

int main() {
  int n; cin >> n;
  string s; cin >> s;

  stack<P> st;
  vector<int> sum(n+1);
  REP(i,n) {
    if (s[i] == '(') st.emplace('(',i);
    if (s[i] == ')' && st.size()) {
      auto [c,idx] = st.top();
      if (c == '(') {
        st.pop();
        sum[idx]++;
        sum[i+1]--;
      }
    }
  }

  REP(i,n) sum[i+1] += sum[i];
  REP(i,n) if (sum[i] == 0) cout << s[i];
  return 0;
}

AtCoder abc305 参加メモ

KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） - AtCoder

B - ABCDEFG

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  char p,q; cin >> p >> q;
  const int n = 7;
  vector<int> a = {0,3,1,4,1,5,9};
  vector<int> s(n+1);
  REP(i,n) s[i+1] = s[i] + a[i];
  cout << abs(s[p-'A'+1] - s[q-'A'+1]) << endl;
  return 0;
}

C - Snuke the Cookie Picker

長方形の上下左右の端は必ず存在するのでそれを探す。見つけたらその境界内を探索してクッキーが置かれていないところが答え

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int h,w; cin >> h >> w;
  vector<string> s(h);
  REP(i,h) cin >> s[i];

  // l: 左端, r: 右端, b: 下端, t: 上端
  int l = 1e9, r = 0;
  int b = 0, t = 1e9;
  REP(i,h) REP(j,w) {
    if (s[i][j] != '#') continue;
    l = min(l,j);
    r = max(r,j);
    t = min(t,i);
    b = max(b,i);
  }

  for(int i = t; i <= b; i++) for(int j = l; j <= r; j++) {
    if (s[i][j] == '#') continue;
    cout << i+1 << " " << j+1 << endl;
    return 0;
  }
}

D - Sleep Log

二分探索 + 累積和 + α。

クエリの L と R で二分探索して累積和でざっくり寝ていた時間が求まる。そこから、L/R 両端の半端な部分を足し引きして正確な時間を求める。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;

int main() {
  int n; cin >> n;
  vector<ll> a(n);
  REP(i,n) cin >> a[i];
  vector<ll> s(n); // 寝ていた時間の累積和
  for(int i = 2; i < n; i++) {
    s[i] += s[i-1];
    if (i % 2 == 0) s[i] += a[i] - a[i-1];
  }

  int q; cin >> q;
  REP(_,q) {
    ll l,r; cin >> l >> r;
    auto idxl = lower_bound(a.begin(),a.end(),l) - a.begin();
    auto idxr = upper_bound(a.begin(),a.end(),r) - a.begin() - 1;
    ll ans = s[idxr] - s[idxl];
    if (idxl % 2 == 0) ans += a[idxl] - l;
    if (idxr % 2 == 1) ans += r - a[idxr];
    cout << ans << endl;
  }
  return 0;
}

E - Art Gallery on Graph

体力の多い警備員がいる頂点から、その警備員の体力 h 分の距離までを探索していく。 訪問した頂点が警備員の体力 h - 距離 より大きい値で訪問済みの場合は探索する必要がないので打ち切ってよい。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;

int main() {
  int n,m,k; cin >> n >> m >> k;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<P> pa(k);
  REP(i,k) {
    int p,h; cin >> p >> h;
    p--;
    pa[i] = {h,p};
  }
  sort(pa.rbegin(),pa.rend()); // h の多い順にソート
  vector<int> mx(n,-1); // mx[i] := 頂点 i に訪問したときの 「警備員の体力 h - 頂点 i までの距離」 の最大値

  auto bfs = [&](int h, int i) -> void {
    queue<P> q;
    q.emplace(i,h);
    while(q.size()) {
      auto [ni,nh] = q.front(); q.pop();
      if (mx[ni] >= nh) continue;
      mx[ni] = nh;
      for(auto nv: g[ni]) q.emplace(nv,nh-1);
    }
  };

  for(auto [h,p]: pa) bfs(h,p);
  vector<int> ans;
  REP(i,n) if (mx[i] != -1) ans.push_back(i+1);
  cout << ans.size() << endl;
  for(int v: ans) cout << v << " ";
  return 0;
}