AtCoder Beginner Contest 104に参加しました
久しぶりにリアルタイムでAtCoderに参加したのでその感想でも書いておこうかと思います.
今回参加したコンテストはAtCoder Beginner Contest 104です
問題のタイトルは以下のようになっています.
- A . Rated for Me
- B . AcCepted
- C . All Green
- D . We Love ABC
A. Rated for Me
問題の概要
次に開催されるコンテストABCではレートが1200未満の人のレートが変動する.
その次に開催されるコンテストARCではレートが2800未満の人のレートが変動する.
そのさらに次に開催されるコンテストAGCでは全ての人のレートが変動する.
Q . レートが
の人のレートが変動する次のコンテストは何でしょう?
解法
単純な条件分岐で解けます.
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <stack> #include <queue> #include <set> #include <cstring> using namespace std; // ascending order #define vsort(v) sort(v.begin(), v.end()) // descending order #define vsort_r(v) sort(v.begin(), v.end(), greater<int>()) // ascending order #define asort(array, N) sort(array, array + N) // descending order #define asort_r(array, N) sort(array, array + N, greater<int>()) #define vunique(v) v.erase(unique(v.begin(), v.end()), v.end()) #define mp make_pair #define ts(x) to_string(x) typedef long long ll; typedef pair<int, int> P; const ll INF = 1e18; int main(){ cin.tie(0); ios::sync_with_stdio(false); int r; cin >> r; if(r < 1200) cout << "ABC" << endl; else if (r < 2800) cout << "ARC" << endl; else cout << "AGC" << endl; }
B. AcCepted
問題の概要
- 英大文字か英小文字からなる文字列
が与えられる
である.
がちょうど1個含まれる.
- それ以外の
- 以上の条件を満たすとき
、そうでなければ
と出力
解法
条件を上から順に辿っていき、全部満たしたらを、どれか一つでも条件に反していたら
を出力すれば良いです.
ただ、焦ってしまい正しく条件分岐ができておらず、2回も間違ったソースコードを提出してしまいました...
少し複雑ですが、焦らず一つ一つ条件を書いていけば通せます. (物凄く汚いソースコードですがあげておきます.)
ちなみに、急に文をそのまま書いてあるのは、用意していたテンプレートファイルとは違うものをコピーしてしまい、ずっと
の行で怒られていたからです.
コンテスト中にが無いファイルを使っていたことに気づかず物凄く焦っていました.
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <stack> #include <queue> #include <set> #include <cstring> using namespace std; // ascending order #define vsort(v) sort(v.begin(), v.end()) // descending order #define vsort_r(v) sort(v.begin(), v.end(), greater<int>()) // ascending order #define asort(array, N) sort(array, array + N) // descending order #define asort_r(array, N) sort(array, array + N, greater<int>()) #define vunique(v) v.erase(unique(v.begin(), v.end()), v.end()) #define mp make_pair #define ts(x) to_string(x) typedef long long ll; typedef pair<int, int> P; const ll INF = 1e18; int main(){ cin.tie(0); ios::sync_with_stdio(false); string s; cin >> s; int n = s.size(); if(s[0] != 'A') { cout << "WA" << endl; return 0; } int count = 0; int idx = 0; for(int i = 2; i < n - 1; i++) { if(s[i] == 'C') { count++; idx = i; } } if(count != 1) { cout << "WA" << endl; return 0; } for(int i = 1; i < n; i++) { if(i == idx) continue; if('A' <= s[i] && s[i] <= 'Z') { cout << "WA" << endl; return 0; } } cout << "AC" << endl; }
C. All Green
問題の概要
- 問題集があって、それぞれの問題には難易度に応じて点数がつけられている.
である
に対して、
点をつけられた問題が
問存在.
- 問題集を解いて得られるスコアは以下の2つの要素の和で与えられる.
- 基本スコア : 解いた問題全ての配点の合計.
- ボーナス :
点獲得できる.
- 目標スコアが
点以上の人は少なくとも何問の問題を解く必要があるか.
解法
Twitterとかで見ると本問題はいつものC問題より少し難しめみたいですね.
私は、まだ競プロをはじめてまもないため、いつものコンテストとの比較ができないので、Twitterではこういった情報が手に入って楽しいなと感じました.
さて、公式での解答やTwitterでの解答とは違うのですが、一応紹介しておきます.
私は、最近勉強していたDPを用いて解きました.
今回は、どこまでの問題を解いたのかと、それらの問題で何問解いたのかという状態を考えました.
つまり、
としました.
こうしたとき、最終出力はを最初に満たす
となります.
(問題は全部で点がつけられているものまであり、はじめて目標スコアである
を超える問題数が答えです.)
ここから漸化式を立てるのですが、今回の問題で気をつけたいのは基本スコアとは別でボーナスがあることです.
このボーナスを考慮に入れながら値を更新していく必要があります.
$$ dp[i + 1] = \begin{cases} max(dp[i + 1][j], dp[i][j - k] + 100 (i + 1) \times k + c[i]) & j \geq k かつ k = p[i]\\ max(dp[i + 1][j], dp[i][j - k] + 100 (i + 1) \times k) & j \geq k かつ k \neq p[i] \\ max(dp[i + 1][j], dp[i][j]) \end{cases} $$
としました. ただし、]で、
点の問題のうち解いた数を表しています.
点が付いている問題の問題数より多くは解くことが許されていないため、
には条件がついています.
1つめの式は、点が付いている問題を全部解いたときに相当します.
2つめの式は、点が付いている問題を何問か解いたときに相当します.
3つめの式は、点が付いている問題を解かないときに相当します.
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <stack> #include <queue> #include <set> #include <cstring> using namespace std; // ascending order #define vsort(v) sort(v.begin(), v.end()) // descending order #define vsort_r(v) sort(v.begin(), v.end(), greater<int>()) #define vunique(v) unique(v.begin(), v.end()) #define mp make_pair #define ts(x) to_string(x) #define rep(i, a, b) for(int i = (int)a; i < (int)b; i++) #define repm(i, a, b) for(int i = (int)a; i > (int)b; i--) #define bit(a) bitset<8>(a) typedef long long ll; typedef pair<int, int> P; const ll INF = 1e18; int main(){ cin.tie(0); ios::sync_with_stdio(false); int d, g; cin >> d >> g; int p[d], c[d]; int num = 0; rep(i, 0, d) { cin >> p[i] >> c[i]; num += p[i]; } int dp[d + 1][num + 1]; rep(i, 0, d + 1) rep(j, 0, num + 1) dp[i][j] = 0; rep(i, 0, d) { rep(j, 0, num + 1) { rep(k, 0, p[i] + 1) { if(j >= k) { if(k == p[i]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k] + 100 * (i + 1) * k + c[i]); dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k] + 100 * (i + 1) * k); } else dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); } } } rep(i, 0, num + 1) { if(dp[d][i] >= g) { cout << i << endl; return 0; } } }
D. We Love ABC
問題の概要
- 文字列
のABC数を以下の条件を全て満たす整数の組み
の個数と定義
<
<
- 与えられる文字列は'A','B','C','?'のいずれか.
- '?'をそれぞれ'A','B','C'に置き換えて新しい文字列が作られる.
- これらの文字列全てのABC数を求めよ.
解法(解けませんでした)
コンテストではTLEで終わってしまったので、正解の解法をここで紹介できませんが、記録として残しておきたいと思います.
正解のアルゴリズムが知りたいという方はこれより下を見ても何も得られないので、ブラウザバックしてください.
さて、私はTLE覚悟で深さ優先探索を使って実装しました.
どうせDP何だろうなと思ってはいたのですが、とりあえず手は動かそうと思い、深さ優先探索で解きました. (もちろん結果はTLEでした.)
各'?'に対して'A','B','C'の3通りで置き換えることができるので、ひたすらどんどん置き換えて全パターン列挙していきます.
'?'の数と置き換えた回数が一致したら一番深くまで探索したということにし、一つ前に戻って別の文字に置き換えていきます.
例えば、'??'に対しては、'A?' -> 'AA'('?'の数と置き換えた回数が一致したのでABC数を求めて一つ前に戻る) -> 'AB' -> 'AC' -> 'BA' -> ... -> 'CC'となります.
これは単純な深さ優先でかけます.
一応書いたのであげておきます.
8問ACで残りはTLEでした...
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <stack> #include <queue> #include <set> #include <cstring> using namespace std; // ascending order #define vsort(v) sort(v.begin(), v.end()) // descending order #define vsort_r(v) sort(v.begin(), v.end(), greater<int>()) #define vunique(v) unique(v.begin(), v.end()) #define mp make_pair #define ts(x) to_string(x) #define rep(i, a, b) for(int i = (int)a; i < (int)b; i++) #define repm(i, a, b) for(int i = (int)a; i > (int)b; i--) #define bit(a) bitset<8>(a) typedef long long ll; typedef pair<int, int> P; const ll INF = 1e18; int checkABC(string s) { int count = 0; rep(i, 0, s.size()) { rep(j, i + 1, s.size()) { rep(k, j + 1, s.size()) { if(s[i] == 'A' && s[j] == 'B' && s[k] == 'C') count++; } } } return count; } int main(){ cin.tie(0); ios::sync_with_stdio(false); string s; cin >> s; int Q; rep(i, 0, s.size()) { if(s[i] == '?') Q++; } if(Q == 0) { cout << checkABC(s) << endl; return 0; } queue <string> q; char dx[3] = {'A', 'B', 'C'}; string init[3] = {"A", "B", "C"}; int ans = 0; int mod = 1e9 + 7; rep(i, 0, 3) { q.push(init[i]); string tmpString; while(q.size()) { tmpString = q.front(); q.pop(); if(tmpString.size() == Q) { string tmp = s; int k = 0; rep(j, 0, s.size()) { if(s[j] == '?') { tmp[j] = tmpString[k]; k++; } } ans += checkABC(tmp) % mod; continue; } rep(i, 0, 3) { string newString = tmpString + dx[i]; q.push(newString); } } } cout << ans << endl; }
感想
久しぶりのリアルタイムでのコンテスト参加だったのですが、いつもより少し難しめと言われているC問題を解けたのでとても嬉しいです.
少し前までDPなんて一生できるようにならないと思ってたのですが、こうやってリアルタイムでのコンテストでもDPを使えるようになりました. (今回たまたまできただけですが...)
なので、まだDPってなに？って思っている方は、こちらの記事を一通り実装して見るといいと思います. qiita.com
今回のD問題は私には無理でした...
公式解説や他の人の解答を見てしっかり勉強します.
