seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC141

atcoder.jp

所要時間

  • 30分ABC3完答,Cで一回WA,D問お手上げ

解答メモ

A

  • Weathering with you.
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S;
  cin >> S;

  if(S == "Sunny"){
    cout << "Cloudy" << endl;
  }else if(S == "Cloudy") {
    cout << "Rainy" << endl;
  }else{
    cout << "Sunny" << endl;
  }
  
  return 0;
}

B

  • そのまま解く
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S;
  cin >> S;

  bool result = true;
  // odd
  for(int i=0; i < S.length(); i+=2){
    if(!(S[i] == 'R' || S[i] == 'U' || S[i] == 'D')){
      result = false;
    }
  }

  if(!result){
    cout << "No" << endl;
    return 0;
  }

  if(S.length() == 1){
    cout << "Yes" << endl;
    return 0;
  }

  // even
  for(int i=1; i < S.length(); i+=2){
    if(!(S[i] == 'L' || S[i] == 'U' || S[i] == 'D')){
      result = false;
    }
  }

  if(result){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

C

  • 問題をもし1問も解答できなかった場合の最終スコアはK-Q と考えると,K-Qに正答できた問題数を足して1以上ならOKと読み替えられるので  \mathcal{O} \left(Q+N\right)で解ける
  • 一回なぜかWA食らったが,if(score[i] + K - Q > 0) でオーバーフローしたためと考えられる(全部 long longで宣言するように修正しただけでACになった)
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll N, Q, K;

  cin >> N >> K >> Q;

  ll score[100001];
  REP(i, N+1) {score[i] = 0;}

  int tmp_a;
  REP(i, Q) {
    cin >> tmp_a;
    ++score[tmp_a];
  }

  for(long i=1; i<=N; ++i){
    if(score[i] + K - Q > 0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }

  return 0;
}

D

  • 以下が分からなかった
    • どういう戦略で割引券を使うのが最適か
      • 値段でソートして一番高いやつから多く使って行けばいいんじゃね?と思って実装してみたが違った
  • 解説PDF

    • 以下が分からなかった
      • 最初の定理については何となく分かる
      • \lfloor \frac {X} {2^{Y}} \rfloor = \lfloor \lfloor X / 2 \rfloor / 2 \rfloor \dots は毎回の除算で小数点以下を切り捨てているので雰囲気は分かる
      • しかしこの定理に基づいてどう実装するか?priority_queueの使い方知らないマン
  • 解説動画 youtu.be

    • めちゃくちゃわかりやすくて感動した.↑の定理はたしかに2進数で考えると「そりゃそうやな」と腑に落ちる(けど数学的に証明できないと使うのは怖い).
    • 普通に考えれば「その時点で一番高いものを半額にしていけばよい」というのは確かにそうなのでそう解けば良かったが,↑の定理が思いつかないと厳しいか,あるいは「このような定理が成り立つ.知らんけど.」で,一か八かでこの方針で解くことになりそうではある.D問題解けた人はどうやって導いたんだこれ?

santa98.hatenablog.com

bondo.hateblo.jp

  • みんな大して苦労せずに解いてるところを見るに,競プロ勢にとってはこの程度の問題は普通なのかもしれない...
  • ともかくpriority_queue使えないと同様の問題で詰むのがよくわかったので,使い方と時間計算量をちゃんと調べておく必要がある

  • 解説見て書いた解答

    • priority_queueの時間計算量は,pushpop \mathcal{O} (\log N), top \mathcal{O}(1)らしい
    • よって時間計算量は  \mathcal{O} (M \times 2 \times \log N)
#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M;
  priority_queue<ll> A;
  ll tmp_a;

  cin >> N >> M;
  REP(i, N) {
    cin >> tmp_a;
    A.push(tmp_a);
  }

  REP(i, M) {
    tmp_a = A.top();
    A.pop();
    A.push(floor(tmp_a / 2));
  }

  ll result = 0;
  REP(i, N){
    result += A.top();
    A.pop();
  }

  cout << result << endl;

  return 0;
}