AtCoder Beginner Contest 027

[TakefumiYamamura]

http://abc027.contest.atcoder.jp/

[TakefumiYamamura]

C - 倍々ゲーム

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

問題文

高橋君と青木君が以下のような二人ゲームで勝負する。

まず、正の整数 N が与えられる。 また、変数 x を 1 に初期化する。高橋君から始め、高橋君と青木君が交互に次の操作を行う。

x の値を 2x または 2x+1 に置き換える。 x が N よりも大きくなったとき、最後に操作を行った人が負けである。

二人が最善を尽くすとき、どちらが勝つか求めよ。

note

数学

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

#define ll long long

using namespace std;

int main(){
    ll n;
    cin >> n;

    ll depth  = 0;

    for (ll i = n; i > 0 ; i /= 2)
    {
        depth++;
    }
    ll x = 1;
    ll count = 0;
    // cout << depth << endl;

    if(depth % 2 == 0){
        while(x <= n){
            if(count % 2 == 0){
                x  = x * 2;
            } else {
                x = x * 2 + 1;
            }
            count ++;
        }
    } else {
        while(x <= n){
            if(count % 2 == 0){
                x  = x * 2 + 1;
            } else {
                x = x * 2;
            }
            count ++;
        }       
    }

    if(count % 2 == 0){
        cout << "Takahashi" << endl;
    }else{
        cout << "Aoki" << endl;
    }
}

[TakefumiYamamura]

D - ロボット

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

問題文

数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。

このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から末尾まで順に実行される。

M : 正または負の好きな向きに、距離 1 だけ移動する。

• : 今の座標を x とすると、幸福度が +x だけ変化する。
• : 今の座標を x とすると、幸福度が −x だけ変化する。 命令列を実行し終えた後、 ロボットは原点に戻っていなければならない 。 命令列を実行している間、ロボットの座標および幸福度は負になり得る。

最終的な幸福度を最大化するようにロボットが移動したとき、最終的な幸福度を求めよ。

note

動的計画法かと最初おもった、でも部分点しかそれじゃとんれい。 結局数学ひらめき問題だった。このあたりの勘は勝負で鍛えるしかないのかなぁ

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

#define ll long long

using namespace std;

int main(){
    string s;
    cin >> s;
    ll imos = 0;
    vector<ll> m;

    for (int i = 0; i < s.length(); ++i)
    {
        if(s[i] == '+'){
            imos++;
        } else if (s[i] == '-') {
            imos--;
        } else {
            m.push_back(imos);
        }
    }

    sort(m.begin(), m.end());

    ll ans = 0;
    for (int i = 0; i < m.size(); ++i)
    {
        if(i < m.size()/2){
            ans -= m[i]; 
        }else{
            ans += m[i];
        }
    }

    cout << ans << endl;

}