AtCoder Beginner Contest 085

はじめに

AtCoderのBeginner Contest 085の解説と勉強です。
問題はこちらを参照してください。

A - Already 2018

文字列を入れ替えるだけの問題。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

string str;

int main() {
  cin >> str;

  if (str.substr(0, 4) == "2017") {
    str[3] = '8';
  }

  cout << str << endl;
  return 0;
}

改善点

特になし

B - Kagami Mochi

「どの餅もその真下の餅より直径が小さい」ということなので、「大きさの違う餅が何種類あるか」という問題に帰着できます。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int N;
int d[100];
int num = 0;

int main() {
  cin >> N;
  rep(i, N) {
    cin >> d[i];

    bool check = true;
    rep(j, i) {
      if (d[i] == d[j]) {
        check = false;
        break;
      }
    }

    if (check) num++;
  }

  cout << num << endl;
  return 0;
}

改善点

特になし

C - Otoshidama

指定されたお札の枚数ちょうどで、指定された金額を決定する問題です。

指針としては、まず初めに一番少ない枚数で指定された金額を作り、そのあとに両替を繰り返します。

この両替では、大きなお札から段々と崩す（＝お札の枚数が増える）両替だけを行います。したがって、両替としてあり得るのは「10000円→5000円」「5000円→1000円」「10000円→1000円」の3つの選択肢があります。

しかし、「10000円→1000円」の両替は、「10000円→5000円」と「5000円→1000円」の両替で表現できます。したがって、考える必要がありません。

さらに、両替によって両替によって減る枚数が大きい「5000円→1000円」から順番に両替します。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int N, Y;
int _N;
int x = 0, y = 0, z = 0;

int main() {
  cin >> N >> Y;

  // 最小の枚数を決定する
  x = Y / 10000;
  Y = Y % 10000;
	
  y = Y / 5000;
  Y = Y % 5000;
	
  z = Y / 1000;
  Y = Y % 1000;
	
  if (Y != 0) { x = -1, y = -1, z = -1; }
  else {
    while (x + y + z != N) {
      if (N - (x + y + z) >= 4 && y >= 1) {
        z += 5;
        y -= 1;
      }
      else if (N - (x + y + z) >= 1 && x >= 1) {
        y += 2;
        x -= 1;
      }
      else {
        x = -1, y = -1, z = -1;
        break;
      }
    }
  }

  cout << x << " " << y << " " << z << endl;
  return 0;
}

改善点

特になし

D - Katana Thrower

複数個ある刀が与えられ、それぞれの刀に攻撃方法が二つあり、「振る」は何回もでき、「投げる」は1回しかできなく、それ以降その刀は使用できなくなる状態で、最速で魔物を倒す問題。

複数回できる「振る」攻撃は、最も強い「振る」攻撃を持つ刀で行うのが最も効率的です。

一方で、1回しかできない「投げる」攻撃は、最も強い「振る」攻撃力以上の攻撃力を持っている場合は、使用する方が効率的です。

しかし、「振る」より「投げる」の方が攻撃力が強いという制約から、最も強い「振る」攻撃力を持つ刀によって「振る」攻撃をしている時、もしその刀を「投げる」ことで魔物を倒すことができる場合、その刀は「投げる」べきです。したがって、最後の一撃は最も強い「振る」攻撃力を持つ刀による「投げる」攻撃です。さらに、ここで重要なことは攻撃が決まっている場合、攻撃の順番は関係ないということです。

以上のことから、まず「投げる」の攻撃力に基づいてソートをし、最も強い「振る」攻撃より強い「投げる」攻撃を強い順に行います。攻撃の順番は関係ないことから、この時点で、最も強い「振る」攻撃を持つ刀の「投げる」攻撃が先に行われているようになってしまっていますが、関係ありません。最後は残った魔物のHPに対して、最も強い「振る」攻撃を繰り返すだけです。

注意したいのは、実際に戦う時には最も強い「振る」攻撃力を持つ刀の「投げる」攻撃であるということです。

自分の解答

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<numeric>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
  int num = 0;

  int N, H;
  cin >> N >> H;

  vector<pii> ab(N);
  int max_a = 0, max_ai;

  REP(i, N) {
    cin >> ab[i].first >> ab[i].second;
    if (max_a < ab[i].first) {
      max_a = ab[i].first;
      max_ai = i;
    }
  }

  sort(ab.begin(), ab.end(), [](const pii x, const pii y) { if (x.second == y.second) { return x.first < y.first; } else { return x.second > y.second; }});

  REP(i, N) {
    if (max_a < ab[i].second) {
      num++;
      H -= ab[i].second;
      if (H <= 0) break;
    }
    else break;
  }

  if (H <= 0) cout << num << endl;
  else cout << num + (H + max_a - 1) / max_a << endl;

  return 0;
}

改善点

特になし
この問題のようにあくまでも順番に行う操作であっても、順番を無視できる可能性がある問題はよく出てきますね。