RUPC2019 DAY2 の解いた問題まとめ
RUPC2019 お疲れさまでした。
DAY2 の解いた問題のまとめをソースコードとともに掲載します。
[問題リンク]
Aizu Online Judge Arena
A問題: Lunch
pair
#include<bits/stdc++.h>
using namespace std;
signed main(){
char c[3] = {'A', 'B', 'C'};
vector<pair<int, char> > v(3);
for(int i = 0; i < 3; i++){
int x; cin >> x;
v[i] = {x, c[i]};
}
sort(v.begin(), v.end());
cout << v[2].second << endl;
return 0;
}
B 問題: Milk
交換できる回数は max(0, (x - b)) / (a - b) で求まる
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;
signed main(){
int a, b, x; cin >> a >> b >> x;
cout << (x + ((max(0LL, (x - b)) / (a - b)) % MOD) * (b % MOD) ) % MOD << endl;
return 0;
}
C 問題: Phone Number
ボタンの並び方は 9! 通りなので、全探索できる。
G[i][j] := i -> j と指を動かす回数 をあらかじめ求めておく。
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007LL;
signed main(){
int n; cin >> n;
string s; cin >> s;
int G[10][10] = {};
for(int i = 1; i < n; i++){
int cur = (int)(s[i - 1] - '0');
int nxt = (int)(s[i] - '0');
G[cur][nxt]++;
}
vector<int> vec(9);
for(int i = 0; i < 9; i++) vec[i] = i + 1;
int ans = INF;
vector<int> ansV(9);
do{
int phone[3][3];
for(int j = 0; j < 3; j++){
for(int i = 0; i < 3; i++){
phone[i][j] = vec[3 * j + i];
}
}
int cost = 0;
for(int ci = 0; ci < 3; ci++){
for(int cj = 0; cj < 3; cj++){
for(int ni = 0; ni < 3; ni++){
for(int nj = 0; nj < 3; nj++){
int cur = phone[ci][cj];
int nxt = phone[ni][nj];
int dis = (int)abs(ci - ni) + (int)abs(cj - nj);
cost += G[cur][nxt] * dis;
}
}
}
}
if(cost < ans){
ans = cost;
ansV = vec;
}
}while(next_permutation(vec.begin(), vec.end()));
for(int j = 0; j < 3; j++){
for(int i = 0; i < 3; i++){
cout << ansV[3 * j + i];
}
cout << endl;
}
return 0;
}
D 問題: Tunnel
dp[i][j] := y_i までが決まっており、y_i = j となったときの面積の最大値
y の取りうる範囲を 1 <= y <= M とると、遷移は O(M) かかり、全体として O(N M^2)
m = 500 と適当に決めてといた。
算数パートは、(1)三角形が二つできるパターンと、(2)台形が一つのパターンの二つの場合分けをした。
#include<bits/stdc++.h>
using namespace std;
#define MAX_HIGHT 500
const int MOD = 1000000007LL;
signed main(){
int n; cin >> n;
vector<double> h(n);
for(int i = 0; i < n; i++) cin >> h[i];
vector<vector<double> > dp(n + 1, vector<double> (MAX_HIGHT + 10, 1e18));
dp[0][1] = 0.0;
for(int i = 0; i < n; i++){
for(int j = 1; j <= MAX_HIGHT; j++){
if(dp[i][j] == 1e18) continue;
for(int k = 1; k <= MAX_HIGHT; k++){
double L = abs(h[i] - j);
double R = abs(h[i] - k);
double S;
if((h[i] - j) * (h[i] - k) <= 0){
//三角形二つ
if(abs(L * L + R * R) < 1e-8) S = 0.0;
else S = (L * L + R * R) / (2.0 * (L + R));
}else{
//台形
if(abs(L + R) < 1e-8) S = 0.0;
else S = (L + R) / 2.0;
}
dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + S);
}
}
}
double ans = 1e18;
for(int i = 0; i <= MAX_HIGHT; i++) ans = min(ans, dp[n][i]);
printf("%.10f\n", ans);
return 0;
}
E 問題: こたつがめを燃やさないで
ダイクストラ法でがんばる。
上下左右移動(1)
斜め移動(2)
爆弾がある場合(a)
爆弾がない場合(b)
の組み合わせの 4 通りの辺の張り方がある
実装は、グリッドをグラフに変換してから Dijkstra をしている
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007LL;
const int INF = MOD;
int di[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};
vector<int> dijk(int s, int v, vector<vector<pair<int, int> > > adjlist){
priority_queue <pair<int, int> > wait;
vector<int> result(v, INF);
//スタート地点を追加
result[s] = 0;
wait.push(make_pair(0, s));
//ダイクストラ本体
while(!wait.empty()){ //waitが空になるまで
int nowpoint = wait.top().second;
int nowcost = -wait.top().first;
wait.pop();
if(result[nowpoint] < nowcost) continue;
//今いる頂点と隣接しているすべての頂点をなめる
for(int i = 0; i < adjlist[nowpoint].size(); i++){
int nextpoint = adjlist[nowpoint][i].second;
int nextcost = nowcost + adjlist[nowpoint][i].first;
//現時点より安く到達できそうであれば、結果を更新して優先度付きキューに格納
if(result[nextpoint] > nextcost){
result[nextpoint] = nextcost;
wait.push(make_pair(-nextcost, nextpoint));
}
}
}
return result; //結果列を返す
}
signed main(){
int h, w, a, b; cin >> h >> w >> a >> b;
vector<vector<char> > G(h + 2, vector<char> (w + 2, 'x'));
int si, sj, gi, gj;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> G[i][j];
if(G[i][j] == 's'){
si = i;
sj = j;
G[i][j] = '.';
}
if(G[i][j] == 'g'){
gi = i;
gj = j;
G[i][j] = '.';
}
}
}
int GridtoGraph[1010][1010];
int num = 0;
for(int i = 0; i <= h + 1; i++){
for(int j = 0; j <= w + 1; j++){
GridtoGraph[i][j] = num;
num++;
}
}
//first := コスト second := 行先
vector<vector<pair<int, int> > > adjlist(num);
int s = GridtoGraph[si][sj];
int g = GridtoGraph[gi][gj];
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
int cur = GridtoGraph[i][j];
bool isExist = false; //爆弾が周りにあるか
if(G[i][j] == '*') isExist = true;
for(int h = 0; h < 8; h++){
int ni = i + di[h];
int nj = j + dj[h];
if(G[ni][nj] == '*') isExist = true;
}
for(int h = 0; h < 8; h++){
int ni = i + di[h];
int nj = j + dj[h];
if(G[ni][nj] == 'x') continue;
//この時点で '.' '*' '#' の三通り
int nxt = GridtoGraph[ni][nj];
if(h % 2 == 0){
//上下左右の移動
if(G[ni][nj] == '#'){
if(isExist) continue;
adjlist[cur].push_back({a + b, nxt});
}else{
adjlist[cur].push_back({a, nxt});
}
}else{
//斜め移動
int subi1 = i + di[h - 1];
int subj1 = j + dj[h - 1];
int subi2 = i + di[(h + 1) % 8];
int subj2 = j + dj[(h + 1) % 8];
if(G[ni][nj] == '#' || G[subi1][subj1] == '#' || G[subi2][subj2] == '#'){
if(isExist) continue;
adjlist[cur].push_back({2 * a + b, nxt});
}else{
adjlist[cur].push_back({2 * a, nxt});
}
}
}
}
}
vector<int> result(num);
result = dijk(s, num, adjlist);
int ans = result[g];
if(ans == INF) cout << "INF" << endl;
else cout << ans << endl;
return 0;
}
楽しかったです。会津大学さん、ありがとうございました。
