KUPC
またらてプロ(@LatteMalta)と出ました。
A問題(らて)
やるだけ。
B問題(僕)
全探索を書けばよいのに手動で頑張りました。
なぜか血迷ってコンソール上のツールっぽいものを作りましたが要らなかったです。
そんなものを作る暇があればn回全探索が書けました。
C問題(らて)
ワーシャルフロイドらしいです。
コード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() int N; int a[30][30]; const int INF=1001001001; int dist[30][30]; void solve(){ cin>>N; rep(i,N)rep(j,N)cin>>a[i][j]; rep(i,N)if(a[i][i]){ cout<<"NO"<<endl; return; } fill_n(*dist,30*30,INF); rep(i,N)dist[i][i]=0; rep(i,N)rep(j,N){ if(~a[i][j])dist[i][j]=a[i][j]; } rep(k,N)rep(i,N)rep(j,N){ dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } rep(i,N)rep(j,N){ if(a[i][j]==-1){ if(dist[i][j]!=INF){ cout<<"NO"<<endl; return; } } else{ if(dist[i][j]!=a[i][j]){ cout<<"NO"<<endl; return; } } } cout<<"YES"<<endl; } int main(){ int T; cin>>T; while(T--)solve(); return 0; }
D問題(僕)
動くときは常に右にしか動かないので、町iまで進むときに必要な最小の日数(もしくは行けないか)とその時の所持金を計算しておきます。
そのあと、各町iについて余った日数で一番有益な町に留まり続ける貪欲(O(1))を、全てのiについてやりました。
コード
using namespace std; typedef long long ll; #define int long long int N, A[100001], B[100001]; int mi[100001], cost[100001]; void GetMinDays() { int maxB = B[0], cost_ = 0; for (int i = 1; i <= N; i++) { mi[i] = mi[i - 1] + 1; cost_ += A[i - 1]; if (cost_ < 0) { if (maxB == 0) { mi[i] = LLONG_MAX / 2; return; } int plus = (-cost_ - 1) / maxB + 1; mi[i] += plus; cost_ += plus * maxB; } cost[i] = cost_; maxB = max(maxB, B[i]); } } int Solve() { int maxB = 0, res = 0; for (int i = 0; i <= N; i++) { maxB = max(maxB, B[i]); if (mi[i] > N) break; res = max(res, (N - mi[i]) * maxB + cost[i]); } return res; } signed main() { cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < N; i++) { cin >> B[i]; } GetMinDays(); printf("%lld\n", Solve()); return 0; }
E問題(僕)
Aを長方形の角に固定し、Bについて三分探索、更にその中でCについて三分探索しました。完全にゴリ押し感があります。
よく考えたら実はCも下半分だけで良いですが計算量にはほぼ関係ないですね。
コード
using namespace std; typedef long long ll; #define int long long int T, H, W; double GetDistance(double dx, double dy) { return sqrt(dx * dx + dy * dy); } double F(double b, double c) { return min(GetDistance(W, c), GetDistance(W - b, H - c)); } double PutC(double b) { double l = 0, r = H; while (r - l > 1e-8) { double c1 = (l * 2 + r) / 3, c2 = (l + r * 2) / 3; if (F(b, c1) < F(b, c2)) l = c1; else r = c2; } return min(GetDistance(b, H), F(b, r)); } double PutB() { double l = 0, r = W / 2.0; while (r - l > 1e-8) { double c1 = (l * 2 + r) / 3, c2 = (l + r * 2) / 3; if (PutC(c1) < PutC(c2)) l = c1; else r = c2; } return PutC(r); } signed main() { cin >> T; for (int t = 0; t < T; t++) { cin >> H >> W; if (H > W) swap(H, W); double ans = PutB(); printf("%.6lf\n", ans); } return 0; }
F問題(僕)
二分木を作ったら、逆ポーランド記法が実は深さ優先探索の帰りがけ順となっていることに気付いたので、キュー版は幅優先探索の帰りがけ順なのでは？という感じでやりました。
using namespace std; typedef long long ll; #define int long long struct Vertex { char c; Vertex *p[2]; Vertex(char _c) { c = _c; p[0] = p[1] = NULL; } }; Vertex *root; void ILikeTree(string A) { stack<Vertex*> s; for (int i = 0; i < A.size(); i++) { Vertex *v = new Vertex(A[i]); if (!isdigit(A[i])) { v = new Vertex(A[i]); v->p[0] = s.top(); s.pop(); v->p[1] = s.top(); s.pop(); } s.push(v); if (i == A.size() - 1) root = v; } } string Solve() { string B; queue<Vertex*> q; q.push(root); while (!q.empty()) { Vertex* v = q.front(); q.pop(); B.push_back(v->c); if (v->p[0] == NULL) continue; q.push(v->p[1]); q.push(v->p[0]); } reverse(B.begin(), B.end()); return B; } signed main() { string A; cin >> A; ILikeTree(A); cout << Solve() << endl; return 0; }
G問題(らて)
らて「二分探索+BIT+貪欲」
さすがプロ。
コード
using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define int long long struct BIT{ int N; vector<int>dat; void init(int n){ N=n; dat.assign(N+1,0); } void add(int k,int x){ for(k++;k<=N;k+=k&-k)dat[k]+=x; } int sum(int k){ int ret=0; for(k++;k;k-=k&-k)ret+=dat[k]; return ret; } }; int N; int A[100000],B[100000]; int latte[100000]; vector<int>malta[100000]; BIT bit; signed main(){ scanf("%lld",&N); rep(i,N)scanf("%lld",&A[i]); rep(i,N)scanf("%lld",&B[i]); rep(i,N)latte[i]=A[i]; sort(latte,latte+N); rep(i,N)if(latte[i]<B[i]){ cout<<-1<<endl; return 0; } rep(i,N)A[i]=upper_bound(B,B+N,A[i])-B-1; rep(i,N)malta[A[i]].pb(i); bit.init(N+100); priority_queue<int>que; int prev=INT_MAX,idx=N-1; int ans=0; for(int i=N-1;i>0;i--){ if(prev!=B[i]){ prev=B[i]; for(;idx>=i;idx--)rep(j,malta[idx].size())que.push(malta[idx][j]); } int cur=que.top();que.pop(); int tmp=bit.sum(N)-bit.sum(cur); ans+=N-1-cur-tmp; bit.add(cur,1); } cout<<ans<<endl; return 0; }
H問題(らて)
らて「bitを決めるDP(bitDPではない)」
さすがプロ。
コード
using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define int long long typedef pair<int,int>pii; const int INF=LLONG_MAX/100; void debug(int bit){ for(int i=0;i<10;i++)cout<<(bit>>i&1);cout<<endl; } int dp[65][130][2]; void solve(){ int N;cin>>N; fill_n(**dp,65*130*2,INF); dp[0][60][0]=0; for(int i=0;i<60;i++){ for(int j=1;j<120;j++){ for(int k=0;k<2;k++){ if(dp[i][j][k]==INF)continue; int b; if(N>>i&1){ dp[i+1][j-1+k][1]=min(dp[i+1][j-1+k][1],dp[i][j][k]+(1ll<<i)); dp[i+1][j+1-k][k]=min(dp[i+1][j+1-k][k],dp[i][j][k]); } else{ dp[i+1][j-k][k]=min(dp[i+1][j-k][k],dp[i][j][k]+(1ll<<i)); dp[i+1][j+k][0]=min(dp[i+1][j+k][0],dp[i][j][k]); } } } } cout<<dp[60][60][0]<<endl; } signed main(){ int T; cin>>T; while(T--)solve(); return 0; }
結果
らてプロがめっちゃ17位を取ってくれたっぽいです。(チームでは1位疑惑がある)
F問題のWA数が足を引っ張っている感じで申し訳ないです。
良問だったらしいのでG,Hを近いうちに解こうと思います。
KUPCは毎年良問集らしいですし、難易度的にも心優しいめコンテストでした。
