Codeforces Round #617 (Div. 3) バチャ

URL：https://codeforces.com/contest/1296
ABCDの4完！4ペナ出してるのが痛すぎるけど、順位表を見る限り他の人も結構ペナを出していた……。

A. Array with Odd Sum

数列から適当に $i$ 番目と $j$ 番目の数字を選んで $A_j$ を $A_i$ に置き換える、という操作を好きな回数できる。適切に操作することで数列の和を奇数にすることが可能か？という問題。
なんか問題文難しくない？操作についてと何を求めるのかを誤読して1ペナ。奇数の個数が奇数か、奇数が1個以上かつ偶数が1個以上ある場合YES、そうでなければNO。

B. Food Buying

$x$ 円分の物を購入すると $⌊\frac{x}{10}⌋$ 円のキャッシュバックがもらえる。適切に物を買ったとき、払える金額の合計の最大値はいくらか、という問題。
$x$ を $⌊\frac{x}{10}⌋$ + $x$ % $10$ に置き換えてシミュレートしていく。このとき $⌊\frac{x}{10}⌋$ だけ別に足し合わせておいて、あとから元の $x$ の値と足せば答えが出る。

C. Yet Another Walking Robot

最初 $(0, 0)$ にロボットがいて、L,R,U,Dからなる文字列で上下左右の動きを命令されている。この文字列の部分文字列のうち、切り取っても切り取り前とロボットの座標が変わらない部分のうち最も短いものを切り取るという問題。
zero sum rangesと同じ考え方で、既に出てきた座標に移動した場合、それは切り取っても問題ない動きということになる。一番短いやつを切り取らなきゃいけないので、mapで座標 $(a, b)$ が出てきたときの文字列の最新の位置を保持していく。

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

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
signed main(){
 
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  int T;
  cin >> T;
 
  rep(t, T){
    int N;
    cin >> N;
    string S;
    cin >> S;
    map<pair<int, int>, int> now;
    now[make_pair(0, 0)] = 0;
    int x = 0;
    int y = 0;
    int ansa = 0;
    int ansb = 0;
    int ans = INF;
    rep(i, N){
      if( S[i] == 'U' ) y++;
      else if( S[i] == 'D' ) y--;
      else if( S[i] == 'L' ) x--;
      else x++;
      if( now.count(make_pair(x, y)) ){
        if( i-now[make_pair(x, y)] < ans ){
          ansa = now[make_pair(x, y)]+1;
          ansb = i+1;
          ans = ansb-ansa;
        }
      }
      now[make_pair(x, y)] = i+1;
    }
    if( ans == INF ) cout << -1 << "\n";
    else cout << ansa << " " << ansb <<"\n";
  }
}

D. Fight with Monsters

自分が攻撃→ライバルが攻撃を繰り返して、1匹ずつモンスターを倒していく。自分の攻撃力・ライバルの攻撃力・ライバルの攻撃の順番を飛ばすことができる魔法の回数・モンスターたちの体力が与えられるので、自分の手番で最大何匹のモンスターが倒せるかを求める。
まず与えられるモンスターの体力は全部 $(A+B)$ で余りを取る。もし余りが0の場合は $H_i=A+B$ として、ソートする。自分の手番で一撃で倒せる範囲の体力( $1$ ~ $A$ )は0回の魔法で倒せる。残り体力が $A$ 以上のモンスターについては、体力が少ない順に何回魔法を使えば倒せるかを求める。
体力 $H$ のモンスターを倒すには切り上げの関係で $\frac{H+A-1}{A}$ 回攻撃する必要がある。順番として、魔法0回で $A$ ダメージ与えることができて、以降は魔法1回ごとに追加で $A$ ダメージを与えられるから、魔法を使う回数を求めるときは分子から $A$ を引く。

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

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e9;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
signed main(){
 
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  int N, A, B, K;
  cin >> N >> A >> B >> K;
  vector<int> H(N);
  int ans = 0;
  rep(i, N){
    cin >> H[i];
    H[i] %= (A+B);
    if( H[i] == 0 ) H[i] = A+B;
  }
  sort(H.begin(), H.end());
 
  rep(i, N){
    if( H[i] > 0 && H[i] <= A ){
      ans++;
      continue;
    }
    if( (H[i]-1)/A <= K ){
      ans++;
      K -= (H[i]-1)/A;
    }else break;
  }
  cout << ans << endl;
 
}