Codeforces Round #316 DIV2 B問題 - Simple Game

Source

Codeforces Round #316 DIV2 B問題 (1000pt)
Problem description

問題概要

$2$ 人でゲームを行う．
最初に正整数 $N$ を決め，自分も相手も $1$ 以上 $N$ 以下の整数を選ぶ．
また，その後，$1$ から $N$ までの整数を一様にランダムに選び，その値を $c$ とする．
それぞれが選んだ整数のうち，$c$ に近い整数を選んだほうが勝ちとなる（$c$ との差が等しい場合は自分の負けとする）．
整数 $N$ と，更に，相手が選ぶ整数 $M$ も与えられるので，自分が勝つ確率が最も高くなるような整数の選び方を $1$ つ求める問題．

解法

$1$ から $N$ までの整数を大小半分に分け，
相手が小さい方を選んでいるなら相手が選んだ整数 $+1$ を，
相手が大きい方を選んでいるなら相手が選んだ整数 $-1$ を選べば良い．
（ちょうど真ん中の整数を選んでいるなら，$\pm 1$ どちらでも勝率は変わらないのでどちらでも良い）
ただし，$N=1$ の時は，自分も $1$ を選ぶしかないことに注意する．

C++のスパゲッティなコード

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

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

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 main(){
  int N, M;

  reader(&N,&M);
  if(M <= N/2) writerLn(min(N,M+1)); else writerLn(max(1,M-1));

  return 0;
}

Current time: 2024年04月24日00時27分46秒
Last modified: 2015年08月15日04時57分09秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF316 CF_Div2_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：