今日はバーチャルコンテストを行いました。

コンテストの解説

コンテストのリンクはこちら

YNU CPC 2019 VC 004 A

ABC002 A - 正直者

https://atcoder.jp/contests/abc002/tasks/abc002_1

問題概要

整数 $X,Y$ のうち大きいほうの値を出力してください。

コード例

#include <iostream>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    if(x > y){
        cout << x << endl;
    }
    else{
        cout << y << endl;
    }
    return 0;
}

ABC009 - 引っ越し作業

https://atcoder.jp/contests/abc009/tasks/abc009_1

問題概要

$1$ 回に荷物を $2$ 個まで運べます。$N$ 個の荷物をすべて運ぶのに最低何回必要か求めてください。

コード例

基本的には $N/2$ ですが、$N$ が奇数のときは端数を切り上げることに注意してください。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (n+1)/2 << endl;
    return 0;
}

ABC077 B - Around Square

https://atcoder.jp/contests/abc077/tasks/abc077_b

問題概要

$N$ 以下の平方数のうち、最大のものを求めてください。

解法

$1,4,9,16…$ と $x^2$ を小さい順に調べていって、 初めて $N$ を超えたときの $(x-1)^2$ が答えです。

コード例

#include <iostream>
using namespace std;

int main() {
    int n, x = 1;
    cin >> n;
    while(x*x <= n){
        x += 1;
    }
    x -= 1;
    cout << x*x << endl;
    return 0;
}

ABC064 B - Traveling AtCoDeer Problem

https://atcoder.jp/contests/abc064/tasks/abc064_b

問題概要

直線上に $N$ 個の家が並んでいます。 $i$ 番目の家は 座標 $a_i$ にあります。
いまから、すべての家にプレゼントを配ることを考えます。
好きな場所から開始し、好きな場所で終了することができるとき、最小の移動距離を求めてください。

解法

寄り道をする、同じ場所を往復する、というような無駄な移動をしないようにします。
つまり、最適な移動方法は「一番端からスタートしてもう一方の端まで一直線に行く」になります。

よって答えは (一番右の家の座標)-(一番左の家の座標) となります。

コード例

#include <iostream>
using namespace std;

int main() {
    int n, amax = 1000, amin = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(a > amax){
            amax = a;
        }
        if(a > amin){
            amin = a;
        }
    }
    cout << amax - amin << endl;
    return 0;
}

ABC048 C - Boxes and Candies

https://atcoder.jp/contests/abc048/tasks/arc064_a

問題概要

$N$ 個の箱が横一列に並んでいます。最初、左から $i$ 番目の箱には $a_i$ 個のキャンディが入っています。

次の操作を好きな回数だけ行うことができます。

• キャンディが $1$ 個以上入っている箱をひとつ選び、その箱のキャンディを $1$ 個食べる。

また、次の条件を満たすことを目標とします。

• どの隣り合う $2$ つの箱を見ても、それらの箱に入っているキャンディの個数の総和が $x$ 以下である。

条件を満たすために必要な操作回数の最小値を求めてください。

解法

端から順に確定させていくことを考えます。まず、 $a_1 > x$ であれば $a_1 = x$ となるまで操作を行います。次に、 $i = 1,2,…,N-1$ の順に $a_i + a_{i+1} \le x$ となるように操作を行います。もし最初から $a_i + a_{i+1} \le x$ であれば操作をする必要はありません。$a_i + a_{i+1} > x$ であれば $a_i + a_{i+1} = x$ となるまで操作を行う必要があります。このとき、$a_{i+1}$ のみを減らすのが最適です。なぜならば、次に判定する $a_{i+1} + a_{i+2} \le x$ について操作回数を減らすことが期待できるためです。

以上の方法より、解を求めることができます。

コード例

#include <iostream>
using namespace std;

int main() {
    long long int n, x, a[100000], ans = 0;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    // 左端がxを超えているか
    if(a[0] > x){
        ans += a[0] - x;
        a[0] = x;
    }
    // 左端から順に確定させる
    for(int i = 0; i < n-1; i++){
        if(a[i] + a[i+1] > x){
            long long int t = (a[i] + a[i+1]) - x;
            ans += t;
            a[i+1] -= t;
        }
    }
    cout << ans << endl;
    return 0;
}

以降解法の流れのみ

ABC096 D - Five, Five Everywhere

https://atcoder.jp/contests/abc096/tasks/abc096_d

$\mod 5$ で合同な $5$ つの素数の和は必ず $5$ の倍数であることが示せます。

よって、エラトステネスの篩で素数を列挙し、例えば $5$ で割ったあまりが $1$ であるような素数を $N$ 個選べば条件を満たします。

ARC027 C - 最高のトッピングにしような

https://atcoder.jp/contests/arc027/tasks/arc027_3

スペシャルチケットの制約がなければ、容量 $X+Y$、荷物の重さ $t_i$、価値 $h_i$ のナップサック問題と同じであることが分かります。

ここにスペシャルチケットの制約を加えることを考えます。スペシャルチケットを節約しても高々 $X$ 個までのトッピングしか選べません。これをDPの状態変数に加えます。

$dp[i][j][k] =$ $i$ 番目のトッピングまでみて $j$ 個選び、チケットを $k$ 枚使ったときの最大値

と置くことでこの問題を解くことができます。求める解は $\max_{i=0}^{X} dp[N][i][X+Y]$ です。

あるいは

$dp[i][j][k] =$ $i$ 番目のトッピングまでみてスペシャルチケットを $j$ 枚、通常チケットを $k$ 枚使ったときの最大値

としても解けます。

ARC029 C - 高橋君と国家

そのままでは考えづらいので工夫が必要です。交易所がある町同士が連結であるとすると最小全域木の問題に落とし込めることに気づきます。交易所のある町同士をつなぐ代わりに仮想的な都市xを追加します。この都市xと直接辺でつながっている都市には交易所があるとみなします。すると、xと各都市に対してコスト $c_i$ の辺を張ればよく、クラスカル法やプリム法でこの問題は解くことができます。