AtCoder ABC173 反省会 [A,B,C,D完][C++]

こんにちは。ABC173でした。

ギリチョンDまで解けました。

A

int main(){
  int n;cin>>n;
  for(int i=0; i<20; i++){
    if(n<=i*1000){
      cout<<(i*1000)-n<<endl;
      return 0;
    }
  }
}

なんかまどろっこしいけど通るから…………

B

B - Judge Status Summary

int main(){
  int N;cin>>N;
  int ac=0, wa=0, tle=0, re=0;
  rep(n,N){
    string s;cin>>s;
    if(s=="AC")ac++;
    if(s=="WA")wa++;
    if(s=="TLE")tle++;
    if(s=="RE")re++;
  }

  cout<<"AC x "<<ac<<endl;
  cout<<"WA x "<<wa<<endl;
  cout<<"TLE x "<<tle<<endl;
  cout<<"RE x "<<re<<endl;
}

はい。

C

C - H and V

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

int main(){
  int H,W,K;cin>>H>>W>>K;
  vector<string> c(H);
  rep(i,H)cin>>c[i];
  int ans=0;

  for(int i=0; i<(1<<H); i++){
    for(int j=0; j<(1<<W); j++){
      
      int cnt = 0;
      for(int h=0; h<H; h++){
        for(int w=0; w<W; w++){
          if(i&(1<<h) || j&(1<<w))continue;
          if(c[h][w]=='#')cnt++;
        }
      }

      if(cnt==K)ans++;
    }
  }

  cout<<ans<<endl;
}

制約が小さいのでbit全探索しました。iとjのループで行と列それぞれ消すところを指定。

例えばi=001010(2進数)のときは「2行目と4行目を消去」を表す。

hとwのループで「消去する行or列はcontinue（無視）、それ以外#があったらカウント」としています。

計算量的には $O(HW 2^{H+W})$ かな？

D

D - Chat in a Circle

まず、 $N$ 人をフレンドリーさ降順に（大きい方が先頭）ソートする。以後ソート済み順序で扱う。

最初に先頭の人をサークルに入れると、「心地よさ $A_0$ を得られるエリア」が1つできる。

それ以降は、$i$ 人目を入れるごとに「心地よさ最大のエリアを1つ消費して」「心地よさ $A_i$ を得られるエリア」が2つ（$i$ 人目の両隣に）できる。とすれば最適。

フレンドリーさが大きい人から順に処理する事で、「エリア」をキューで管理できる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define all(v) (v).begin(), (v).end()

int main(){
  int N;cin>>N;
  vector<int> A(N);
  rep(i,N)cin>>A[i];
  sort(all(A), greater<int>());
  queue<int> que;
  ll ans = 0;
  rep(i,N){
    if(i==0){
      que.push(A[i]);
      continue;
    }else{
      ans+= que.front();
      que.pop();
      que.push(A[i]);
      que.push(A[i]);
    }
  }
  cout<<ans<<endl;
}