Codeforces Round #640 (Div. 4) DETAYO~~~~~~~~

Div.4に参加しましたが、結果はさんざんでした（大反省）
コンテストURL：https://codeforces.com/contest/1352

A. Sum of Round Numbers

問題概要

左端（一番大きい桁）以外が0の数（例：4000、1、9、800）を「丸められた数」とします。クエリ数と正の整数が与えられるので、「丸められた数」の和でをあらわすとき、必要な「丸められた数」の最小の個数と「丸められた数」を求めてください。

考え

「を10で割ったあまり」をvectorに格納しつつ、が0になるまで10で割っていきます。そのあと、格納された数が0でない場合は桁数を見て10を掛けて出力します（とは書いたけどとてもバグらせました……）。

実装（折りたたんでいます）

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> num;
    int now = 10;
    while( N > 0 ){
      num.push_back(N%10);
      N/= 10;
    }
    int ans = 0;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) != 0 ){
        ans++;
        num.at(i) *= pow(10, i);
      }
    }
    cout << ans << endl;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) == 0 ) continue;
      cout << num.at(i) << " ";
    }
    cout << endl;
  }
}

B. Same Parity Summands

問題概要

正の整数が与えられます。数列がすべて奇数、またはすべて偶数である場合に、その和をにすることが可能か判定してください。可能な場合はそのような数列を1つ出力してください。

考え

全部奇数にする場合は最後以外1、全部偶数にする場合は最後以外2にして、一番最後の数で帳尻を合わせればいいです。どちらでも帳尻を合わせられない場合は和をにすることができません。
全部奇数にするときは個の1でを埋めて、に入れるが正の奇数になる必要があります。全部偶数にするときには個の2でを埋めて、に入れるが正の偶数になる必要があります。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    
    if( (N-(K-1))%2 == 1 && N-(K-1) > 0 ){
      //すべて奇数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 1 << " ";
      cout << N-(K-1) << endl;
    }else if( (N-2*(K-1))%2 == 0 && N-2*(K-1) > 0 ){
      //すべて偶数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 2 << " ";
      cout << N-2*(K-1) << endl;
    }else cout << "NO" << endl;
  }
}

C. K-th Not Divisible by n

問題概要

正の整数が与えられるので、で割り切れない正の整数のうち番目のものを出力してください。

考え

「小さいほうから個見た場合、で割り切れない数は個含まれる」
上記はが大きくなるほども大きくなる（＝単調性がある）ので二分探索で求めることができるみたいです。「で割り切れない数の個数」を求めるには、個の数の中からの倍数だけを抜けばいいので、ということになります。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int ok = 10e12;
    int ng = 0;
    while( ok-ng > 1 ){
      int mid = (ok+ng)/2;
      if( mid - (mid/N) >= K ) ok = mid;
      else ng = mid;
    }
    cout << ok << endl;
  }
}

算数（数学）orエスパーでもできます（本番中はこっちだった）

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int A = N*K;
    if( A%(N-1) == 0 ){
      cout << A/(N-1)-1 << endl;
    }else{
      cout << A/(N-1) << endl;
    }
  }
}

D. Alice, Bob and Candies

問題概要

飴が個並んでいて、左から番目の飴の大きさはです。アリスは左から、ボブは右から、交互に飴を食べるゲームをします。自分の番の時、（一番最初のアリスの時以外は）「直前に相手が食べた飴の大きさの合計」より大きくなるように、1つ以上の飴を食べる必要があります。飴がなくなったら終了です。ゲームの総ターン数と、アリスとボブそれぞれが食べる飴の個数を出力してください。

考え

dequeを使って、アリスのターンの時は前から、ボブのターンの時は後ろから飴を取っていけばいいです。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    deque<int> dq;
    for( int i = 0; i < N; i++ ){
      int A;
      cin >> A;
      dq.push_back(A);
    }
    
    bool fg = 1; //0のときalice
    int alice = 0;
    int bob = 0;
    int K = 0;
    int now = 0;
    int ans = 0;
    while( !dq.empty() ){
      if( fg ){ //aliceのとき
        now += dq.front();
        alice += dq.front();
        dq.pop_front();
        if( now > K ){
          K = now;
          fg = 0;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }else{
        now += dq.back();
        bob += dq.back();
        dq.pop_back();
        if( now > K ){
          K = now;
          fg = 1;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }
    }
    cout << ans << " " << alice << " " << bob << endl;
  }
}

E. Special Elements

問題概要

数列が与えられます。であるようなの個数を求めてください。

考え

連続する部分数列の和と等しいはいくつありますか？ということなので、まずは累積和をします。lとrの位置をそれぞれ全探索して一通り部分数列の和を求めた後、と等しい数があるか見ます。8000*8000なので、TLEはしなくてもメモリが不安な気持ちになるようなならないような（？）が最大でもであることから、vectorのサイズはで十分です。じゅぴろさんありがとうございました……。

実装（折りたたんでいます）

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

signed main() {
  
  cin.tie(0);
  ios::sync_with_stdio(false);
    
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    for( int i = 0; i < N; i++ ) cin >> A.at(i);
    vector<bool> num(N*N+10);
    vector<int> R(N+1);
    for( int i = 0; i < N; i++ ) R.at(i+1) = R.at(i) + A.at(i);
    
    for( int i = 0; i <= N; i++ ){
      for( int j = i+2; j <= N; j++ ){
        num.at(R[j]-R[i]) = 1;
      }
    }
    
    int ans = 0;
    for( int i = 0; i < N; i++ ){
      if( num[A[i]] ) ans++;
    }
    cout << ans << endl;
  }
}

F, G なんもわからん（就寝……）