AtCoder Beginner Contest 046

[TakefumiYamamura]

http://abc046.contest.atcoder.jp/

[TakefumiYamamura]

D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 300 点

問題文

シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。 このゲームは N ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。

(※) 各ターンの後で、(今までにパーを出した回数)≦(今までにグーを出した回数)　を満たす

このゲームでの各プレイヤーの得点は、(勝ったターンの数) − (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す N ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 s で与えられます。 s の i(1≦i≦N) 文字目が gのときは i ターン目でTopCoDeerくんがグーを出すことを、 pのときはパーを出すことを表します。

制約

1≦N≦105 N=|s| s の各文字はgかp s で表される手は、条件(※)を満たしている

note

最初dpとかで解くのかなぁと思ったら数学の問題だったの巻。

#include <iostream>
#include <vector>
#include <string>

using namespace std;
#define ll long long

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    string s;
    cin >> s;

    ll ans = 0;

    ll len = s.length();

    for (int i = 0; i < len; ++i)
    {
        if(s[i] == 'p'){
            ans--;
        }
    }

    cout << ans + len/2  << endl;
}

[TakefumiYamamura]

C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 300 点

問題文

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは N 回画面を見て、 i(1≦i≦N) 回目に見たときに表示されている比は Ti:Ai でした。ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 N 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

制約

1≦N≦1000 1≦Ti,Ai≦1000(1≦i≦N) Ti と Ai は互いに素 (1≦i≦N) 答えが 1018 以下になることは保証されている

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main(){
    int n;
    ll t[100100];
    ll a[100100];
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> t[i] >> a[i];
    }

    for (int i = 1; i < n; ++i)
     {
        ll tmp_t = t[i];
        ll tmp_a = a[i];
        if(t[i-1] > t[i] || a[i-1] > a[i]){
            ll tmp_mul = max( (t[i-1] - 1)/ t[i] + 1, (a[i-1] - 1) / a[i] + 1);

            t[i] *= tmp_mul;
            a[i] *= tmp_mul;

        }

     }

     cout << t[n-1] + a[n-1] << endl;

}