ABC395の振り返り

1ヶ月間、脳働いてません

A問題(diff:14)

今度はAでペナを食らうという…
シュミレーションするだけです。
計算量は $O(N)$ です。
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, a;
  cin >> N >> a;
  for(int i = 0; i < N - 1; i++) {
    int A;
    cin >> A;
    if(A <= a) {
      cout << "No" << endl;
      return 0;
    }
    a = A;
  }
  cout << "Yes" << endl;
}

AC時間:4:19

B問題(diff:72)

B問題にグリッドが来るとやる気が失せます…(実際C問題から解いた)
だいたい $O(N^3)$
ACコード(1ms)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<vector<char>> ans(N, vector<char>(N, ' '));
  for(int i = 0; i < N; i++) {
    int j = N - i - 1;
    if(i > j) {
      break;
    }
    for(int k = i; k <= j; k++) {
      for(int l = i; l <= j; l++) {
        ans[k][l] = (i % 2 ? '.' : '#');
      }
    }
  }
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cout << ans[i][j];
    }
    cout << endl;
  }
}

AC時間:2:17

C問題(diff:161)

バケット法の練習ですね
$A$ の要素ごとにわけてインデックスの差の最小値を取り、もしなかったら-1的な感じが良いでしょう。計算量は $O(N)$ です。
ACコード(87ms)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<vector<int>> A((int)1e6+5, vector<int>(0, 0));
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    A[a].push_back(i);
  }
  int ans = N + 1;
  for(int i = 1; i <= (int)1e6; i++) {
    if((int)A[i].size() == 0) {
      continue;
    }
    for(int j = 0; j < (int)A[i].size() - 1; j++) {
      ans = min(ans, A[i][j + 1] - A[i][j] + 1);
    }
  }
  if(ans == N + 1) {
    cout << -1 << endl;
  }
  else {
    cout << ans << endl;
  }
}

AC時間:16:05

D問題(diff:919)

これ350じゃないです、400です

E問題(diff:978)

あと少しでした(2ケースだけWAになってしまった…)
コンテスト後ACコード(253ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//ここからグラフ探索系
using Graph = vector<vector<int>>;
struct edge {
  int to;
  ll cost;
};
using Cost_Graph = vector<vector<edge>>;
using D_heap = priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>;
//グラフ探索系終わり
//library end

edge make_edge(int a, ll b) {
  edge ans;
  ans.to = a, ans.cost = b;
  return ans;
}

Cost_Graph G(400100);
vector<ll> dist(400100, -1);

int main() {
  int N, M;
  ll X;
  cin >> N >> M >> X;
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(make_edge(v, 1)), G[v + N].push_back(make_edge(u + N, 1));
  }
  for(int i = 1; i <= N; i++) {
    G[i].push_back(make_edge(i + N, X)), G[i + N].push_back(make_edge(i, X));
  }
  G[2 * N].push_back(make_edge(N, 0));
  D_heap que;
  que.push(make_pair(0LL, 1));
  while(!que.empty()) {
    pair<ll, int> v = que.top();
    que.pop();
    if(dist[v.second] != -1) {
      continue;
    }
    dist[v.second] = v.first;
    for(edge next_v : G[v.second]) {
      if(dist[next_v.to] == -1) {
        que.push(make_pair(v.first + next_v.cost, next_v.to));
      }
    }
  }
  cout << dist[N] << endl;
}

感想

疲れた(パフォーマンス614,レート680)
次こそは何もないように頑張ります