AtCoder Beginner Contest 306 に参加しました＆反省会

AtCoder Beginner Contest 306 の振り返り

• C問題まで解くことができた
• A問題：文字列を一文字ずつみていき、その都度2回出力する
• B問題：unsigned long型で2の63乗までの和を計算する(符号付きのlong long 型だと63乗-1が上限なのでWA)
• C問題：連想配列によって数字とその出現位置を記録する。数値と出現位置のペア型をソートして結果を出力する
• D問題：毒状態を管理するd。動的計画法

B問題

atcoder.jp

方針

提出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main () {

  vector<int> A(64);
  for (int i = 0; i < 64; i++) cin >> A[i];

  unsigned long long ans = 0;

  for (int i = 0; i < 64; i++) {
    ans += A[i] * (unsigned long long)pow(2, i);
  }

  cout << ans << endl;

  return 0;
}

解説*1から

実装例

#include<bits/stdc++.h>

using namespace std;

using ull = unsigned long long;

int main() {
    ull ans = 0;
    for (int i = 0; i < 64; i++) {
        ull a;
        cin >> a;
        ans += a << i;
    }
    cout << ans << endl;
}

C問題

atcoder.jp

方針

• 空の配列を用意する
• 数列を走査し、今までに見た部分のなかに各数字が何回現れたのかを別の配列で管理する。今見ている数字をとしたとき、が現れたのが回目であるならば、の末尾にを追加する
• を出力する
  提出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main () {

  int N;
  cin >> N;

  vector<vector<int>> index(N+1);
  for (int i = 0; i < 3*N; i++) {
    int q;
    cin >> q;
    int j = i + 1;
    index[q].push_back(j);
  }

  vector<pair<int, int>> prs;
  for (int i = 1; i <= N; i++) {
    prs.push_back({index[i][1], i});
  }

  sort(prs.begin(), prs.end());
  for (auto pr : prs) cout << pr.second << " ";
  cout << endl;

  return 0;
}

解説*2から

実装例

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> cnt(n + 1), ans;
    for (int i = 0; i < 3 * n; i++) {
        int a;
        cin >> a;
        ++cnt[a];
        if (cnt[a] == 2) ans.push_back(a);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i == n - 1 ? '\n' : ' ');
    }
}

D問題

atcoder.jp

解説*3から

実装例

#include<bits/stdc++.h>

using namespace std;

long long dp[300005][2];

int main(){
  long long n;
  cin >> n;
  vector<long long> x(n),y(n);
  for(long long i=0;i<n;i++){
    cin >> x[i] >> y[i];
  }

  for(long long i=0;i<=n;i++){
    dp[i][0]=-4e18;
    dp[i][1]=-4e18;
  }
  dp[0][0]=0;

  for(long long i=0;i<n;i++){
    if(x[i]==0){
      dp[i+1][0]=max(dp[i][0],max(dp[i][0],dp[i][1])+y[i]);
    }
    else{
      dp[i+1][1]=max(dp[i][1],dp[i][0]+y[i]);
    }

    dp[i+1][0]=max(dp[i+1][0],dp[i][0]);
    dp[i+1][1]=max(dp[i+1][1],dp[i][1]);
  }
  cout << max(dp[n][0],dp[n][1]) << "\n";
  return 0;
}

*1:https://atcoder.jp/contests/abc306/editorial/6599

*2:https://atcoder.jp/contests/abc306/editorial/6599

*3:https://atcoder.jp/contests/abc306/editorial/6606