zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC119-C「Synthetic Kadomatsu」です。
ポイント
非常に難しい問題でした。自力で解けなかったため，こちらの記事（けんちょんの競プロ精進記録）を参考にさせていただきました。ポイントとしては「それぞれの竹を3本に合成しきってから帳尻を合わせる」という解法に気づくことができるかというところです。
まず，使える魔法は3種類ありますが，その順番は関係ないのです。例えば長さ$a$，$b$の竹があったときに「合成→短縮」の順番で魔法を使うと，魔法を使った後の長さ$x$は
x &= (a+b) - 1\\
&= a + b - 1
\end{align}
となります。次に「短縮→合成」の順番で魔法を使うと，短縮に長さ$a$の竹を選んだとすれば
x &= (a - 1) + b\\
&= a + b - 1
\end{align}
短縮に長さ$b$の竹を選んだ場合も同様です。このように，競プロでは「操作の順番は関係ない」系の問題がよく出題されるようなので，ここら辺の問題で感覚を研ぎ澄ませておきたいです。
さて，魔法の順番が関係ないことになれば，あとは「合成して3本の竹にする」組み合わせを全て考える全探索を行えばOKです。しかし，この全探索も一筋縄ではいきません。最もスッキリするパターンは，再帰を用いて実装する方法です。
どのような再帰関数を書けば良いのでしょうか。考えられるのは，竹の個数分だけインデックスを調べていき，それぞれに対して「竹Aとして合成する」「竹Bとして合成する」「竹Cとして合成する」「使わない」の4パターンに対応するような関数を書くことです。
再帰関数の作り方は，まず引数と返り値を設計して，次にbreakするポイントを設定して，最後に再帰部分を記述するのがわかりやすいです。それぞれ順番に見ていきましょう。
引数はi(何番目の竹を見ているか)，a(竹Aとして合成された竹の長さ)，b(竹Bとして合成された竹の長さ)，c(竹Cとして合成された竹の長さ)の4つを考えればOKでしょう。返り値は一旦resとして設定しておきます。
// 再帰関数
int rec(int i, int a, int b, int c){
// breakするポイント
// 再帰処理を書く
// 返り値
return res;
}次にbreakするポイントを設計します。今回は，見ている竹のインデックスが$N$になればbreakします。つまり，インデックス$N-1$までの$N$個の竹を全て合成or無視しきったところでbreakするということです。今回は，再帰しきった後に返したい値は，それぞれの合成後の竹における目標の長さとの差分を合計したものです。つまり，abs(A-a)+abs(B-b)+abs(C-c)です。
// 再帰関数
int rec(int i, int a, int b, int c){
// breakするポイント
if (i==N){
return abs(A-a) + abs(B-b) + abs(C-c);
}
// 再帰処理を書く
// 返り値
return res;
}ここで注意しなくてはならないのは，「竹A or B or Cとして竹が選ばれない可能性がある」ということです。例えば，竹Bとして合成する竹が選ばれなかったケースを考えてみましょう。すると，そもそも竹がありませんから，延長も短縮も行うことができなくなり，与えら得た条件の長さの竹Bを作ることはできなくなってしまいます。
ですので，aかbかcのいずれかが0であった場合には適当に大きい値を返しておけばOKです。
// 再帰関数
int rec(int i, int a, int b, int c){
if (i==N){
if (a==0 || b==0 || c==0) return 1000000;
else return abs(A-a) + abs(B-b) + abs(C-c);
}
// 再帰処理を書く
// 返り値
return res;
}あとは再帰部分を記述していきます。素直に「竹Aとして合成する」「竹Bとして合成する」「竹Cとして合成する」「使わない」の4パターンを考えます。この際，以下のchmin関数を利用します。chmin(a, b)は「aがbよりも小さければaをbで更新する」という関数です。
void chmin(int &a, int b) { if (a > b) a = b;}さて，再帰部分を完成させていきましょう。
// 再帰関数
int rec(int i, int a, int b, int c){
if (i==N){
if (a==0 || b==0 || c==0) return 1000000;
else return abs(A-a) + abs(B-b) + abs(C-c);
}
// 再帰処理を書く
// まず竹を使わない場合を考えてしまう
// この時点で変数resがセットされる
int res = rec(i+1, a, b, c);
// chmin(a, b)は「aがbよりも小さければaをbで更新する」という関数
// resは最小値であるべきなので以下でresを最小値として更新している
// (条件式) ? (真のときの値) : (偽のときの値)を使っている
// aが0のときは「最初に竹が選ばれた」だけなので合成魔法を使う必要はない
chmin(res, rec(i+1, a+L[i], b, c) + (a>0 ? 10:0));
chmin(res, rec(i+1, a, b+L[i], c) + (b>0 ? 10:0));
chmin(res, rec(i+1, a, b, c+L[i]) + (c>0 ? 10:0));
// 返り値
return res;
}これで再帰関数は完成です。以下で実装の全体をお伝えします。
順番を変えても関係ない系の問題と再帰関数
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
void chmin(int &a, int b) { if (a > b) a = b; }
// コードはここから
int N, A, B, C;
int L[10];
int rec(int i, int a, int b, int c){
if (i==N){
if (a==0 || b==0 || c==0) return 1000000;
else return abs(A-a) + abs(B-b) + abs(C-c);
}
// 注目している竹を使わない場合
int res = rec(i+1, a, b, c);
// 最初に使う竹を選ぶ場合は合成ではない
// 竹が選ばれるのが2回目以降であれば10ポイントを消費する
chmin(res, rec(i+1, a+L[i], b, c) + (a>0 ? 10:0));
chmin(res, rec(i+1, a, b+L[i], c) + (b>0 ? 10:0));
chmin(res, rec(i+1, a, b, c+L[i]) + (c>0 ? 10:0));
return res;
}
int main(){
cin >> N >> A >> B >> C;
rep(i, N) cin >> L[i];
// 0インデックス目から開始
// もちろん最初はどの竹に対しても素材は選ばれていないため全て0でセットする
cout << rec(0,0,0,0) << endl;
}
コメント