업다운 디펜스 #1

July 8, 2023

업다운 디펜스

업다운 디펜스란 백준에서 Solved.ac 기준으로 특정 난이도의 문제를 랜덤으로 풀고,

$30$분 안에 그 문제를 해결한다면 한 티어 높은 문제로, 그렇지 못한다면 한 티어 낮은 문제로 이동하는 문제풀이법이다.

문제는 Solved.ac에서 *g4 s#50.. -@$me 와 같이 난이도 및 푼 사람이 50명 이상인 문제 중 고르고 랜덤으로 섞어서 가장 먼저 나오는 것을 푼다.
괄호 안에 +는 틀린 횟수이다.
그 뒤에 따라 붙는건 분:초 이다.
초록색은 30분안에 해결을 했음을 나타내고, 빨간색은 못풀었음을 나타낸다.
성공한 예시 - [+2] 15:22
실패한 예시 - [+7] 42:50
$30$분이 지나도 풀이를 못떠올려서 해설을 찾아봐서 풀었을 때 - [-]

간만에 시작해보도록하자.

[Gold 5] BOJ 1553 - 도미노 찾기 [+] 08:40

BOJ 1553 - 도미노 찾기

단순 백트랙킹 문제였다.

void solve() {  
   vs b(8);  
   fv(b);  
  
   vvi used(7, vi(7));  
   int ans = 0;  
   vvi c(8, vi(7));  
   function<void(int)> fn = [&](int i) -> void {  
      debug(i);  
      if (i == 56) {  
         ans++;  
         return;  
      }  
      int y = i / 7, x = i % 7;  
      if (c[y][x]) {  
         fn(i + 1);  
         return;  
      }  
  
      int m = b[y][x] - '0';  
      if (x != 6 && !c[y][x + 1]) {  
         int j = b[y][x + 1] - '0';  
         if (!used[m][j]) {  
            used[m][j] = used[j][m] = 1;  
            c[y][x] = c[y][x + 1] = 1;  
            fn(i + 1);  
            c[y][x] = c[y][x + 1] = 0;  
            used[m][j] = used[j][m] = 0;  
         }  
      }  
      if (y != 7 && !c[y + 1][x]) {  
         int j = b[y + 1][x] - '0';  
         if (!used[m][j]) {  
            used[m][j] = used[j][m] = 1;  
            c[y][x] = c[y + 1][x] = 1;  
            fn(i + 1);  
            c[y][x] = c[y + 1][x] = 0;  
            used[m][j] = used[j][m] = 0;  
         }  
      }  
   };  
   fn(0);  
   cout << ans;  
}

[Gold 4] BOJ 23031 - 으어어… 에이쁠 주세요.. [+] 10:50

BOJ 23031

시뮬레이션 문제이다.

