ABC396の振り返り

4完奪還

A問題(diff:不明)

シンプルにミスり1ペナ
$i = 1, \dots , N - 2$ について $A_i = A_{i+1} = A_{i+2}$ であるものが存在するか判定すればよいです。
計算量は $O(N)$ です。
ACコード(pypy54ms, c++1ms)

N = int(input())
A = list(map(int, input().split()))
f = 0
for i in range(N - 2):
  if A[i] == A[i + 1] and A[i] == A[i + 2]:
    f = 1
if f:
  print("Yes")
else:
  print("No")

AC時間:2:39

B問題(diff:不明)

最近のB問題の中で最も簡単
c++ならvectorでも使えばよいでしょう。
計算量は $O(Q)$ です。
ACコード(1ms)

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

int main() {
  int Q;
  cin >> Q;
  vector<int> card(100, 0);
  for(int i = 0; i < Q; i++) {
    int query;
    cin >> query;
    if(query - 1) {
      cout << card[(int)card.size() - 1] << endl;
      card.pop_back();
    }
    else {
      int x;
      cin >> x;
      card.push_back(x);
    }
  }
}

AC時間:3:50

C問題(diff:不明)

謎に沼ってしまった
$B$ と $W$ を降順ソートし、順に貪欲っぽくすれば良かったのですが、普通にコーナーケースっぽいものに引っかかってしまいました。
変数の初期化をどうするかに気をつけましょう(自戒)
計算量は $O(NlogN+MlogM)$ です。(ソート)
ACコード(129ms)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//library end

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> B(N), W(M);
  for(ll &o : B) {
    cin >> o;
  }
  for(ll &o : W) {
    cin >> o;
  }
  sort(B.begin(), B.end(), [](int a, int b) { return a > b; }), sort(W.begin(), W.end(), [](int a, int b) { return a > b; });
  ll sum = 0;
  int ind = -1;
  for(int i = 0; i < N; i++) {
    if(B[i] < 0) {
      break;
    }
    sum += B[i], ind = i;
  }
  ll ans = sum;
  for(int i = 0; i < M; i++) {
    if(W[i] <= 0 || i >= N) {
      break;
    }
    sum += (ind < i ? B[i] : 0) + W[i], ans = max(ans, sum);
  }
  cout << ans << endl;
}

AC時間:60:35(!?)

D問題(diff:不明)

久々のDグラフ探索
DFSで単純パス全列挙していくと良いです。辺を通る度にxorしましょう。
計算量は $O(N!+M)$ です。$N \le 10$、$M \le 45$ より、間に合います。
ACコードではダイクストラ法用の自作ライブラリを使っています。ですが、この問題の解法はダイクストラ法ではないです。
ACコード(2ms)

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

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

int N;
Cost_Graph G;
vector<int> seen(15, false);
ll ans = (ll)2e18;
void dfs(int v, ll x) {
  seen[v] = true;
  if(v == N) {
    ans = min(ans, x);
  }
  else {
    for(edge next_v : G[v]) {
      if(seen[next_v.to]) {
        continue;
      }
      dfs(next_v.to, x ^ next_v.cost);
    }
  }
  seen[v] = false;
}

int main() {
  int M;
  cin >> N >> M;
  G.assign(N + 1, vector<edge>(0));
  for(int i = 0; i < M; i++) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    G[u].push_back(make_edge(v, w)), G[v].push_back(make_edge(u, w));
  }
  dfs(1, 0);
  cout << ans << endl;
}

AC時間:17:48

E問題(diff:不明)

グラフ帰着ですか…

F問題(diff:不明)

ちらっと見て遅延セグ木かなと思いましたが、普通に違うわ、遅延セグ木の使い方も分からないわで、解けませんでした

感想

一応4完できたので良かったです。
パフォーマンス737でレート686になりました。もっと上げていきたいです。
2年生になるまでに入緑は厳し目かもしれないので、4月か5月中には行きたいです。