yukicoder No.72 - そろばん Med

Source

ニコニコミュニティ
問題文

問題概要

珠の数が合計 $N$ 個の，一列しか無いが，上の珠の数，下の珠の数を自由に変えられるそろばんを考える．
つまり，上の珠の数と下の珠の数の和が $N$ で，上の珠，下の珠それぞれ，$1$ 箇所だけ珠 $1$ 個分のスペースを開ける．
それぞれの状態を $0$ からある整数までと対応させるとき，対応させることのできる整数の最大値はいくらかを求める問題．

解法

状態数${}-1$ が答えで，状態数を最大化すれば良い．
上の玉の数を $x$ 個とすると，上の珠のスペースの位置は $x+1$ 個あり，下の珠も同様なので，状態数は $(x+1)(N-x+1)$ となる．
二次関数になるので，最大値を求めて，上の珠の数と下の珠の数ができるだけ等しくなるように分けるのが最適であることがわかり，これは直感的にもほぼ自明．
多倍長が使えるなら，上の珠の数をいくつにするかというのを三分探索しても良いが，そこまでする必要はないように思う．
制約の小さいバージョンはこちら（yukicoder No.71）．

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)

#define ll long long

void reader(ll *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);}

#define MD 1000007

int main(){
  ll N, N1, N2, res;

  reader(&N);
  N1 = N/2; N2 = N-N1;
  N1 %= MD;
  N2 %= MD;
  res = (N1 + 1) * (N2 + 1) - 1;
  res %= MD;
  res = (res+MD)%MD;
  writer((int)res,'\n');

  return 0;
}

Current time: 2024年04月17日05時53分02秒
Last modified: 2014年12月23日23時52分21秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：