문제에서 하라는대로 하면 된다.

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};  
const int dy8[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dx8[] = {0, 1, 1, 1, 0, -1, -1, -1};  
struct zombie {  
   int y, x, d;  
};  
  
void solve() {  
   int n;  
   cin >> n;  
   string s;  
   cin >> s;  
   vs b(n);  
   fv(b);  
  
   vector<zombie> z;  
   vvi on(n, vi(n));  
   for (int y = 0; y < n; y++)  
      for (int x = 0; x < n; x++) {  
         if (b[y][x] == 'Z') {  
            z.pb({y, x, 2});  
         }  
      }  
  
   int d = 2, y = 0, x = 0;  
  
   auto in = [&](int y, int x) {  
      return y >= 0 && y < n && x >= 0 && x < n;  
   };  
  
   for (char c: s) {  
      if (c == 'L') {  
         d = md(4, d - 1);  
      }  
      if (c == 'R') {  
         d = md(4, d + 1);  
      }  
      if (c == 'F') {  
         int ny = y + dy[d], nx = x + dx[d];  
         if (in(ny, nx)) {  
            y = ny, x = nx;  
  
            if (b[ny][nx] == 'S') {  
               on[ny][nx] = 1;  
               for (int d8 = 0; d8 < 8; d8++) {  
                  int nny = y + dy8[d8];  
                  int nnx = x + dx8[d8];  
                  if (in(nny, nnx))  
                     on[nny][nnx] = 1;  
               }  
            }  
  
            for (auto &[zy, zx, zd]: z) {  
               if (!on[zy][zx] && zy == y && zx == x) {  
                  cout << "Aaaaaah!";  
                  return;  
               }  
            }  
         }  
      }  
  
      int oy = y, ox = x;  
      for (auto &[y, x, d]: z) {  
         int ny = y + dy[d], nx = x + dx[d];  
         if (!in(ny, nx)) {  
            d = md(4, d + 2);  
         } else {  
            y = ny, x = nx;  
         }  
         if (y == oy && x == ox && !on[y][x] && b[y][x] != 'S') {  
            cout << "Aaaaaah!";  
            return;  
         }  
      }  
   }  
   cout << "Phew...";  
}

[Gold 3] BOJ 3806 - S를 T로 [+7] 32:57

BOJ 3806

$10$분만에 제출한 코드가 정답이였는데

내 테스트케이스 문제 템플릿에 #이 들어간 Case #1: 3 처럼 출력하게 되어있어서 계속틀렸다.

그냥 처음 제출에서 # 하나 지우고 제출하니 통과되었다.

해답은 다음과 같다.

$0_s$ 를 $0$이 $s$에 있는 횟수처럼 쓰겠다.

$0$은 언제나 $1$로 바꾸지만 $1 \to 0$ 은 안된다는 점을 관찰한다.

그럼 안되는 경우는 $0_t > 0_s + ?_s$ 임을 알 수 있다.

모든 ?를 $0$으로 바꿔도 $t$에 있는 $0$개수만큼이 안나오기 때문이다.

그 외의 경우에는 항상 만들 수 있다.

일단 ? 는 제쳐두고 $1$번 연산을 얼마나 써야하는지 생각해보자.

$\text{Max}(0, 1_t-1_s-?_s)$ 만큼은 항상 $1$번 연산을 써줘야 하므로 $s_i=0$ 그리고 $t_i=1$ 인 저만큼에 대해서 $1$번 연산을 해주고 시작한다.

그 다음 $?_s$ 만큼 정답에 더해주고, $s_i \neq t_i$ 인 것의 개수를 $s_i=0$ 이라면 $u_0$, $s_i=1$ 이라면 $u_1$ 이라고 했을 때,

$\text{Min}(u_0,u_1)$ 만큼 정답에 더해준다. 3번 연산을 최대한 쓰는것이 이득이기 때문에 서로 교환할 수 있는것들을 모두 교환해준다.

이제 $u_0$과 $u_1$ 중 더 큰것에서 작은것을 뺀 만큼 정답에 더해주면 된다.

왜냐면 현재까지 $s_i \neq t_i$ 인 것들은 항상 ? 중에서 그걸로 바꿔서 교환해줘서 맞춰줘야하는데,

?의 개수만큼 이미 정답에 더해두었고 남는 ?들을 적절히 바꿔서 교체하면 결국 교체하는 비용만 들기 때문이다.

void solve() {  
   string s, t;  
   cin >> s >> t;  
   int n = sz(s);  
  
   int one_t = cntt(t, '1'), zero_t = n - one_t, one_s = cntt(s, '1'), zero_s = n - one_s;  
  
   int q = cntt(s, '?');  
   if (zero_t > zero_s + q) {  
      cout << -1 << endl;  
      return;  
   }  
   int ans = q;  
   int op1 = max(0, one_t - q - one_s);  
   for (int i = 0; i < n; i++) {  
      if (s[i] == '0' && t[i] == '1' && op1) {  
         ans++;  
         s[i] = '1';  
         op1--;  
      }  
   }  
  
   vi u0, u1;  
   for (int i = 0; i < n; i++) {  
      if ((s[i] == '0') && t[i] == '1') u0.pb(i);  
      if ((s[i] == '1') && t[i] == '0') u1.pb(i);  
   }  
   for (int i = 0; i < min(sz(u0), sz(u1)); i++) {  
      ans++;  
      swap(s[u0[i]], s[u1[i]]);  
   }  
   ans += sz(u0) - min(sz(u0), sz(u1)) + sz(u1) - min(sz(u0), sz(u1));  
   cout << ans << endl;  
}  
  
signed main() {  
   fastio  
   int tt;  
   cin >> tt;  
   for (int t = 1; t <= tt; t++) {  
      cout << "Case " << t << ": ";  
      solve();  
   }  
   return 0;  
}

[Gold 4] BOJ 25559 - 패스 [+2] 14:57

BOJ 25559

$1$번 사람은 항상 $N$을 패스해야 한다.

왜냐면 다른 사람이 $N$을 쓴다면 자기 자신으로 돌아오게 되고 그럼 그 사람은 그 사람으로 왔을 때의 패스와 자기 자신의 패스에 의해 $2$번 이상 패스를 받는것이 되기 때문이다.

이외에는 짝수라면 항상 가능하다.

$l, r$ 을 관리하며 $l=1,r=N$ 으로 두고 한 칸씩 좁혀가며 계속 패스를 하는 방식으로 하면 된다.

void solve() {  
   int n;  
   cin >> n;  
  
   int cur = 0;  
   vi used(n + 1);  
   used[n] = 1;  
   vi ans;  
   ans.pb(n);  
   for (int i = n - 1, l = 0, r = n - 1; i >= 1; i--) {  
      if (cur == l) {  
         int move = r - l;  
         if (used[move]) {  
            cout << -1;  
            return;  
         }  
         used[move] = 1;  
         ans.pb(move);  
         cur = r;  
         l++;  
      } else {  
         int move = (l + n - r);  
         if (used[move]) {  
            cout << -1;  
            return;  
         }  
         used[move] = 1;  
         ans.pb(move);  
         cur = l;  
         r--;  
      }  
   }  
   for (int i: ans)cout << i << ' ';  
}

[Gold 3] BOJ 20160 - 야쿠르트 아줌마 야쿠르트 주세요 [+2] 12:30

BOJ 20160

다익스트라를 $10$번 돌려서 각 지점에 가장 늦게 도착하는 거리를 모두 기록해둔다음 자신의 시작 위치에서도 다익스트라를 돌려 갈 수 있는 지점 중 가장 작은 번호를 출력하면 된다.

const int inf = 2e15;  
void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<vector<pi>> edges(n);  
   for (int i = 0, u, v, w; i < m; i++) {  
      cin >> u >> v >> w, u--, v--;  
      edges[u].pb({v, w});  
      edges[v].pb({u, w});  
   }  
   vi t(10);  
   fv(t);  
   for (int &i: t)i--;  
   int s;  
   cin >> s, s--;  
  
   auto get_dist = [&](int start) {  
      vi ret(n, inf);  
      ret[start] = 0;  
      priority_queue<pi, vector<pi>, greater<>> q;  
      q.push({0, start});  
      while (sz(q)) {  
         auto [cur_d, cur] = q.top();  
         q.pop();  
         if (ret[cur] < cur_d) continue;  
         for (auto &[to, w]: edges[cur]) {  
            if (ret[to] > ret[cur] + w) {  
               ret[to] = ret[cur] + w;  
               q.push({ret[to], to});  
            }  
         }  
      }  
      return ret;  
   };  
   vi dist_ya(n, -1);  
  
   dist_ya[t[0]] = 0;  
   int cur_dist = 0;  
   for (int i = 0; i < 10;) {  
      auto d = get_dist(t[i]);  
      int nxt = -1;  
      for (int j = i + 1; j < 10; j++) {  
         if (d[t[j]] == inf) continue;  
         else {  
            nxt = j;  
            break;  
         }  
      }  
      if (nxt == -1) break;  
      maxa(dist_ya[t[nxt]], cur_dist + d[t[nxt]]);  
      cur_dist += d[t[nxt]];  
      i = nxt;  
   }  
  
   auto d = get_dist(s);  
   int ans = inf;  
   for (int i = 0; i < 10; i++) {  
      if (dist_ya[t[i]] != -1 && d[t[i]] != inf && d[t[i]] <= dist_ya[t[i]]) {  
         mina(ans, t[i]);  
      }  
   }  
   if (ans == inf) cout << -1;  
   else cout << ans + 1;  
}

