Indeedなう 本選A
オープンコンテストに参加して,3完でした.ボーダー突破は難しい.
以下 問題の感想とソースコード
A Table Tennis
貪欲だなと思い,書いたら通る
int n; int a[110]; int main(void){ cin >> n; rep(i,n) cin >> a[i]; sort(a,a+n); int cmin=2015,cmax=0; rep(i,n){ int cur=a[i]+a[n-1-i]; cmin=min(cmin,cur); cmax=max(cmax,cur); } cout << cmax-cmin << endl; return 0; }
B Office Ninja
六角座標のダイクストラ.行の偶奇によって,列の遷移先が変わるので注意
int r,c; string a[110]; int dr[2][6]={ {-1,-1,0,0,1,1}, {-1,-1,0,0,1,1} }; int dc[2][6]={ {-1,0,-1,1,-1,0}, {0,1,-1,1,0,1} }; int dist[110][110]; typedef tuple<int,int,int> state; int dijkstra(){ int sr=-1,sc=-1,gr=-1,gc=-1; rep(i,r)rep(j,c){ if(a[i][j]=='s') sr=i,sc=j; if(a[i][j]=='t') gr=i,gc=j; } rep(i,r)rep(j,c) dist[i][j]=inf; dist[sr][sc]=0; set<state> s; state init(0,sr,sc); s.insert(init); while(!s.empty()){ state cur=*(s.begin()); s.erase(cur); int cr,cc,cost; tie(cost,cr,cc)=cur; if(dist[cr][cc]<cost) continue; rep(i,6){ int nr=cr+dr[cr&1][i]; int nc=cc+dc[cr&1][i]; if(nr<0||r<=nr||nc<0||c<=nc) continue; int ncost=cost; if(isdigit(a[nr][nc])) ncost+=(a[nr][nc]-'0'); if(dist[nr][nc]>ncost){ dist[nr][nc]=ncost; state next(ncost,nr,nc); s.insert(next); } } } return dist[gr][gc]; } int main(void){ cin >> r >> c; rep(i,r) cin >> a[i]; cout << dijkstra() << endl; return 0; }
C Optimal Recommendations
各項目の点数が101通りだから,3次元配列を取る.
memo[a][b][c]=最大年収とすればよい.
そして,memoの情報を伝搬させていくときに,それぞれ小さい方から回す.
int memo[110][110][110]; int main(void){ int n,m; cin >> n >> m; rep(i,n){ int a,b,c,w; cin >> a >> b >> c >> w; memo[a][b][c]=max(memo[a][b][c],w); } rep(d,301)rep(i,101)rep(j,101)rep(k,101){ if(i+j+k==d){ memo[i+1][j][k]=max(memo[i+1][j][k],memo[i][j][k]); memo[i][j+1][k]=max(memo[i][j+1][k],memo[i][j][k]); memo[i][j][k+1]=max(memo[i][j][k+1],memo[i][j][k]); } } rep(i,m){ int x,y,z; cin >> x >> y >> z; cout << memo[x][y][z] << endl; } return 0; }