競プロやります。

競プロを頑張るブログです。

トップ > 企業コンテスト > みんなのプロコン2019

みんなのプロコン2019

企業コンテスト

C - When I hit my pocket...

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_c

方針

まず K+1 \leq A のとき、ビスケットを円に交換できないので、すぬけ君はビスケットをたたいて増やす以外の操作を行えません。よって K + 1 を出力します。

B - A \leq 2 のとき、ビスケット→円→ビスケット の2回の操作で増えるビスケットの数は 2 枚以下ですから、円に交換するよりもビスケットをたたき続ける方が効率よく増やせます。よってこのときも K+1 を出力します。

それ以外のとき、まずはビスケットを A 枚まで増やしたのち、「円に交換してからビスケットに戻す」操作を繰り返せばよいです。
はじめビスケットを 1 枚持っているので、A 枚にした時点で残りの操作回数は N - A + 1 回です。これが偶数のときは「円に交換してからビスケットに戻す」の繰り返しになるので、A 枚から交換によって (N - A + 1) / 2 × (B - A) 枚増やすことができます。奇数のときは、最後の 1 回は円に交換するのではなく、ビスケットをたたいて 1 枚増やすことに注意します。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll K, A, B;
    cin >> K >> A >> B;
    if(A + 2 >= B || K + 1 <= A) cout << K + 1 << endl;
    else if((K-A+1)%2==0){
        cout << A + (K-A+1)/2*(B-A) << endl;
    }else{
        cout << A + (K-A+1)/2*(B-A) + 1 << endl;
    } 
}

D - Ears

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
コンテスト中には解けませんでした。解説を参考にしています。

方針

すぬけ君の散歩の出発地点を S 、到着地点を T とします。また散歩で訪れた範囲のうち、座標の最小値を D 、最大値を U とします。以下では S < T としていますが、ほかの場合でも同じです。

f:id:poporix:20190210171521p:plain:w500

このとき耳 i に入っている石の数は、上図からもわかるように、

  • i \leq D のとき、0 個
  • D < i \leq S のとき、正の偶数個
  • S < i \leq T のとき、奇数個
  • T < i \leq U のとき、正の偶数個
  • i > U のとき、0 個

となります。
また隣り合う整数座標の間を往復することによって、どの耳についても入る石の数を正の偶数個だけ増やせますから、上記の条件を満たす任意の石の入り方を、散歩によって実現することができます。

dp[i][t] を、座標 0 \leq x < i に D, S, T, U のうち t 個が含まれているときの、耳 1 ~ i についてのりんごさんの操作回数の最小値とします。 dp[0][t] = 0 で、求めるものは \min \{ dp[L][t]~|~0 \leq t \leq 4 \} です。（求めるものは dp[L][4] ではないです。D, S, T, U のうち一部またはすべてが x = L である場合もあるからです。）

dp[i][t] がどのように表されるかを考えます。
(0) t = 0 のとき
散歩によって耳 i に入る石の数は 0 個ですから、 A_i 個の石はすべてりんごさんの操作によって入れる必要があります。
また x = i の時点で D, S, T, U が含まれていないとき、 x=i-1 の時点でも D, S, T, U は1つも含まれません。
　　 dp[i][0] = dp[i-1][0] + A_i

(1) t = 1 のとき
散歩によって耳 i の中に任意の正の偶数個の石を入れることができます。よって耳 i に対して行う操作は、 A_i = 0 のときは 耳の中に散歩で 2 個の石を入れておき、2回の操作で取り除くのが最善、 A_i が正の場合は、 A_i が偶数のとき 0 回、奇数の時 1 回です。
また x = i の時点で t = 1 のとき、 x = i-1 の時点では t = 0,~1 のどちらかです。（ x = i-1 が D のとき、 x=i-1 で t = 0、 x = i で t = 1 となります）
　　 \displaystyle dp[i][1] = \begin{cases} \min\{ dp[i-1][t]~|~0 \leq t \leq 1 \} + 2~&(A_i = 0) \\ \min\{ dp[i-1][t]~|~0 \leq t \leq 1 \} + A_i \% 2~&(A_i > 0)\\ \end{cases}

(2) t = 2 のとき
散歩によって耳 i の中に任意の奇数個の石を入れることができます。よって耳 i に対して行う操作は、 A_i が偶数のとき 1 回、奇数の時 0 回です。
また、 x = i -1 の時点では t = 0,~1,~2 のどれかです。（ x = i-1 が D かつ S の場合や、 x < i-1 に D があり x = i-1 が S の場合など）
　　 dp[i][2] = \min\{ dp[i-1][t]~|~0 \leq t \leq 2 \} + 1 - A_i \% 2

(3) t = 3 のとき
(1) と同様に考えます。ただし、 x = i-1 の時点でのありうる t は、 t = 0,~1,~2,~3 であることに注意します。
　　 \displaystyle dp[i][3] = \begin{cases} \min\{ dp[i-1][t]~|~0 \leq t \leq 3 \} + A_i \% 2~&(A_i > 0) \\ \min\{ dp[i-1][t]~|~0 \leq t \leq 3 \} + 2~&(A_i = 0)\\ \end{cases}

(4) t = 4 のとき
(0) と同様に考えます。ただし、 x = i-1 の時点でのありうる t は、 t = 0,~1,~2,~3,~4 であることに注意します。
　　 dp[i][4] = \min\{ dp[i-1][t]~|~0 \leq t \leq 4 \} + A_i

ソースコード

dp[i][t] を求めるのに \min \{dp[i-1][t^{\prime}]~|~0 \leq t^{\prime} \leq t \} が必要になるわけですが、 t^{\prime} について for 文を回しながら順に min を取っていくことで求めています。

#include <bits/stdc++.h>
#define ll long long
#define inf 1e18
using namespace std;

int main(){
    int L;  cin >> L;
    vector<ll> a(L+1,0);
    for(int i=1; i<=L; i++) cin >> a[i];

    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(L+2, vector<ll>(5,0));
    for(int i=1; i<=L; i++){
        ll prev = inf;
        for(int t=0; t<=4; t++){
            prev = min(prev, dp[i-1][t]);
            if(t==0 || t==4) dp[i][t] = prev + a[i];
            if(t==1 || t==3) dp[i][t] = prev + (a[i]==0 ? 2:a[i]%2);
            if(t==2) dp[i][t] = prev + 1 - a[i]%2;
        }
    }

    ll ans = inf;
    for(int t=0; t<=4; t++) ans = min(ans, dp[L][t]);
    cout << ans << endl;
}