保存されている過去のバージョンの一覧

2015年11月22日07時52分24秒

AtCoder Beginner Contest #031 C問題 - 数列ゲーム

Source

AtCoder Beginner Contest #031
問題文

問題概要

要素数 $N$ の整数列 $S_1,S_2,\ldots,S_N$ が与えられる．
高橋くんと青木くんが以下のゲームを行う．
高橋くんが要素を $1$ つ選び，次に青木くんが別の要素を $1$ つ選ぶ．
数列の中で，選ばれた要素と，その間の要素だけ残し，残りを削除する．
数列の奇数番目の要素の和が高橋くんの点数に，偶数番目の要素の和が青木くんの点数になる．
青木くんは自分の点数が最大となるように選び，複数あるなら，最も左の要素を選ぶ．
高橋くんは，青木くんの戦略を知っているとして，得られる点数の最大値を求める問題．

解法

高橋くんの選び方を全て試し，青木くんの動きをシミュレーションすれば良い．
時間計算量 $O(N^3)$．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N, S[100];

pair<int,int> eva(int a, int b){
  int i, m=0, res1 = 0, res2 = 0;
  if(a > b) swap(a, b);

  REP(i,a,b+1){
    if(m==0) res1 += S[i];
    else     res2 += S[i];
    m ^= 1;
  }

  return make_pair(res1,res2);;
}

int main(){
  int i, j;
  int res = -1000000, tmp1, tmp2;
  pair<int,int> t;

  reader(&N);
  rep(i,N) reader(S+i);

  rep(i,N){
    tmp1 = tmp2 = -1000000;
    rep(j,N) if(j!=i){
      t = eva(i, j);
      if(tmp2 < t.second){
        tmp1 = t.first;
        tmp2 = t.second;
      }
    }
    res = max(res, tmp1);
  }

  writerLn(res);

  return 0;
}

Current time: 2024年04月25日10時13分15秒
Last modified: 2015年11月22日07時52分24秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC031 ABC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：