AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)
結論
それぞれの竹を、Aに使う、Bに使う、Cに使う、使わないに分類する。その組み合わせを全探索
考えていたこと
本営の解説と同じ方針には行き着いたのですが、実装力が足らず。。。
本番ではbit全探索で実装を試みていたので、後でアプローチしてみようと思います。
#include <bits/stdc++.h> using namespace std; int N, A, B, C; int l[10]; int dfs(int cur, int a, int b, int c) { if (cur == N) { if (min({a, b, c}) > 0) { return abs(a - A) + abs(b - B) + abs(c - C) - 30; } else { return INT_MAX - 10; } } int ret0 = dfs(cur + 1, a, b, c); int ret1 = dfs(cur + 1, a + l[cur], b, c) + 10; int ret2 = dfs(cur + 1, a, b + l[cur], c) + 10; int ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10; return min({ret0, ret1, ret2, ret3}); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> A >> B >> C; for (int i = 0; i < N; ++i) { cin >> l[i]; } int res = dfs(0, 0, 0, 0); cout << res << endl; return 0; }
AtCoder ABC 119 B - Digital Gifts (200 点)
結論
やるだけ。
考えていたこと
精度大丈夫かな?とヒヤヒヤしながらサブミットしましたが、大丈夫でした。
今思えば配列で持つ必要ないですね。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; double x[N]; string u[N]; for (int i = 0; i < N; ++i) { cin >> x[i] >> u[i]; } double res; for (int i = 0; i < N; ++i) { if (u[i] == "JPY") { res += x[i]; } else { res += x[i] * 380000; } } cout << res << endl; return 0; }
AtCoder ABC 119 A - Still TBD (100 点)
結論
やるだけ。
考えていたこと
C++で初のコンテスト参加だったため、C++でsplitってどうやるね~んって混乱し、思いの外時間を要してしまいました。
そもそも文字列比較でOKだし、scanfって手もあったのにな。。。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string S; cin >> S; string res; if (S <= "2019/04/30") { res = "Heisei"; } else { res = "TBD"; } cout << res << endl; return 0; }
AtCoder ABC 118 C - Monsters Battle Royale (300 点)
結論
モンスターの体力すべてについてに最大公約数が答えとなる。
方針
ようやく考察し甲斐のある問題が来たぜ!(震え声)
なんとなく最大公約数じゃね?と思ってサブミットしたらACしちゃった、というのが辛いところ。
実装もシンプルなので、他の人の回答を見てもあまり参考にならないのも難しいところです。
「その時に最も体力が小さいモンスターが殴り続ければ、最後に生き残るモンスターの体力が最小化される」
という仮説を立てます。なんとなく正しい気がします。
この通りに殴り続けると、モンスターの体力が減りゆく様からユークリッドの互除法を感じます。
つまり最小公倍数ってことだな!?ってなります。なりました。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; int A[N]; for (int i = 0; i < N; ++i) { cin >> A[i]; } int res = A[0]; for (int i = 1; i < N; ++i) { res = __gcd(res, A[i]); // i番目までのモンスターの体力の最大公約数 } cout << res << endl; return 0; }
AtCoder ABC 118 B - Foods Loved by Everyone (200 点)
方針
i個目の食べ物が選ばれた回数を保持して、選ばれた回数が人数と等しくなった食べ物の個数が答えになります。
制約がゆるいので、いくつかやりようはありそうです。(i番目の人まで全員が選んだ食べ物を保持する、でも間に合う)
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; // i個目の食べものが選ばれた回数を保持 vector<int> cnt(M, 0); for (int i = 0; i < N; ++i) { int K_i; cin >> K_i; for (int j = 0; j < K_i; ++j) { int A_ij; cin >> A_ij; ++cnt[A_ij - 1]; // 0-indexed } } int res = 0; for (int i = 0; i < M; ++i) { if (cnt[i] == N) { // N回選ばれた食べ物を数え上げ ++res; } } cout << res << endl; return 0; }
AtCoder ABC 118 A - B +/- A (100 点)
そろそろ水色コーダーになりたくなってきたので、ABCの問題をローラーしていきます。(1年以上緑コーダーでステイ中)
ついでにC++への移行を進めていきたい。
方針
やるだけ。
(言う人が言うとハラスメントになるやつ。これは問題のままをコーディングするだけなので問題なしと思われる。)
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // 入力 int A, B; cin >> A >> B; int res; // 回答 if (B % A == 0) { // AがBの約数ならA+B res = A + B; } else { // そうでなければB-A res = B - A; } cout << res << endl; // 回答を出力 return 0; }
競技プログラミングなんて簡単だよ!(私は全くそうは思わないが)
って感じを醸し出していきたいのでコメントはやや冗長に書いていきます。
初投稿です
はじめまして、
a_key_bakoと申します。
ブログを開設してみました。
趣味のプログラミングとか本とかコーヒーとかゲームとか音楽のこととかとかとか書いていきます。