[Gold 2] BOJ 5625 - 페스트리 [+] 06:04

BOJ 5625

각 삼각형마다 세 개의 점 중 $x,y$ 들이 가장 작은것과 가장 큰것을 미리 파싱한 후 쿼리로 들어오는 좌표에 걸치는 것의 개수를 세면 된다.

누적합 배열 두개(x,y니까 총 4개)를 준비해서 하나는 시작지점, 하나는 끝지점에 1씩 더해놔주자.

$v$ 라는 값이 있을 때 $0 \sim v$ 에 끝지점이 있는 것과 $v \sim \infty$에 시작지점이 있는것의 개수를 각각 $a,b$ 라 한다면 $n-a-b$ 가 정답이다.

// region FENWICK  
template<class T>  
struct fenwick {  
   int n;  
   vector<T> tree;  
   fenwick(int n) : n(n) { tree.resize(n + 1); }  
   T sum(int i) {  
      T ret = 0;  
      for (; i; i -= i & -i) ret += tree[i];  
      return ret;  
   }  
   void update(int i, T x) { for (i++; i <= n; i += i & -i) tree[i] += x; }  
   T query(int l, int r) { return l > r ? 0 : sum(r + 1) - sum(l); }  
};  
// endregion  
  
void solve() {  
   int n;  
   cin >> n;  
   fenwick<int> X_s(1000005), X_e(1000005), Y_s(1000005), Y_e(1000005);  
   for (int i = 0; i < n; i++) {  
      vector<pi> p(3);  
      for (auto &[x, y]: p) cin >> x >> y;  
      int mn_x = 2e9, mx_x = -2e9;  
      int mn_y = 2e9, mx_y = -2e9;  
      for (auto &[x, y]: p) {  
         mina(mn_x, x);  
         maxa(mx_x, x);  
         mina(mn_y, y);  
         maxa(mx_y, y);  
      }  
      X_s.update(mn_x, 1);  
      X_e.update(mx_x, 1);  
      Y_s.update(mn_y, 1);  
      Y_e.update(mx_y, 1);  
   }  
   int q;  
   cin >> q;  
   while (q--) {  
      string dir, dd;  
      int v;  
      cin >> dir >> dd >> v;  
      if (dir == "x") {  
         int left = X_e.query(0, v);  
         int right = X_s.query(v, 1000004);  
         cout << n - left - right << endl;  
      } else {  
         int left = Y_e.query(0, v);  
         int right = Y_s.query(v, 1000004);  
         cout << n - left - right << endl;  
      }  
   }  
}

