D - Mixing Experiment
D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder
薬品をにする最小費用を求める問題。
制約も小さいので、でナップサックをすると解ける。
更新をを薬品の最小の比だと思い込んでて時間を溶かした。
具体的には、漸化式を
int div=(int)gcd((ll)(j+val[i+1].first),(ll)(k+val[i+1].second)); pii ni=mp((j+val[i+1].first)/div,(k+val[i+1].second)/div); cmin(dp[i+1][ni.first][ni.second],dp[i][j][k]+c[i+1]);
こんな形で更新してた。
頭を冷やしてみると、比の足し算はやばい事がわかるし、比はとの間にしか成り立たない関係ということもわかる。
反省。
#include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vector<int> > #define vl vector<ll> #define vvl vector<vector<ll>> #define vb vector<bool> #define vc vector<char> #define vs vector<string> using ll = long long; using ld =long double; #define int ll #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define loop(i,s,n) for(int i=s;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; typedef pair<int, int> pii; typedef pair<int,pii> piii; #define mp make_pair long long gcd(long long a, long long b) {return b ? gcd(b, a % b) : a;} long long lcm(long long m, long long n ){ if((0 == m )||( 0 == n ))return 0; return ((m / gcd(m, n)) * n); } int dp[41][401][401]; signed main(){ int n; cin>>n; pii comp; cin>>comp.first>>comp.second; rep(i,n)rep(j,401)rep(k,401)dp[i][j][k]=INF; dp[0][0][0]=0; vector<pii>val; vector<int>c(n); rep(i,n){ pii temp; cin>>temp.first>>temp.second; cin>>c[i]; val.push_back(mp(temp.first,temp.second)); dp[i][val[i].first][val[i].second]=c[i]; } rep(i,n-1){ rep(j,401){ rep(k,401){ if(dp[i][j][k]==INF)continue; cmin(dp[i+1][j][k],dp[i][j][k]); pii ni=mp((j+val[i+1].first),(k+val[i+1].second)); cmin(dp[i+1][ni.first][ni.second],dp[i][j][k]+c[i+1]); } } } int ans=INF; rep(i,401)rep(j,401){ int div=gcd(i,j); if(i&&j){ if(i/div==comp.first&&j/div==comp.second)cmin(ans,dp[n-1][i][j]); } } if(ans==INF)ans=-1; cout<<ans<<endl; }
D - 3N Numbers
D: 3N Numbers - AtCoder Beginner Contest 062 | AtCoder
以前解けなかった問題が、ヒントで解けるようになったので…
前半の要素と後半の要素の差を最大にすれば良い。
中間の要素(配列の添字だと)を最適に選べば良い。
PriorityQueueを使って、前半要素のうちの最小値と中間要素を比較していく。(後半の場合も同じく)
ちなみに、
Submission #1735282 - AtCoder Beginner Contest 062 | AtCoder
こういう解法だと絶対に解けない。要素全部前半にくっつけたほうが良い場合がある。
が奇数の時、前半と後半の両方に含まれる場合があるんじゃないかと思ってたけど、そんなことはない。
(↑これでめっちゃ時間とかした。)
#include<bits/stdc++.h> using ll = long long; #define int ll #define ld long double #define INF 1e9 #define EPS 0.0000000001 #define rep(i,n) for(int i=0;i<n;i++) #define all(in) in.begin(), in.end() template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; } template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; } #define MAX 9999999 using namespace std; typedef pair<int, int> pii; typedef pair<double,double>pdd; signed main(){ int n; cin>>n; vector<int>v(3*n); rep(i,3*n) cin>>v[i]; priority_queue<int,vector<int>,greater<int>>lque; priority_queue<int,vector<int>>sque; int ls=0,ss=0; vector<int>lv; vector<int>sv; rep(i,n){ lque.push(v[i]); sque.push(v[2*n+i]); ls+=v[i]; ss+=v[2*n+i]; } lv.push_back(ls); sv.push_back(ss); int ans=-INF*INF; cmax(ans,ls-ss); rep(i,n){ lque.push(v[n+i]); sque.push(v[2*n-i-1]); ls+=v[n+i]-lque.top(); ss+=v[2*n-i-1]-sque.top(); lv.push_back(ls); sv.push_back(ss); sque.pop(); lque.pop(); } rep(i,lv.size())cmax(ans, lv[i]-sv[n-i]); cout<<ans<<endl; }
番目まで見たときの、前半の合計の最大値
番目まで見たときの、後半の合計の最小値
添字マジックには気をつけよう!
ABC 051 D - Candidates of No Shortest Paths
D: Candidates of No Shortest Paths - AtCoder Beginner Contest 051 | AtCoder
無向連結グラフの最短距離
に含まれない辺の数を求める問題です。
含まれない辺 = 全点間最短経路を求めたときに、更新された辺
が含まれない辺ということがわかります。
の範囲はたかだたなので、warshallfloyd法で充分間に合います。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) using pii = pair<int, int>; #define int ll #define INF 1e18 using ll = long long; signed main(){ int n,m; cin>>n>>m; vector<vector<int>>d(n,vector<int>(n,INF)); rep(i,m){ int a,b,c; cin>>a>>b>>c; d[a-1][b-1]=d[b-1][a-1]=c; } vector<vector<int>>d_min; rep(i,n)d[i][i]=0; d_min=d; rep(k,n)rep(i,n)rep(j,n)d_min[i][j]=min(d_min[i][j],d_min[i][k]+d_min[k][j]); int ans=0; rep(i,n)rep(j,n)if(i!=j&&d[i][j]!=INF&&d_min[i][j]!=INF&&d[i][j]!=d_min[i][j]) ans++; cout<<ans/2<<endl; return 0; }
B - PackDrop
葉から根に向かって最小値を更新していき、dfsで解くことができます。
シンプルで好きです。
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; #define mp make_pair #define INF 1e9 int ans=0; vector<vector<int>>edge(1001,vector<int>()); vector<int>cost(1001,INF); void dfs(int vertex){ if(edge[vertex].size()==0)return; rep(i,edge[vertex].size()){ int to = edge[vertex][i]; ans+=cost[to]-cost[vertex]; dfs(to); } return; } int main(){ int n,m; cin>>n>>m; vector<int>par(n+1); using pii = pair<int, int>; rep(i,n-1){ int v; cin>>v; edge[v].push_back(i+1); par[i+1]=v; } vector<int>leaf; rep(i,m){ int v,b; cin>>v>>b; cost[v]=b; leaf.push_back(v); } rep(i,leaf.size()){ int v=leaf[i]; while(v!=0){ cost[par[v]]=min(cost[par[v]],cost[v]); v=par[v]; } } ans+=(int)edge[0].size()*cost[0]; dfs(0); cout<<ans<<endl; }
ACPC2017-参加記-
ACPCの参加記です。
-
0日目
ひたすら新幹線で移動してました。
痛すぎてお尻4つに割れた
— yebi (@sigsigma19) 2017年9月17日
郡山からズに移動する途中の電車は、ひたすら同じ風景が続いてて、やはり大悪魔や植物が競プロしてたり校内にセグ木が生えている大学に移動するのは並大抵のことではないなと思ってたりしてた。
あと宿泊先のホテルが神でした。
-
1日目
立命セットだったので基本的に椅子に座る仕事をしていました。G問題(原案が自分)の問題がコンテスト終了5分まで0submitで悲しい気分になってた。
G問題が解けた人は教えてほしいです。
懇親会では隣がuwiさんと怒髪さんだったので、オセロ方式でレート上がらないかなぁと思ってたりしてた。
-
2日目
二度寝しました。
yebiくんが寝ています
— しゅもん (@shumon_84) 2017年9月19日
kenkooooさんのご厚意でタクシーに乗せてもらってコンテスト開始までに間に合いました。(ありがとうございました。)
コンテストはチーム名acpc_TMLEで参加してA,C,Fをときました。
Cで無限にバグらせて本当に申し訳なかった。(9WA)
Fはuwiさんに方針を教えてもらった(実装の仕方も教えてもらった)のでAC
実装もバグらせたし、Dも解説を聞くと十分に解くことができる問題だったので、自分の実力不足を感じたコンテストでした。
懇親会では隣の席がc7c7さんだったので、話が盛り上がりすぎて…お酒を飲みすぎました。
※RCOさん、ありがとうございます。
今日の懇親会は競プロerらしく半数ほとんど静かだったけどyebi君が寝たのが1番ウケた
— ixmel(める) (@mel_fall524) 2017年9月19日
楽しかったので…セーフ??
なんだかとても汚い話をしていた気がする…
ホテルに帰ってからは流石に反省して問題を解いて寝ました。
-
3日目
最終日は大悪魔こと、ウクーニャさん(@ukuuku09)さんとロールさん(@rollman054)さんとチーム名gpa_4.0で参加しました。
GPA4.0じゃないから今日もマスコットを担当するわ!@sigsigma19、@rollman054、今日は私の僕としてしっかり働くのよ!
— ウクーニャ (@ukuku09) 2017年9月20日
自分のgpaが一番低かったんでA問題をときました。
残りはD問題を担当したんですが、WAが取れず終了。悲しいね。
コンテスト中にukuさんにアドバイスを貰ったんですが、その通り実装していれば通せた問題を落として申し訳なかったです。
最後の最後にukuさんとろーるさんがpythonで*1B問題を通してプロ感がすごかった。
emacsとvimを使いこなしてたので、自分も勉強したいなぁ〜と思った。
-
まとめ
AOJ -2819 Country in Distortion
Country in Distortion | Aizu Online Judge
拡張Dijkstraの問題です。
各頂点に対して、頂点に到着した速度で次の辺へのコストが代わるので、今回はとして頂点からの距離を持ちます。
ここで注意しないと行けないのが、無向グラフかつコストが0の辺が存在するので、continueの条件式をとしなければ行けません。
具体的には
if(d[next.first][_v]<=now.first.first+next.second*v)continue; d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(d[next.first][_v],next.first),_v));
ifの条件式の部分です。
今持っているコストで次の頂点へと推移できる。これをcontinueで弾かなければqueに無限にpushされることになります(REになってしまいます)
#include<bits/stdc++.h> #define int long long #define rep(i,n) for(int i=0; i<n;i++) using namespace std; #define MAX 1e9 int INF=MAX*MAX; typedef pair<int,int> pii; typedef pair<pii,long long> piii; vector<vector<long long>>d(501,vector<long long>(51,INF)); signed main(){ int n,m; cin>>n>>m; vector<vector<pii>>edge(n,vector<pii>()); rep(i,m){ int a,b,c; cin>>a>>b>>c; --a,--b; edge[a].push_back(pii(b,c)); edge[b].push_back(pii(a,c)); } int v0,a,b,c; cin>>v0>>a>>b>>c; priority_queue<piii,vector<piii>,greater<piii>>que; d[0][v0]=0; que.push(piii(pii(0,0),v0)); while(!que.empty()){ piii now=que.top(); que.pop(); int v=now.second; int _v=(v*a+b)%c; /*queに積んでる間に最短距離が更新されたかを防ぐifなので<で良い*/ if(d[now.first.second][v]<now.first.first)continue; for(int i=0; i<edge[now.first.second].size();i++){ pii next=edge[now.first.second][i]; if(d[next.first][_v]<=now.first.first+next.second*v)continue; d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(d[next.first][_v],next.first),_v)); } } int ans=INF; rep(i,51)if(d[n-1][i]!=INF){ vector<vector<long long>>_d(501,vector<long long>(51,INF)); _d[n-1][i]=d[n-1][i]; que.push(piii(pii(d[n-1][i],n-1),i)); while(!que.empty()){ piii now=que.top(); que.pop(); int v=now.second; int _v=(v*a+b)%c; if(_d[now.first.second][v]<now.first.first)continue; for(int i=0; i<edge[now.first.second].size();i++){ pii next=edge[now.first.second][i]; if(_d[next.first][_v]<=now.first.first+next.second*v)continue; _d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(_d[next.first][_v],next.first),_v)); } } rep(i,51)ans=min(ans,_d[0][i]); } cout<<ans<<endl; }