変数名 rem 意味

• remainder
• remain

残り・余りという意味で使われます。

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~

蟻本 2-3 DP rec 意味

• なんで関数名がrecなんだろう？と最初は思いました
• 続きを読んでいくと、漸化式が出てくる
• 漸化式の英訳は recurrence formula
• ということで、recの意味はrecurrence, またはrecursionです。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

tenka1_2018_c ～形が決まれば絶対値が外れる～

Quiz

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

AC code

https://atcoder.jp/contests/tenka1-2018-beginner/submissions/13108762

解説

• 解説の通り、a1 <= a2 <= a3 という単調増加の形はない
• a2を除去しても得られる得点は変わらないため
• それを考慮すると、最適に出来上がった数列はギザギザになる
• ギザギザの形が決まれば、絶対値記号が外れる
• 係数一覧が決まるので、値の大きいaを、大きい係数に対応させればいい

学び

形が決まれば絶対値が外れる

code抜粋

// 係数生成
VI generate_coefficient(ll N){
  VI C;
  if(N%2==0){
    C.push_back(1);
    C.push_back(-1);
    rep(i, (N-2)/2){
      C.push_back(-2);
      C.push_back(2);
    }
  }
  else{
    C.push_back(1);
    C.push_back(1);
    ll rest = N-2;
    ll plus = rest/2;
    ll minus = rest-plus;
    rep(i,plus) C.push_back(2);
    rep(i,minus) C.push_back(-2);
  }
  return C;
}

// 大きい係数に大きい値を当てる
ll f(VI A, VI C){
  RSORT(A);
  RSORT(C);
  ll sum=0;
  rep(i, A.size()){
    sum += A[i] * C[i];
  }
  return sum;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];

    if(N==2){
      ll diff = abs(A[0]-A[1]);
      p(diff); return 0;
    }

    VI C = generate_coefficient(N);
    ll ans0 = f(A, C);

    // 係数反転
    rep(i,N) C[i] *= -1;
    ll ans1 = f(A, C);

    ll ma = max(ans0, ans1);
    p(ma);
    
    return 0;
}

ddcc2018_qual_c ～重複しないように片方をうまく分離する～

Quiz

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c

AC code

https://atcoder.jp/contests/ddcc2019-qual/submissions/13110019

考察

• O(N)で解ければいい
• N=10とする
• P側は1～2で構成するとすると、Q側は1～5まで使える
• P側は1～3で構成するとすると、Q側は1～3まで使える
• そうやって足していけばいいように思えるが、上記２行には重複がある
  • P側=1,1,1,1,1,1,1,1,1,1 Q側=1,1,1,1,1,1,1,1,1,1 など
  • 重複なく数える必要がある
• P側で1～3で構成するとして、3¹⁰で考えると、3が含まれない数列も含まれる
  • 1～3で構成して、3が1つは含まれる数列はいくつだろう
  • 3¹⁰ - 2¹⁰ である
• そのようにP側を分離すると、Q側が取れる場合の数も決まり、求まる
• コードを書く前にN=3で答えが一致することを確認した (サンプル3)

code抜粋

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;
 
    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    mint sum = 0;
    
    FOR(i, 1, N+1){
      // P側の個数
      ll a = mod_pow(i, 10) - mod_pow(i-1, 10);
      if(a<0) a+=mod;

      // Q側の最大値
      ll b = N/i;
      ll c = mod_pow(b, 10);

      sum += a*c;
    }
    p(sum.x);
    
    return 0;
}

Macでonline-judge-toolの環境を構築した

• 競技プログラミングを少し触っていたのは1年ほど前
• その時はテストケースをコピペしてテキストファイルにしてローカルで使っていた
• 結構手間だった
• 今回はツールで自動化しよう

github.com

• Macなのでサクッと入って正常に動く
• テストケースを取得した
• 解放のコードはIDEで書きたい。今回はVisual Studio Code (VSC)
• competitive_programming/atcoder/quiz_id/ ごとに管理

• VSC内からTermialが叩ける
• テストケースがtest/に入る
• cppコードを書く
• コンパイルする g++ answer.cpp
• oj t と打つ
• テストが走る

• Submitの部分はちゃんと書いてないそうなのでAtCoderから直接Submitすればいい
• 「テスト通ってるけどSubmit後のテストでひっかかる」となっちゃうとSubmit祭りになる
  • その時はSubmitも自動化したくなるけど、それはその時考えよう

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

Submit

oj submit https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_a answer.cpp

• 正常に通った👍