精進の記録をどのように管理していくか迷っていたんですが，ブログのエントリとして保管することにしました．
本記事ではABC176 F - Brave CHAINを扱います．ちょっと特殊なDPの問題でした．
atcoder.jp
問題概要
$ N $ 以下の自然数が書かれた $ 3N $ 枚カードが一列に並んでいる．これに対して以下の操作を $ N-1 $ 回行う．
- 左から $ 5 $ 枚のカードを好きに並び替えて左から $ 3 $ 枚を取り除き，この $ 3 $ 枚が同じ数字ならば $ 1 $ 点得る．
最後に余った $ 3 $ 枚のカードが同じ数字なら追加で $ 1 $ 点得る．
制約
- $ 1 \leq N \leq 2000 $
- $ 1 \leq A_i \leq N $
考察
問題文のままの通り操作を考えると何をすればいいのかわからないのでまず操作を分析する．
操作には「並び替える」と書いてあるが，取り除く $ 3 $ 枚のカードは同じ数字であるかのみが重要なので順不同である．また，残す $ 2 $ 枚のカードについても次の操作で好きに並び変えられるため順不同である．
以上のことから $ 1 $ 回の操作は
- 左 $ 5 $ 枚のうち残す $ 2 $ 枚を選んで残り $ 3 $ 枚が同じ数字なら $ 1 $ 点得る
というように言い換えられる．これに関しては直感的にすぐ言い換えられる人が多そう．
操作をこのように言い換えることができると，$ i (\geq 2)$ 回目の操作では $ i-1 $ 回目の操作で残した $ 2 $ 枚のカードと，新しく操作範囲に入る $ 3 $ 枚で操作を行うことになる．この「新しい」 $ 3 $ 枚は $ i $ のみに依存するため，方針としては残した $ 2 $ 枚をなんらかの方法で管理するのが良いことがわかってくる．最初の2枚を $ 0 $ 回目の操作で残したカードと考えることで $ i = 1 $ でも上記のことが言えるようになる．
今までの考察から上図のように列を分割したくなる (入力例 $ 2 $ )．
何も考えずに全探索をすると到底間に合わないことは明らかで，探索空間を絞ったり貪欲に選ぶことも難しそうなのでDPを考える (制約が微妙に小さいところがそれっぽく感じました)．上でも述べたように残した $ 2 $ 枚の情報のみを管理すればいいのでDPは次のように考えられる．
- $ dp[i][j][k] $ : $ i $ 回目の操作までして残った数の組が $ (j, k) $ である場合の得点の最大値
このDPの遷移は $ 5 $ 枚から $ 2 $ 枚選んで残り $ 3 $ 枚が同じが調べるだけなので $ O(1) $ になり，状態数が $ O(N^{3}) $ のため，全体の計算量は $ O(N^{3}) $ になる．しかし $ O(N^{3}) $ の解はこの問題では通らないのでさらに考察を進める．
残した $ 2 $ 枚の情報は最低限必要なので状態数を減らすことは難しい．ここでDPの更新回数を考えてみる．前回の操作で残したカードをそのまま次も残す場合は基本的に更新は行われないが，唯一残りの $ 3 $ 枚のカード (上の図の三つ組) が同じ数字だった場合のみ更新が行われる．しかし，実は三つ組の数字がすべて等しいときはその $ 3 $ 枚を取り除くのが最善手であることが証明できる．
▶証明 (というより正当性の確認)
※以下では三つ組の $ 3 $ 枚のカードをそのまま取り除くことを「そのままの場合」と記述する．
三つ組の数字がすべて等しいとき「そのままの場合」が最善手でない場合が存在する，と仮定する．
この仮定は「残すカードを $ 1 $ or $ 2 $ 枚入れ替えた方が，『そのままの場合』と比較して得点が高くなる可能性がある」と同値である．さらに残すカードをそのままにするときは得点が $ +1 $ されるため，状態が分岐してから合流するまでに $ +2 $ 以上「そのままの場合」より得点を増加させなければならない．
以下，三つ組が $ (\alpha, \alpha, \alpha) $ であるとする．
- $ 1 $ 枚だけ入れ替える場合を考える．入れ替えることで残すカードに入った $ \alpha $ が次に別の数字と入れ替えられたタイミングで「そのままの場合」と合流することがわかる．また，$ \alpha $ でない方のカードによって得点が増加する場合は「そのままの場合」でも同じ分の得点の増加が望める．以上 $ 2 $ つの事実より，状態が分岐してから合流するまでに高々 $ +1 $ しか「そのままの場合」より得点が増加させられないことがわかる．
- $ 2 $ 枚入れ替える場合を考える．両方の $ \alpha $ が $ 1 $ 回ずつ別の数字に入れ替えられたタイミングで「そのままの場合」と合流する．前項と同様に考えて，$ 2 $ 回の入れ替えによって $ +2 $ だけ「そのままの場合」より多く得点を増加させられるように見える．しかし， $ 2 $ 回の入れ替えによって $ +2 $ 点増加する場合，取り除いた $ 6 $ つの $ \alpha $ のうち $ 4 $ つは処理した三つ組たちの中にあるので，「そのままの場合」もこのうち $ 3 $ つを利用して $ +1 $ 点増加させることができる．従ってこの場合も高々 $ +1 $ しか「そのままの場合」より得点が増加させられないことがわかる．
以上の1,2より仮定は矛盾し，三つ組の数字が等しいとき「そのままの場合」は常に最善手であることが示された．
以上のことから，$ 3 $ つの数字がすべて等しい組は取り除いて最後に答えに $ +1 $ すればよいことがわかる．
三つ組をそのまま取り除く場合の更新については考慮できたので，後は三つ組の数字を少なくとも $ 1 $ つは残す場合の更新を考えれば良い．三つ組を数字を $ (A,B,C) $ とする．$ 3 $ 枚のカードのうちどれかを残す場合，残すカードの組は $ (A,x), (B,x), (C,x) $ ($ x \in [1:N] $) のいずれかになる．よって遷移先の状態 (更新箇所) の数は $ O(N) $ となる．
また，$ dp[j][k] $ のように $ i $ を省略することで三つ組をそのまま取り除く場合の更新を考える必要がなくなる ( $ dp[i+1][j][k]=max(dp[i+1][j][k], dp[i][j][k]) $ の更新が不要になる )．よって三つ組 $ 1 $ つに対する更新箇所の数は $ O(N) $ となる．
次に $ 1 $ 箇所を更新する計算量について考える．
新たな $ 3 $ 枚のカードのうち $ 1 $ 枚を残す場合． $ (x \notin [A,B,C], y \in [A,B,C] ) $ の状態に遷移することになる．$ (x, i \in [1:N]) $ から遷移することになる．つまり，$ x $ を含む状態のうち $ dp $ の最大値で更新すれば良く，これは $ dp 2[x] $ として $ dp $ の更新時に一緒に更新することで $ O(1) $ で取得することができる．また，$ 3 $ 枚のうち残された $ 2 $ 枚のカードが同じ数字 ( $ \alpha $ とする ) の場合，$ (x, \alpha) $ の状態から遷移すると取り除く $ 3 $ 枚のカードは同じであるので $ dp[x][\alpha]+1 $ の値で更新すれば良い．
新たな $ 3 $ 枚のカードのうち $ 2 $ 枚を残す場合． $ (x \in [A,B,C], y \in [A,B,C]) $ の状態に遷移することになる．この場合，あらゆる状態から遷移することになり，$ \bf { 1. } $ の場合と同様に $ dp $ 全体の最大値を管理して，この値で更新すれば良い．また，$ 3 $ 枚のうち残された $ 1 $ 枚を $ \alpha $ とする．$ (\alpha, \alpha) $ の状態から遷移するとき取り除く $ 3 $ 枚のカードは同じであるので $ dp[\alpha][\alpha]+1 $ の値で更新すれば良い．
以上より， $ 1 $ 箇所を更新する計算量は $ O(1) $ である．三つ組 $ 1 $ 組に対する更新の計算量を $ O(N^{2}) $ から $ O(N) $ に落とすことができた．これにより全体の計算量は $ O(N^{2}) $ となり今回の制約でも十分間に合うようになる．
個人的なポイント
- 操作が扱いにくい場合は操作の特徴を分析して言い換えをする．
- DPの更新に必要な情報と不要な情報をきちんと分ける．(今回は残る2枚の情報のみが必要だった)
- DPの状態数をそれ以上削減できないような場合でも毎ループの更新箇所が少ない場合は計算量が落ちる時もある．
- 今回は状態が変化しない場合のDPの更新が不要 + それ以外の場合の更新箇所が少なかったためオーダの $ N $ が一つ落ちた．
- DP配列を毎ループ使いまわして更新の順序が不明の場合，更新クエリをqueueに入れておいて後でまとめて更新すると良さそう．
- 組を状態として持つとき，順序付きで管理するがいちいちswapするのは面倒なのでDPテーブルの更新を関数化すると嬉しい．
提出URL
▶ソースコードを展開
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert
#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}
using namespace std;
template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}
const int INF = 1e9;
const int N_MAX = 2000;
int dp[N_MAX][N_MAX];
int dp2[N_MAX];
int Max = 0;
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
int N; cin>>N;
int s,t; cin>>s>>t; s--; t--;
vector<vi> input(N-1,vi(3));
rep(i,N-1)rep(j,3) cin>>input[i][j], input[i][j]--;
int z; cin>>z; z--;
auto set_val = [&](int a, int b, int val){
if (a>b) swap(a,b);
chmax(dp[a][b],val);
chmax(dp2[a],val); chmax(dp2[b],val);
chmax(Max,val);
};
auto allEqual = [](vi &v){
return v[0]==v[1]&&v[1]==v[2];
};
rep(i,N)rep(j,N) dp[i][j]=-INF;
rep(i,N) dp2[i]=-INF;
set_val(s,t,0);
using P = tuple<int,int,int>;
int sum=0;
rep(i,N-1){
if (allEqual(input[i])){
sum++;
continue;
}
queue<P> que;
rep(j,N)for(auto k:input[i]){
int val = -INF;
vi tmp = input[i];
tmp.erase(find(all(tmp),k));
if (find(all(tmp),j)!=tmp.end()){
chmax(val,Max);
tmp.erase(find(all(tmp),j));
chmax(val,dp[tmp[0]][tmp[0]]+1);
}else{
chmax(val,dp2[j]);
if (tmp[0]==tmp[1]){
chmax(val,dp[j][tmp[0]]+1);
chmax(val,dp[tmp[0]][j]+1);
}
}
que.emplace(j,k,val);
}
while(!que.empty()){
int a,b,val;
tie(a,b,val) = que.front(); que.pop();
set_val(a,b,val);
}
}
int ans=0;
rep(i,N)rep(j,N){
chmax(ans,dp[i][j]+(i==j&&j==z));
}
cout<<ans+sum<<"\n";
return 0;
}