[Gold 1] BOJ 10541 - 싸리와 버드의 피라미드 [+1] 23:40

BOJ 10541

수학적인 누적합문제인데 정확한 구현력이 필요했다.

각 알파벳별로 구간합 배열을 모두 만들어두자.

$a=1$ 은 따로 처리하고$a$ 번 째 줄 이전에 $s_0$ 이 가장 마지막으로 나오는 위치를 얻어내자. $O(1)$로 가능하다.

이제 그만큼 prefix가 잘린채로 $a$ 번째 줄에 진입한 후에 뒤에 suffix중 $c$가 나오는 개수를 더해준다.

suffix가 $a$번째 줄을 넘어가는 경우도 잘 처리해주자.

그러면 이제 $a$ 줄에서 남은 개수가 $k$라고 한다면 $\left\lfloor \dfrac{k}{\vert s \vert} \right\rfloor$ 만큼은 모든 단어를 다 포함해주는 것이 된다.

그만큼 $s_0$ 의 위치를 또 이동시킨다음 또 포함되는 prefix 부분에서 $c$의 개수만 더해주면 된다.

int128 로 처리해주도록 하자.

void solve() {  
   int n;  
   cin >> n;  
   string s;  
   cin >> s;  
   int m = sz(s);  
   // 단어 하나당 몇개씩 있는지  
   vector<vector<signed>> psum(26, vector<signed>(m + 1));  
   for (int i = 0; i < m; i++) {  
      for (int j = 0; j < 26; j++) {  
         psum[j][i + 1] = psum[j][i] + ((s[i] - 'A') == j);  
      }  
   }  
   auto qry = [&](int i, int l, int r) -> int {  
      if (l > r) return 0;  
      return psum[i][r + 1] - psum[i][l];  
   };  
   int k;  
   cin >> k;  
   auto sum = [&](int x) { return x * (x + 1) / 2; };  
   while (k--) {  
      string _c;  
      int a, c;  
      cin >> a >> _c;  
      c = _c[0] - 'A';  
  
      if (a == 1) {  
         if (s[0] - 'A' == c) cout << 1 << endl;  
         else cout << 0 << endl;  
         continue;  
      }  
  
      int last_first = sum(a - 1) / m * m + 1;  
      if (last_first == sum(a - 1) + 1) last_first -= m;  
      assert(last_first >= 1);  
  
      int ret = 0;  
      int prefix_len = sum(a - 1) - last_first + 1;  
      int remain_len = m - prefix_len;  
  
      if (remain_len > a) {  
         int cut = remain_len - a;  
         cout << qry(c, prefix_len, m - 1 - cut) << endl;  
         continue;  
      }  
      ret = qry(c, prefix_len, m - 1);  
      last_first += m;  
  
      int remain_in_row = sum(a) - last_first + 1;  
      int q = remain_in_row / m;  
      ret += qry(c, 0, m - 1) * q;  
      last_first += q * m;  
  
      prefix_len = sum(a) - last_first + 1;  
      if (prefix_len >= 1) {  
         ret += qry(c, 0, prefix_len - 1);  
      }  
      cout << ret << endl;  
   }  
}

