AtCoder abc251 参加メモ

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) - AtCoder の参加メモ

B - At Most 3 (Judge ver.)

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

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

  vector<int> m(3e6+1);
  REP(i,n) {
    m[a[i]] = 1;
    for(int j = i+1; j < n; j++) {
      m[a[i]+a[j]] = 1;
      for(int k = j+1; k < n; k++) {
        m[a[i]+a[j]+a[k]] = 1;
      }
    }
  }

  int ans = 0;
  for(int i = 1; i <= w; i++) ans += m[i];
  cout << ans << endl;
  return 0;
}

C - Poem Online Judge

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

int main() {
  int n; cin >> n;
  unordered_set<string> st;
  int ans = 1e9+5, mx = -1;

  REP(i,n) {
    string s; int t; cin >> s >> t;
    if (st.count(s)) continue;
    st.insert(s);
    if (mx < t) { mx = t; ans = i+1; }
  }
  cout << ans << endl;
  return 0;
}

D - At Most 3 (Contestant ver.)

パズル。解説読むとなぜこれをコンテスト中に思いつけなかったんだろうという感じの問題。

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

int main() {
  cout << 99*3 << endl;
  REP(i,99) cout << i+1 << " " << (i+1)*1e2 << " " << (i+1)*1e4 << " ";
  return 0;
}

E - Tahakashi and Animals

• DP
• 最初と最後を決め打ちして考える

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
using ll = long long;
const ll LINF = 1e18+5;

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

  vector<vector<ll>> dp(2,vector<ll>(2));
  REP(i,n) {
    vector<vector<ll>> p(2,vector<ll>(2));
    p[0][0] = i == 0 ? LINF : dp[1][0];
    p[1][0] = min(dp[0][0],dp[1][0]) + a[i];

    p[0][1] = dp[1][1];
    p[1][1] = min(dp[0][1],dp[1][1]) + a[i];
    swap(dp,p);
  }

  cout << min(min(dp[0][0],dp[1][0]), dp[1][1]) << endl;
  return 0;
}