AtCoder Beginner Contest 306

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） - AtCoder

結果

A - Echo : AC(1:22)
B - Base 2 : AC(42:35)(1ペナ)
C - Centers : AC(22:11)
D - Poisonous Full-Course : AC(81:18)(1ペナ)
E - Best Performances : 提出無し

A - Echo

長さ$${N}$$の文字列$${S}$$が与えられるため、全ての文字を$${2}$$連続にして出力する問題

自分の回答

int main(){
  int N;
  string S;
  cin >> N >> S;

  for(char c : S){
    printf("%c%c", c, c);
  }
  printf("\n");
}

そのまま

公式解説

省略

B - Base 2

$${0}$$と$${1}$$からなる長さ$${64}$$の数列$${A=(A_{0},A_{1},…,A_{63})}$$が与えられるため、$${A_{0}2^0+A_{1}2^1+…+A_{63}2^{63}}$$を求める問題

自分の回答

ls = list(map(int,input().split()))

t=1
ans=0
for int in ls:
  ans+=int*t
  t*=2

print(ans)

C++だとオーバーフローの対策が思いつかなかったからPythonを調べて書いた

オーバーフローに気付かずWA

公式解説

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;
}

https://atcoder.jp/contests/abc306/editorial/6599より

unsignedは考えた(自分の場合uint64_t)けどダメだったな？と思ったらprintfのフォーマットが違った
%ldじゃなくて%luなのか

それと2のn乗は1のビットシフトでいけるのか

なるほど

C - Centers

$${1}$$から$${N}$$が全て$${3}$$回ずつ現れる数列が与えられるため、$${2}$$回目が現れた順にその数字を出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> num(N + 1, 0);
  vector<int> ans;
  for(int i = 0; i < 3 * N; i++){
    int a;
    cin >> a;
    num[a]++;
    if(num[a] == 2){
      ans.push_back(a);
    }
  }

  for(int x : ans){
    printf("%d ", x);
  }
  printf("\n");
}

数字iが何回現れたかを記録する配列numを作ってnum[i]が2ならiを答えの配列に入れる
だけど配列作らなくてもそのまま出力して大丈夫だったな

公式解説

省略

D - Poisonous Full-Course

高橋君がレストランで$${N}$$品からなるフルコースを食べる
$${X_{i}}$$が$${0}$$の時、美味しさが$${Y_{i}}$$の解毒剤入りの料理
$${X_{i}}$$が$${1}$$の時、美味しさが$${Y_{i}}$$の毒入りの料理が提供される
高橋君がお腹を壊していない時、解毒剤入りの料理を食べても変化せず、毒入りの料理を食べるとお腹を壊す
高橋君がお腹を壊している時、解毒剤入りの料理を食べるとお腹を壊していない状態になり、毒入りの料理を食べると死ぬ
始め、高橋君がお腹を壊していない状態から、各料理に対して料理を食べるか下げてもらうか選んで死なずに最後まで料理が提供された時、食べた料理の美味しさの総和として考えられる最大値を求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<vector<int64_t>> dp(2, vector<int64_t>(N + 1, 0));
  for(int i = 1; i <= N; i++){
    int x, y;
    cin >> x >> y;
    if(x == 1){
      dp[0][i] = dp[0][i - 1];
      dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + y);
    }
    else{
      dp[1][i] = dp[1][i - 1];
      dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[0][i - 1]) + y);
    }
  }

  printf("%ld\n", max(dp[0][N], dp[1][N]));
}

i=0が壊してないi=1が壊しているでj品目における最大値で動的計画法

解毒剤の時0から食べる選択肢の存在を忘れてWA

公式解説

省略

E - Best Performances

長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$があり、最初全ての項は$${0}$$である
この数列に対し$${A_{X_{i}}}$$を$${Y_{i}}$$に変更する操作を$${Q}$$回行い、操作を行うたびに数値の大きい順に$${K}$$項の和を求める問題

自分の回答

計算量の削減方法が一切思いつかなかった

公式解説

int k;
multiset<int> x,y;
long long s;

void balance(){
  while(x.size()<k){
    auto iy=y.end();iy--;
    x.insert((*iy));
    s+=(*iy);
    y.erase(iy);
  }
  if(x.empty() || y.empty()){return;}
  while(1){
    auto ix=x.begin();
    auto iy=y.end();iy--;
    int ex=(*ix);
    int ey=(*iy);
    if(ex >= ey){break;}
    s+=(ey-ex);
    x.erase(ix);
    y.erase(iy);
    x.insert(ey);
    y.insert(ex);
  }
}

void add(int v){
  y.insert(v);
  balance();
}

void erase(int v){
  auto ix=x.find(v);
  if(ix!=x.end()){ s-=v; x.erase(ix); }
  else{ y.erase(y.find(v)); }
  balance();
}

int main(){
  int n;
  cin >> n >> k;
  vector<int> a(n,0);
  for(int i=0;i<k;i++){ x.insert(0); }
  for(int i=k;i<n;i++){ y.insert(0); }
  s=0;
  
  int q;
  cin >> q;
  while(q>0){
    q--;
    int p,w;
    cin >> p >> w;
    p--;
    add(w);
    erase(a[p]);
    a[p]=w;
    cout << s << "\n";
  }
  return 0;
}

https://atcoder.jp/contests/abc306/editorial/6607より

数列Aと今の総和s、multisetで大きい順にK個の要素を入れるXと他を入れるYを用意
Yに値を入れてAから書き換えられる数値がXにあったら削除してsから引く、Yにあったら削除のみ、その後A書き換え
Xの要素数がK未満ならYの最大をXに移動、Xの最小値<Yの最大値である限りその2つを交換
要素が移動するときその差分をsに足す

こんな感じかな