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の実装で詰まったのでできたら追記します…