C - 数列ゲーム

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

問題文

高橋君と青木君は長さ N の数列 S を用いたゲームを行う。

ゲームは高橋君の手番と青木君の手番 1 回ずつからなる。

ゲームは以下の要領で行われる。

最初に高橋君が数列の要素のうち 1 つに丸をつける。次に青木君が数列の要素で高橋君が丸を付けなかったもののうち 1 つに丸をつける。高橋君と青木君が丸を付けた 2 つの要素に対して、その 2 つの要素およびそれらの間にあるすべての要素を残して、それ以外の要素をすべて削除する。残った数列を T と置く。数列 T のうち、数列 T 内で左から奇数番目の要素の合計が高橋君の得点、偶数番目の要素の合計が青木君の得点となる。青木君は、丸を付けられる要素の中で、青木君が得点を最も多く得られる要素に丸を付ける。そのような要素が複数あるならばそれらのうち最も左側にある要素に丸を付ける。

高橋君は青木君の丸の付け方を知っている。高橋君が得られる得点として考えられる得点の最大値を求めよ。

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

int x[51];

struct set
{
    ll tak, ao;
};

ll solve(int a, int n){
    set max = {-50*n, -50*n};
    for (int i = n-1; i >= 0; --i)
    {
        if(a == i) continue;
        set tmp = {0, 0};

        int start, finish;
        if(i < a){
            start = i;
            finish = a; 
        } else{
            finish = i;
            start = a;
        }

        while(start <= finish){
            if( (finish - start) % 2 == 0){
                tmp.tak += x[finish];
            }else{
                tmp.ao += x[finish];
            }
            finish--;
        }
        if(tmp.ao >= max.ao) max = tmp;
    }
    return max.tak;
}

int main(){
    int n;

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x[i];
    }

    ll ans = -50*n;
    for (int i = 0; i < n; ++i)
    {
        ans = max(ans, solve(i, n));
    }

    cout << ans << endl;

}

D - 語呂合わせ

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

問題文

日本には数字と短い文字列を対応させる語呂合わせの文化がある。

このことに興味を持った高橋君は、1 以上 K 以下の数字のみからなる正整数 v1, v2, ... , vN とそれぞれの正整数に対応する文字列 w1, w2, ... , wN の組 (v1, w1), (v2, w2), ... , (vN, wN) から、どの数字がどの文字列に対応しているかを推論することにした。

すなわち、以下の条件を満たす K 個の文字列 s1, s2, ... , sK を求めたい。

1≦i≦K を満たす任意の整数 i に対して、1≦|si|≦3 を満たす。 1≦i≦N を満たす任意の整数 i に対して、整数 vi を桁ごとに分解した際に得られる数字が上から順に d1, d2, ... , dl としたとき、文字列 sd1, sd2, ... , sdl をこの順に連結した文字列が wi に等しい。 K 個の文字列 s1, s2, ... , sK を出力するプログラムを作成せよ。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#define ll long long
#define MAX_N 51
using namespace std;
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 k, n;
vector<string> val;
vector<string> str;
int len[MAX_N];
string ans[10];

//指定した数で文字列の長さがあってるか
bool check_num(){
    for (int i = 0; i < n; ++i)
    {
        int count = 0;
        for (int j = 0; j < val[i].length(); ++j)
        {
            int tmp = val[i][j] - '1';
            count += len[tmp];
        }
        if(count != str[i].length()) return false;
    }
    return true;
}

//中身に矛盾がないか
bool check_contents(){
    string ans[10];
    for (int i = 0; i < n; ++i)
    {
        int count = 0;
        for (int j = 0; j < val[i].length(); ++j)
        {
            int tmp = val[i][j] - '1';
            string tmp_str;
            for (int l = count; l < count + len[tmp]; ++l)
            {
                tmp_str.push_back(str[i][l]);
            }
            if(ans[tmp].empty()){
                ans[tmp] = tmp_str;
            } else {
                if(ans[tmp] != tmp_str) return false;
            }
            count += len[tmp];
        }
    }

    for (int i = 0; i < k; ++i)
    {
        cout << ans[i] << endl;
    }
    return true;
}

int main(){
    cin >> k >> n;
    for (int i = 0; i < n; ++i)
    {
        string v,w;
        cin >> v >> w;
        val.push_back(v);
        str.push_back(w);
    }

    // 3bit全探索
    for (int mask = 0; mask < pow(3, k); ++mask)
    {
        int tmp = mask;
        for (int i = 0; i < k; ++i)
        {
            len[i] = tmp % 3 + 1 ;
            tmp /= 3;
        }
        if(!check_num()) continue;
        if(check_contents()) break;
    }

    return 0;
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 031 #22

C - 数列ゲーム

問題文

D - 語呂合わせ

問題文