読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 21/22/23

yukicoder

- 21 平均の差

  • 問題概要

N個の数字をK個のグループ(要素数が1以上)に分けます。
グループ内の数字の平均値が最大のものと最小のものの差が最大になるようにグループ分けをしたときの差を答えよという問題です。

  • 解説

タイトル詐欺です。
平均を最大にする組み合わせは最大値を1個選んだとき、
平均を最小にする組み合わせは最小値を1個選んだときです。
それ以外の部分は適当に1個以上の集合に組み合わせられます。
したがって最大値-最小値が解です。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;


int main(void){
    int N; 
    int K;
    int H=0, L=1000;
    cin >> N >> K;
    for (int i = 0; i < N; i++){
        cin >> K;
        H = max(H, K);
        L = min(L, K);
    }
    cout << H-L << endl;
    return 0;
}

- 22 括弧の対応

  • 問題概要

(())()のように括弧がそれぞれ左右対応している文字列が与えられます。i文字めの括弧に対応する括弧は何文字目かを答えよという問題です(雑

  • 解説

i文字目が(だったとき、[t+1,j]の区間において、jが)であり)の数がm、(の数がm-1であるような最小のjが解になります。
i文字目が)の時は逆に操作するだけ。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;


int main(void){
    int N, K;
    int mv = 1;
    string s;
    cin >> N >> K >> s;
    K--;
    if (s[K] == ')')mv=-1;
    int cnt = 0;
    for (int i = K+mv; cnt !=1; i+=mv){
        if (s[i] == s[K])cnt--;
        else cnt++;
        if (cnt == 1)
            cout << i + 1 << endl;
    }
    return 0;
}

- 23 技の選択

  • 問題概要
  • 解説

期待値でDPをしましょう。
HPが残りnの相手を倒すのに必要な攻撃回数の期待値をdp(n)とすると、
現在の相手のHPがhであるとき,
通常技を使う場合の期待値はdp(h-A)+1
必殺技が当たったときの期待値はdp(h-D)+1
当たらなかったときはdp(h)+1
となります。
必殺技を使う場合の期待値は,dp(h)=\frac{2}{3}(dp(h-D)+1)+\frac{1}{3}(dp(h)+1)となります。
これを変形すると,dp(h)=dp(h-D)+1.5になります。
必殺技を使う場合と使わない場合の最小値を選択すればOkです。

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int H, A, D;
    cin >> H >> A >> D;
    double e[10001];
    e[0] = 0;
    for (int i = 1; i <= H; i++)
        e[i] = min(e[max(0, i - A)] + 1, e[max(0, i - D)] + 1.5);
    cout << e[H] << endl;
    return 0;
}