yukicoder No.873 - バイナリ、ヤバいなり！ｗ

Source

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

問題概要

省略

解法

省略

cLay（version 20190830-1）のコード

C++に変換後のコードはこちら

int N;
int dp[300001];

char res[300001]; int ress;

int search(int mode){
  int i;

  for(i=mode+1;i*i<=N;i+=2){
    if(dp[N] == dp[N-i*i] + i) return i;
  }

  for(i=2-mode;i*i<=N;i+=2);
  for(;;){
    i -= 2;
    if(dp[N] == dp[N-i*i] + i) return i;
  }

  return -1;
}

{
  int i, j, s;
  
  rep(i,300001) dp[i] = int_inf;
  dp[0] = 0;

  for(i=1;i*i<=300000;i++){
    for(j=i*i;j<=300000;j++) dp[j] <?= dp[j-i*i] + i;
  }

  rd(N);
  while(N){
    if(ress==0 || res[ress-1] == 0) s = 0;
    else                            s = 1;
    i = search(s);
    N -= i * i;
    rep(j,i) res[ress++] = (s+j)%2;
  }

  rep(i,ress) res[i] += '0';
  wt(res);
}

Current time: 2024年04月20日22時25分21秒
Last modified: 2019年09月01日01時06分01秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)