AtCoder abc376 参加メモ

AtCoder Beginner Contest 376 - AtCoder

A - Candy Button

最後に飴をもらった時刻を記憶しておく

#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,c; cin >> n >> c;
  int p = -1e4, ans = 0;
  REP(_,n) {
    int t; cin >> t;
    if (t-p >= c) { ans++; p = t; }
  }
  cout << ans << endl;
  return 0;
}

B - Hands on Ring (Easy)

愚直にシミュレーションしたが、B にしては実装が重かった。 L or R、左 or 右回りで場合分けがあり、これをそのまま書くと煩雑になってしまう。

  • R を動かす場合は swap(l,r) をし、コード上は常に L を動かすだけにする
  • 左 or 右回りは dir で動く方向を +1 or -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,q; cin >> n >> q;
  int l = 0, r = 1;
  auto f = [&](int dir, int pos, int t)  {
    int cost = 0;
    while(pos != t) {
      if (pos == r) { cost = 1e9; break; }
      cost++;
      pos = ((pos+dir) % n + n) % n;
    }
    return cost;
  };

  int ans = 0;
  REP(_,q) {
    char h; int t; cin >> h >> t; t--;
    if (h == 'R') swap(l,r);
    ans += min(f(1,l,t),f(-1,l,t));
    l = t;
    if (h == 'R') swap(l,r);
  }
  cout << ans << endl;
  return 0;
}

C - Prepare Another Box

追加する箱のサイズを二分探索で求めた。 おもちゃの入れ方は、一番小さいおもちゃから、一番小さい箱に貪欲に入れていくのが最適となる。

#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<int> a(n),b(n-1);
  REP(i,n) cin >> a[i];
  REP(i,n-1) cin >> b[i];
  sort(a.begin(),a.end());

  auto f = [&](int x) -> bool {
    auto c = b;
    c.push_back(x);
    sort(c.begin(),c.end());
    REP(i,n) if (a[i] > c[i]) return false;
    return true;
  };

  int ok = 1e9+5, ng = 0;
  while(ok-ng>1) {
    int mid = (ok+ng)/2;
    if (f(mid)) ok = mid;
    else ng = mid;
  }
  cout << (ok > 1e9 ? -1 : ok) << endl;
  return 0;
}

D - Cycle

頂点1 から BFS して頂点 1 に最短で戻る経路を探索する。 ED問題にしては?とくに捻りはなくBFSするだけだった。

#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 n,m; cin >> n >> m;
  vector g(n,vector<int>());
  REP(i,m) {
    int a,b; cin >> a >> b; a--; b--;
    g[a].push_back(b);
  }

  vector<int> dist(n,INF);
  queue<int> q;
  q.push(0);
  dist[0] = 0;

  while(q.size()) {
    auto now = q.front(); q.pop();
    for(auto v: g[now]) {
      if (v == 0) { cout << dist[now]+1 << endl; return 0; }
      if (dist[v] <= dist[now]+1) continue;
      dist[v] = dist[now]+1;
      q.push(v);
    }
  }

  cout << -1 << endl;
  return 0;
}

E - Max × Sum

{a,b} のペアを昇順ソートして a が小さい値から順番に見ていく。 a は昇順に見ていけば今の a が常に最大の値となる。 Σb は、k 個を越えたら以降は一番大きい値を捨てていけば良い。

#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>;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int t; cin >> t;
  REP(_,t) {
    int n,k; cin >> n >> k;
    vector<P> items(n);
    REP(i,n) cin >> items[i].first;
    REP(i,n) cin >> items[i].second;
    sort(items.begin(),items.end());

    priority_queue<int> pq;
    ll sumb = 0, ans = LINF;
    for(auto [a,b]: items) {
      pq.push(b);
      sumb += b;
      if ((int)pq.size() == k) {
        ans = min(ans,(ll)a * sumb);
        sumb -= pq.top(); pq.pop();
      }
    }
    cout << ans << endl;
  }
  return 0;
}

雑感

B 問題でかなり時間かけてしまい大焦り。 D 問題もスタートが頂点1 というのを見落として、全体で最小サイクルを探索するコードを書いてしまった。 F問題は場合分けを考えていたら頭がおかしくなってきたので諦め。

D 問題解いた時点ではかなり遅かったが、E が解けたおかげで Highest 更新。まだいつ緑に落ちてもおかしく水準なのでヒヤヒヤする。

tic40さんのAtCoder Beginner Contest 376(Promotion of AtCoder Career Design DAY)での成績:1469位
パフォーマンス:1409相当
レーティング:1214→1235 (+21) :)
Highestを更新しました!
#AtCoder #ABC376(PromotionofAtCoderCareerDesignDAY) https://atcoder.jp/users/tic40/history/share/abc376?lang=ja