キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) - AtCoder https://atcoder.jp/contests/abc193?lang=ja
53分でABCDの4完。 Cは典型問題・Dはやるだけ実装面倒。
machikaneさんのキャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)での成績：1256位 パフォーマンス：1380相当 レーティング：1200→1219 (+19) :) #AtCoder #キャディプログラミングコンテスト2021(ABC193) https://atcoder.jp/users/machikane/history/share/abc193?lang=ja
まあ通すべきD問題を通せたから及第点だろう。 ABCD問題を35分で解いて青パフォ取りたかった。
A - Discount
やるだけ。 整数同士を浮動小数点数として演算したいならば、キャストする。 これを忘れないようにしよう。
const long double ans = (1 - (long double)b / a) * 100;
B - Play Snuke
やるだけですね。
- 各店について処理する
- スヌケマシンが売りきれずに買えるか調べる
- $A_i > X_i$なら買える
- スヌケマシンが買えるなら最小金額を更新する
- 最小金額を出力する
code
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
constexpr int INF = 1000000000 + 8;
#define int long long
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n), p(n), x(n);
for (int i = 0; i < n; i++) cin >> a[i] >> p[i] >> x[i];
int ans = INF;
// それぞれの店で買ったときの値段を調べる
for (int i = 0; i < n; i++) {
// 店に着くまでに売り切れるなら値段は調べない
if (!(a[i] < x[i])) continue;
// 最小の値段を更新
ans = min(p[i], ans);
}
cout << (ans != INF ? ans : -1) << "\n";
}
C - Unexpressed
「2以上の整数$a,b$を用いて$ab$と表せる数」はあんまりたくさんないと思う。 表せるものをすべて数えたらよさそう。
- $a$を2から大きくしていく
- $ab$を数える ここで$a2$を既に数えていたら飛ばす
- $a2 \leq N$ならばもう数える数は無いので打ち切る
打ち切らないと$O(N)$になりTLEする。
code
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
// AとBの乗算がオーバーフローするか返す
template <typename T>
constexpr bool isProdOverflow(T a, T b) {
if (b == 0) return false;
return a > numeric_limits<T>::max() / b;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
// $a^b$で表せる値の数
int expressed = 0;
// もう出た値
set<int> pop;
// aをそれぞれ調べる
for (int a = 2; a <= n; a++) {
// もう数える値が無いので計算を打ち切るかどうか
bool cancel = false;
long long x = a;
for (int b = 2; b <= n; b++) {
// オーバーフローするなら打ち切る
// a^bがnを超えるなら打ち切る
if (isProdOverflow(x, a) || x * a > n) {
// a^2がnより大きいなら、aを増やしても表せるようにはならない 計算を打ち切る
cancel = b == 2;
break;
}
x *= a;
// もう出た値なら打ち切る
if (pop.count(x)) break;
// xを数える
expressed++;
pop.insert(x);
}
if (cancel) break;
}
// $a^b$で表せない値の数
const int ans = n - expressed;
cout << ans << "\n";
}
D - Poker
引くカードを全探索したら計算量$O(K2)$でTLEする。 引くカードの数字を全探索したら計算量が小さくなる。
- 高橋が引く数と青木が引く数を全探索する
- 引くカードの組に対してその勝敗を計算する
- 引くカードの組に対してその事象数を計算する
- 高橋が勝つ事象数を計算する
- 確率を計算する
code
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
// $a^r$ 整数演算する
constexpr long long powi(long long a, long long r) {
int ans = 1;
for (int i = 0; i < r; i++) {
ans *= a;
}
return ans;
}
// 文字列sに登場する数字を数えて配列に入れる
array<int, 10> countNumber(string s) {
array<int, 10> hand{};
for (auto &&i : s) {
if ('0' <= i && i <= '9') {
hand[i - '0']++;
}
}
return hand;
}
// 得点を計算する
int getScore(array<int, 10> hand) {
int score = 0;
for (int i = 0; i < 10; i++) {
score += i * powi(10, hand[i]);
}
return score;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(16);
int k;
cin >> k;
string s, t;
cin >> s >> t;
// 4枚目までの手札の数字を配列にいれる
const auto taka4 = countNumber(s), aoki4 = countNumber(t);
// 高橋が引く数と青木が引く数を全探索する
// 引くカードの組に対してその勝敗を計算する
// 引くカードの組に対してその事象数を計算する
// 高橋が勝つ事象数を計算する
// 確率を計算する
// 高橋が勝つ引くカードの組を調べておく
// win_condition[i][j]: 高橋,青木のカードがi,jのとき高橋が勝てるか
array<array<bool, 10>, 10> win_condition{};
// 高橋がi、青木がjを引く
for (int i = 1; i < 10; i++) {
// 高橋の手札
auto taka = taka4;
taka[i]++;
for (int j = 1; j < 10; j++) {
// 青木の手札
auto aoki = aoki4;
aoki[j]++;
// 得点
const int taka_score = getScore(taka), aoki_score = getScore(aoki);
win_condition[i][j] = taka_score > aoki_score;
}
}
// iのカードが山札と5枚目のカードに何枚あるか調べておく
// deck[i]: iのカードが山札と5枚目のカードに何枚あるか
array<int, 10> deck{};
for (int i = 0; i < 10; i++) {
deck[i] = k - taka4[i] - aoki4[i];
}
// 全事象・高橋が勝つ事象
int all_events = 0, win_events = 0;
// 高橋がi、青木がjを引く
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
// 引いたカードの組がありえない組み合わせなら処理を飛ばす
if (deck[i] == 0 && deck[j] == 0) continue;
if (i == j && deck[i] <= 1) continue;
// 引いたカードの組がこうなる事象
int events = deck[i] * deck[j];
if (i == j) events = deck[i] * (deck[i] - 1);
all_events += events;
if (win_condition[i][j]) win_events += events;
}
}
// 事象数から確率を計算する
const long double ans = (long double)win_events / all_events;
cout << ans << "\n";
}
コーディング環境改善
整数べき乗
整数のべき乗を整数型として計算するスニペットを登録した。
// 整数のべき乗を整数型として計算する // b: 底 // e: べき指数 constexpr long long powi(long long b, int e) { long long ans = 1; for (int i = 0; i < e; i++) ans *= b; return ans; }
スニペットの登録はsnippet generator使うと楽です。
入力受け取りスニペットを修正
次が今まで使っていた変数入力スニペット。 変数型→変数名を入力する。
"inputval": { "body": [ "${1:int} ${2:n};", "cin >> $2;", "$0" ], "description": "inputval", "prefix": "inputval" }, "inputvals2": { "body": [ "${1:int} ${2:n}, ${3:m};", "cin >> $2 >> $3;", "$0" ], "description": "inputvals2", "prefix": "inputvals2" },
変数型は九分九厘int型だから型を指定しないように修正した。
"inputint": { "body": [ "int ${1:n};", "cin >> $1;", "$0" ], "description": "inputint", "prefix": "inputint" }, "inputints2": { "body": [ "int ${2:n}, ${3:m};", "cin >> $2 >> $3;", "$0" ], "description": "inputints2", "prefix": "inputints2" },