AtCoder abc320 参加メモ

Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320） - AtCoder

B - Longest Palindrome

二重ループで全探索。回文は reverse した文字列と等しいかどうかで判定

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

int main() {
  string s; cin >> s;
  int n = s.size();

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

  int ans = 0;
  REP(i,n) for(int j = 1; j+i <= n; j++) {
    if (check(s.substr(i,j))) ans = max(ans,j);
  }
  cout << ans << endl;
  return 0;
}

C - Slot Strategy 2 (Easy)

リールが全て同じ数で止まるケースは 9 通りしかない(000,111,222,...,999)
同じ時間に止められるリールは一つ。またリールはどれから止めても良いため、止める順番は 3! = 6 通りある

上記をうまく探索する。

#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();

// リールを止める順番
const vector<vector<int>> orders = {
  { 0,1,2 },{ 0,2,1 },
  { 1,0,2 },{ 1,2,0 },
  { 2,0,1 },{ 2,1,0 }
};

int main() {
  int m; cin >> m;
  vector<string> s(3);
  REP(i,3) cin >> s[i];
  // g[i][j] := i 番目のリールでスロットの表示に j が現れる時間の集合  
  vector g(3,vector(10,vector<int>()));
  REP(i,3) REP(j,m) g[i][s[i][j]-'0'].push_back(j);

  auto impossible = [&](int i) {
    REP(j,3) if (g[j][i].size() == 0) return true;
    return false;
  };

  int ans = INF;
  REP(i,10) {
    if (impossible(i)) continue; // i|i|i でリールを止められるか
    for(auto order: orders) {
      int t = 0;
      for(int reel: order) {
        int modt = t%m;
        auto it = lower_bound(g[reel][i].begin(),g[reel][i].end(),modt);
        if (it == g[reel][i].end()) t += m - modt + g[reel][i][0];
        else t += *it - modt;
        t += 1;
      }
      ans = min(ans,t-1);
    }
  }

  cout << (ans == INF ? -1 : ans) << endl;
  return 0;
}

D - Relative Position

絶対座標がわかっているのは人 1 のみ。グラフとして考えて人 1 から到達可能な点は絶対座標がわかる。DFS で到達不可能な点は undecidable となる。

#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,pair<ll,ll>>;

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(m),b(m);
  vector<ll> x(m),y(m);
  vector g(n,vector<P>());

  REP(i,m) {
    cin >> a[i] >> b[i] >> x[i] >> y[i];
    a[i]--; b[i]--;
    g[a[i]].push_back({ b[i], {x[i],y[i]} });
    g[b[i]].push_back({ a[i], {-x[i],-y[i]} });
  }

  vector<pair<ll,ll>> ans(n);
  ans[0] = {0,0};
  vector<bool> visited(n);
  auto dfs = [&](auto self, int i) -> void {
    for(auto [v,pos]: g[i]) {
      if (visited[v]) continue;
      visited[v] = true;

      auto [nx,ny] = pos;
      auto [px,py] = ans[i];
      ans[v] = { px+nx, py+ny };
      self(self,v);
    }
  };
  visited[0] = true;
  dfs(dfs,0);

  REP(i,n) {
    if (!visited[i]) cout << "undecidable" << endl;
    else cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}

E - Somen Nagashi

そうめん流しに並んでいる人、列から外れた人をそれぞれ２つの優先度付きキューに入れる。

出来事 i が起こったとき、列から外れた人のキューにその時間内に戻ってくる人がいたら、キューから出しそうめん流しに並んでいる人のキューへ加える。
そうめん流しに並んでいる人のキューから番号の最も小さい人がそうめんを食べる。
そうめんを食べた人を列から外れた人のキューへ追加する。

#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<ll,int>;

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

  // そうめん流しに並んでいる人
  priority_queue<int, vector<int>, greater<int>> pq1;
  // 列から外れた人
  priority_queue<P, vector<P>, greater<P>> pq2;
  REP(i,n) pq1.push(i);

  vector<ll> ans(n);
  REP(i,m) {
    // 列へ戻ってくる人の処理
    while(pq2.size()) {
      auto [vt,vi] = pq2.top();
      if (vt > t[i]) break;
      pq2.pop(); pq1.push(vi);
    }
    // そうめんを食べる人の処理
    if (pq1.empty()) continue;
    auto vi = pq1.top(); pq1.pop();
    ans[vi] += w[i];
    pq2.emplace(t[i]+s[i],vi);
  }

  for(auto v: ans) cout << v << endl;
  return 0;
}

雑感

直近 5 回のコンテストで酷い結果を連発しレートは highest から 150 も下がる始末。今日こそはなんとかしたかった。前回といい近頃の C 問題は難しいね。今回は E まで解けたので 1000番台に入ってるかと思いきや 2000 番台。 F 問題は動的計画法で解く方針を立てたものの時間が足りず。解くスピードが足りないな。