AtCoder abc261 参加メモ

B - Tournament Result

全探索で a[i][j], a[j][i] に矛盾がないか調べる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<string> a(n);
  REP(i,n) cin >> a[i];

  bool ok = true;
  REP(i,n) REP(j,n) {
    if (a[i][j] == 'W') {
      if (a[j][i] != 'L') ok = false;
    } else if (a[i][j] == 'L') {
      if (a[j][i] != 'W') ok = false;
    } else if (a[i][j] == 'D') {
      if (a[j][i] != 'D') ok = false;
    }
  }

  cout << (ok ? "correct" : "incorrect") << endl;
  return 0;
}

C - NewFolder(1)

連想配列でこれまで出た文字列をカウントする

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  map<string,int> mp;

  REP(i,n) {
    string s; cin >> s;
    if (mp[s] == 0) cout << s << endl;
    else cout << s << "(" << mp[s] << ")" << endl;
    mp[s]++;
  }
  return 0;
}

D - Flipping and Bonus

周期がありそうで貪欲にできるのかと思ったがだめだった。dfs全探索も間に合わない
DPで dp[i] := カウンタiのときの最大値 を持って更新し、その中で最大の値が答え

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'
using ll = long long;

int main() {
  int n,m; cin >> n >> m;
  vector<int> x(n),b(n+1);
  REP(i,n) cin >> x[i];
  REP(i,m) {
    int c,y; cin >> c >> y;
    b[c] = y;
  }

  vector<ll> dp(n+1,-1);
  dp[0] = 0;
  REP(i,n) {
    vector<ll> p(n+1,-1);
    swap(dp,p);
    REP(cnt,n) {
      // 裏にする処理
      dp[0] = max(dp[0], p[cnt]);
      // 表にする処理
      if (p[cnt] != -1) {
        dp[cnt+1] = max(dp[cnt+1], p[cnt]+x[i]+b[cnt+1]);
      }
    }
  }

  cout << *max_element(dp.begin(),dp.end()) << endl;
  return 0;
}