Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320） - AtCoder
二重ループで全探索。回文は 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;
}
- リールが全て同じ数で止まるケースは 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];
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;
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;
}
絶対座標がわかっているのは人 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;
}
そうめん流しに並んでいる人、列から外れた人をそれぞれ２つの優先度付きキューに入れる。
- 出来事 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 問題は動的計画法で解く方針を立てたものの時間が足りず。解くスピードが足りないな。
