ABC025を解いてみた
A問題
入力をソートして(n-1)/5文字目、(n-1)%5文字目が答えの文字列になります。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 int main(void) { vector<char> str; string ans = "", temp; int n; cin >> temp; cin >> n; for(int i=0; i<5; i++) str.push_back(temp[i]); sort(str.begin(), str.end()); ans += str[(n-1)/5]; ans += str[(n-1)%5]; cout << ans << endl; return 0; }
B問題
d[i]がAからBの範囲内かを判定して条件にそってシミュレーションしていきました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define MAX_N 100 int main(void) { int n, a, b, d[MAX_N], now = 0; string temp; cin >> n >> a >> b; for(int i=0; i<n; i++) { cin >> temp >> d[i]; if(d[i] < a) d[i] = a; else if(d[i] > b) d[i] = b; if(temp == "West") d[i] *= -1; now += d[i]; } if(now < 0) cout << "West " << abs(now) << endl; else if(now > 0) cout << "East " << now << endl; else cout << now << endl; return 0; }
C問題
解説を読んでminimax法をつかって実装しました。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 1000000007 #define INF 1e9 int a[3][3], b[2][3], c[3][2]; // minimax法 int minimax(int cnt) { // 最終盤面の得点を求める if(cnt == 9) { int result = 0; for(int i=0; i<2; i++) { for(int j=0; j<3; j++) { if(a[i][j] == a[i+1][j]) result += b[i][j]; } } for(int i=0; i<3; i++) { for(int j=0; j<2; j++) { if(a[i][j] == a[i][j+1]) result += c[i][j]; } } return result; } int turn = cnt%2; int ret = (turn == 0 ? -INF : INF); for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { //cout << a[i][j] << endl; if(a[i][j] == -1) { a[i][j] = turn; // どちらのターンかによってmaxかminを変える if(turn == 0) { ret = max(ret, minimax(cnt+1)); } else { ret = min(ret, minimax(cnt+1)); } a[i][j] = -1; } } } return ret; } int main(void) { // 入力 int sum = 0; for(int i=0; i<2; i++) { for(int j=0; j<3; j++) { cin >> b[i][j]; sum += b[i][j]; } } for(int i=0; i<3; i++) { for(int j=0; j<2; j++) { cin >> c[i][j]; sum += c[i][j]; } } memset(a, -1, sizeof(a)); //minimax法を実行 int ans = minimax(0); cout << ans << endl; cout << sum - ans << endl; return 0; }
D問題
ビットDPの実装で詰まったのでできたら追記します…