読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC028を解いてみた

ABC 競技プログラミング

abc028.contest.atcoder.jp

A問題

 条件に合わせて分岐して出力しました。Perfectのスペル間違えてWA出したので気をつけたい。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  int n;
  cin >> n;

  if(n <= 59) cout << "Bad" << endl;
  else if(n <= 89) cout << "Good" << endl;
  else if(n <= 99) cout << "Great" << endl;
  else cout << "Perfect" << endl;

  return 0;
}

B問題

 文字コードでint(s[i])-int('A')が0,1,2,3,4,5になるのを使いました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  string s;
  cin >> s;

  int a[6]={0};
  for(int i=0; i<s.size(); i++) {
    a[int(s[i])-int('A')]++;
  }

  cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << " " << a[5] << endl;

  return 0;
}

C問題

 5C3なら全探索でも余裕そうなので、1番大きい、2番目に大きい、3番目に大きい数字を記録しつつ全ての組み合わせについて全探索しました。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  int a[5];
  cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

  int ret = 0, max1 = -INF, max2 = -INF, max3 = -INF;
  for(int i=0; i<5; i++) {
    for(int j=i+1; j<5; j++) {
      for(int k=j+1; k<5; k++) {
        ret = a[i] + a[j] + a[k];
        if(ret > max1) {
          max3 = max2;
          max2 = max1;
          max1 = ret;
        } else if(ret > max2) {
          max3 = max2;
          max2 = ret;
        } else if(ret > max3) {
          max3 = ret;
        }
      }
    }
  }

  cout << max3 << endl;

  return 0;
}

D問題

 全ての数字が異なる場合、kが一つとkより小さい数が一つ、kより大きい数が一つになります。3P3=6より(k-1)*(n-k)*6通りのパターンが存在します。同じ数が2つの場合、kが二つとk以外の数が一つになります。3P1=3より(n-1)*3通りのパターンが存在します。同じ数が3つの場合、kが3つになります。これは1通りしかありません。答えは {(k-1)*(n-k)*6+(n-1)*3+1}/(n*n*n) になります。
 数学っぽく解くだけだったのでそんなに手こずらなかったです。doubleとintで何回かWA出したので気をつけたい。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

int main(void)
{
  double n, k;
  cin >> n >> k;
  double ans = (k-1)*(n-k)*6 + (n-1)*3 + 1;
  cout << fixed << setprecision(15) << ans/(n*n*n) << endl;

  return 0;
}