気ままに実装する機械学習

機械学習に興味のある大学院生によるブログです. 機械学習以外のトピック多めです.

MENU

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 . レートがRの人のレートが変動する次のコンテストは何でしょう?

解法

単純な条件分岐で解けます.

#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

問題の概要

  • 英大文字か英小文字からなる文字列Sが与えられる
  • Sが次の条件を全て満たすかどうかを判定する
    • Sの先頭の文字は'A'である.
    • Sの先頭から3文字目と末尾から2文字目の間に'C'がちょうど1個含まれる.
    • それ以外のSの文字は全て小文字である.
  • 以上の条件を満たすとき'AC'、そうでなければ'WA'と出力

解法

条件を上から順に辿っていき、全部満たしたら'AC'を、どれか一つでも条件に反していたら'WA'を出力すれば良いです.

ただ、焦ってしまい正しく条件分岐ができておらず、2回も間違ったソースコードを提出してしまいました...

少し複雑ですが、焦らず一つ一つ条件を書いていけば通せます. (物凄く汚いソースコードですがあげておきます.)

ちなみに、急にfor文をそのまま書いてあるのは、用意していたテンプレートファイルとは違うものをコピーしてしまい、ずっとrepの行で怒られていたからです.

コンテスト中に repが無いファイルを使っていたことに気づかず物凄く焦っていました.

#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

問題の概要

  • 問題集があって、それぞれの問題には難易度に応じて点数がつけられている.
  • i \leq i \leq Dであるiに対して、100i点をつけられた問題がp_i問存在.
  • 問題集を解いて得られるスコアは以下の2つの要素の和で与えられる.
    • 基本スコア : 解いた問題全ての配点の合計.
    • ボーナス : 100i点の問題p_i問を全て解いた場合、ボーナスとして、基本スコアとは別にc_i点獲得できる.
  • 目標スコアがG点以上の人は少なくとも何問の問題を解く必要があるか.

解法

Twitterとかで見ると本問題はいつものC問題より少し難しめみたいですね.

私は、まだ競プロをはじめてまもないため、いつものコンテストとの比較ができないので、Twitterではこういった情報が手に入って楽しいなと感じました.

さて、公式での解答やTwitterでの解答とは違うのですが、一応紹介しておきます.

私は、最近勉強していたDPを用いて解きました.

今回は、どこまでの問題を解いたのかと、それらの問題で何問解いたのかという状態を考えました.

つまり、dp[i][j] : 100i点がつけられている問題までを使ってj問解いたときに獲得できる最大得点

としました.

こうしたとき、最終出力はdp[D][i] \geq Gを最初に満たすiとなります.

(問題は全部で100D点がつけられているものまであり、はじめて目標スコアであるGを超える問題数が答えです.)

ここから漸化式を立てるのですが、今回の問題で気をつけたいのは基本スコアとは別でボーナスがあることです.

このボーナスを考慮に入れながら値を更新していく必要があります.

$$ 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} $$

としました. ただし、0 \leq k \leq p[i]で、100i点の問題のうち解いた数を表しています.

100i点が付いている問題の問題数より多くは解くことが許されていないため、kには条件がついています.

1つめの式は、100i点が付いている問題を全部解いたときに相当します.

2つめの式は、100i点が付いている問題を何問か解いたときに相当します.

3つめの式は、100i点が付いている問題を解かないときに相当します.

#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

問題の概要

  • 文字列TのABC数を以下の条件を全て満たす整数の組み(i,j,k)の個数と定義
    • 1 \leq i <  j < k \leq |T|
    •  T_i = 'A'
    •  T_j = 'B'
    •  T_k = 'C'
  • 与えられる文字列は'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問題は私には無理でした...

公式解説や他の人の解答を見てしっかり勉強します.