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; }
改善点
特になし
この問題のようにあくまでも順番に行う操作であっても、順番を無視できる可能性がある問題はよく出てきますね。