Codeforces Round #683(Div. 2) 参加記

https://codeforces.com/contest/1447
A、B、Cの3完でした。Dは難しそうなふんいき……。

A. Add Candies

サンプルがちょっと不親切というかひっかけ？だけど、1, 2, 3, ..., N個キャンディがあるときは、i番目にiの袋を選んでそれ以外にiずつ足せば、必ずN回ですべての袋が等しくなる（1つの袋に1+2+3+...+N個入る）

B. Numbers Box

位置は関係なく、負の数の個数が偶数の場合は、うまくこねくり回すことで全部正の数にできる。負の数の個数が奇数かつ0が1つもない場合は必ずどれか1つが奇数になってしまうので、1番絶対値が小さい値を負の数にする。

C Knapsack

ながあったらそれを出力して終わり。ない場合、未満の数字だけ添え字と一緒にpairの配列としてとっておいてソート。i番目までの合計が未満の場合、i+1番目の数字は必ず未満なので、i+1番目を足してもWを超えることはない。前から足していって以上になった時点で出力。

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
const int INF = 1e10;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

signed main(){
  int T;
  cin >> T;
  rep(t, T){
    int N, W;
    cin >> N >> W;
    vector<pair<int, int>> A;
    int fg = 0;
    rep(i, N){
      int S;
      cin >> S;
      if( S < (W+1)/2 ){
        A.emplace_back(make_pair(S, i+1));
      }
      if( S >= (W+1)/2 && S <= W ){ //これ一つで条件を満たす場合
        fg = i+1;
      }
    }
    if( fg > 0 ){
      cout << 1 << "\n" << fg << endl;
      continue;
    }else if( (int)A.size() == 0 ){
      cout << -1 << endl;
      continue;
    }

    N = (int)A.size();
    sort(A.begin(), A.end()); //Aの中はW/2以下の数字だけ
    vector<int> R(N+1);
    rep(i, N){
      R[i+1] = R[i]+A[i].first;
    }

    if( R[N] < (W+1)/2 ){
      cout << -1 << endl;
      continue;
    }

    for( int i = 1; i <= N; i++ ){
      if( R[i] >= (W+1)/2 && R[i] <= W ){
        cout << i << endl;
        for( int j = 0; j < i; j++ ) cout << A[j].second << " ";
        break;
      }
    }

  }
}

ABCの後に出たけどあんまり疲労感がなかった。昼寝のおかげかも？