[Platinum 5] BOJ 20158 - 사장님 달려가고 있습니다 [+] 09:35

BOJ 20158

정답비율이 굉장히 낮은 까다로운 BFS였는데 운좋게 한 번에 맞았다.

$D[i][j][k]$ 를 $(i, j)$ 에 마지막으로 이동한 방향이 $k$ 일 때 최단거리라고 하자.

그럼 4방향을 모두 보며 $k$가 아닌 방향으로만 쭉 나아가면서 간단히 조건을 검사하면 된다.

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};  
int dist[101][101][5];  
const int inf = 0x3f3f3f3f;  
void solve() {  
   int n;  
   cin >> n;  
   vvi b(n, vi(n));  
   fv2(b);  
   memset(dist, inf, sizeof dist);  
   queue<array<int, 3>> q;  
   q.push({0, 0, 4});  
   dist[0][0][4] = 0;  
   auto in = [&](int y, int x) {  
      return y >= 0 && y < n && x >= 0 && x < n;  
   };  
   while (sz(q)) {  
      auto [y, x, no] = q.front();  
      int cur_d = dist[y][x][no];  
      q.pop();  
      for (int d = 0; d < 4; d++) {  
         if (d == no) continue;  
         int speed = 1;  
  
         int dt = 1;  
         for (int k = 1, nxt = 1;; k++) {  
            int ny = y + dy[d] * k;  
            int nx = x + dx[d] * k;  
  
            if (!in(ny, nx)) break;  
  
            if (b[ny][nx]) {  
               if (cur_d + (dt - (k != nxt)) >= b[ny][nx]) {  
                  break;  
               }  
            }  
  
            if (k == nxt) {  
  
               if (dist[ny][nx][d] > cur_d + dt) {  
                  dist[ny][nx][d] = cur_d + dt;  
                  q.push({ny, nx, d});  
               }  
  
               speed++;  
               nxt += speed;  
               dt++;  
            }  
         }  
      }  
   }  
   if (n == 1) {  
      cout << 0;  
      return;  
   }  
   int ans = inf;  
   for (int i = 0; i < 4; i++) {  
      mina(ans, dist[n - 1][n - 1][i]);  
   }  
   if (ans == inf) cout << "Fired";  
   else cout << ans;  
}

업다운 디펜스 #1

업다운 디펜스

[Gold 5] BOJ 1553 - 도미노 찾기 [+] 08:40

[Gold 4] BOJ 23031 - 으어어… 에이쁠 주세요.. [+] 10:50

[Gold 3] BOJ 3806 - S를 T로 [+7] 32:57

[Gold 4] BOJ 25559 - 패스 [+2] 14:57

[Gold 3] BOJ 20160 - 야쿠르트 아줌마 야쿠르트 주세요 [+2] 12:30

[Gold 2] BOJ 5625 - 페스트리 [+] 06:04

[Gold 1] BOJ 10541 - 싸리와 버드의 피라미드 [+1] 23:40

[Platinum 5] BOJ 20158 - 사장님 달려가고 있습니다 [+] 09:35

Comments

You may also enjoy

DaisyUI 공부 및 웹사이트에 적용

모집병 실시간 지원현황 웹사이트 개발

D3 공부, TailwindCss

241203 일상 - Next 복습