迷走

精進記です。説明が分かりにくい部分があったらtwitter(@tancahn2380)に連絡ください。

「みんなのプロコン 2019」 D - Ears

問題

問題

解説

各座標にすぬけ君が何回歩くことができるかについて考察すると、次の5つの区間に分かれることが分かります。

  • 歩く回数が0
  • 歩く回数が0ではない偶数回
  • 歩く回数が奇数回
  • 歩く回数が0ではない偶数回
  • 歩く回数が0

よって、DPをして求めることができます。
DP[i][j]:=区間iで位置jにいるときの最小値

ACコード

int l;
int a[202020];
LL dp[6][202020];
 
LL calc(int k, int j){
    if(k == 1 || k == 5)return a[j];
    if(k%2 == 0){
        if(a[j] == 0)return 2LL;
        return a[j]%2;
    }
    return (a[j] + 1)%2;
}
 
int main(){
    INIT;
    cin >> l;
    REP(i, l)cin >> a[i + 1];
    REP(i, 6)REP(j, 202020)dp[i][j] = HINF<LL>();
    for(int i = 1;i <= 5;i++)dp[i][0] = 0;
 
    for(int j = 1;j <= l;j++){
        for(int k = 1;k <= 5;k++){
            for(int i = 1;i <= k;i++){
                dp[k][j] = min(dp[k][j], dp[i][j - 1] + calc(k, j));
            }
        }
    }
    LL ans = HINF<LL>();
    for(int i = 1;i <= 5;i++)ans = min(ans, dp[i][l]);
    cout << ans << endl;
}

AGC032 A - Limited Insertion

問題

問題

解説

一連の操作を逆順に考え、「長さNの数列bの先頭からj番目がjの時にその値を取り除く」ということを繰り返すことができるかシミュレートします。jが複数選べるときは最も大きいものを選ぶこととします(最も大きいもの以外を選んでしまうと、最も大きいものはそのあとに取り除くことができなくなるため)。

ACコード

int n;
vector<int> b;
int maxl = 0;
int main(){
    INIT;
    cin >> n;
    REP(i, n){
        int a;
        cin >> a;
        a--;
        maxl = max(a, maxl);
        b.emplace_back(a);
    }
    vector<int> ans;
    while(!b.empty()){
        bool flg = false;
        for(int i = min((int)b.size() - 1, maxl);i >= 0;i--){
            if(!flg && b[i] == i){
                ans.emplace_back(i);
                b.erase(b.begin() + i);
                flg = true;
            }
        }
        if(!flg){
            cout << -1 << endl;
            return 0;
        }
    }
    reverse(ALL(ans));
    REP(i, n){
        cout << ans[i] + 1 << endl;
    }
}

ABC123 A Five Antennas

問題

問題

解説

すべてのアンテナが直接通信ができる、すなわち最長区間e- ak以下かどうかの判定をすればよい

ACコード

int a, b, c, d, e, k;

int main(){
    INIT;
    cin >> a >> b >> c >> d >> e >> k;
    cout << (e - a > k ? ":(" : "Yay!") << endl;
}

ABC123 B Five Dishes

問題

問題

解説

気合の実装をした。10で割った余りの小さい順にソートして、余りが1以上のもののうち最も余りが小さいものを最後に注文し、他はその料理よりも前に注文すればよい。

ACコード

int a[5];

int main(){
    INIT;
    REP(i, 5)cin >> a[i];
    int ans = 0;
    REP(i, 5){
        ans += a[i]/10*10;
        a[i] %= 10;
    }
    sort(a, a + 5);
    REP(i, 5){
        if(a[i] != 0){
            ans += a[i];
            a[i] = 0;
            break;
        }
    }
    REP(i, 5){
        if(a[i])ans += 10;
    }
    cout << ans << endl;
}

ABC123 C Five Transportations

問題

問題

解説

一番運搬できる人数が少ない乗り物に合わせて移動するのが最適となります。

ACコード

LL n, a, b, c, d, e;

int main(){
    INIT;
    cin >> n >> a >> b >> c >> d >> e;
    LL m = min({a, b, c, d, e});
    cout << 5 + n/m - (n % m == 0 ? 1 : 0) << endl;
}