Codeforces AIM Tech Round (Div. 2) C : Graph and String

問題リンク :
http://codeforces.com/contest/624/problem/C

問題概要 :
長さnの{'a','b','c'}で構成されている文字列が存在した
これを次の手順でグラフに変換した
1. n個のノードを作成、各ノードに１から順に番号を割り振る
2. 異なる２つのノード番号i,jについて、文字列のi番とj番が一致または隣接していればノードiとノードjに辺を張る
ここで、隣接とはa-b,b-cのことをであり、a-cは隣接とは言わない
この手順でグラフを作成したあと、文字列を消した

グラフが与えられるので、上記の手順にしたがった場合与えられたグラフになるような文字列を出力せよ
複数存在するならどれか１つでよい
存在しない場合はNoと出力せよ

解法:
ノードがちょうど1つしか存在しない場合、明らかに答えとなる文字列は存在する
'a'か'b'か'c'である
どれか好きなのを出力すると良い

ノードがちょうど２つ存在する場合、これも必ず答えとなる文字列は存在する
その２つのノード間に辺があるなら、'a'-'b'か'b'-'c'か'a'-'a','b'-'b','c'-'c'のいずれかを出力するとよい
辺がないなら隣接していないので'a'-'c'が答えとなる

ノードが３つ以上存在する場合、次のような部分をグラフから探す

このような部分が存在しないなら、存在する頂点は全て完全グラフの一部となっているはずである
つまり完全グラフが何個か存在することになる
完全グラフが１つしかないなら、明らかに答えは存在する（全て同じ文字とか）
完全グラフが２つなら、0の完全グラフと２の完全グラフが存在する
それ以上存在するなら答えはない　０と２で２つまでなら完全グラフをつくれるが、もう１つ追加しからそれが０の完全グラフであれ、１であれ、２であれ、どれでも最初の２つの完全グラフとくっついてしまう

上の図のような、三角形の一辺を抜いた部分が存在するなら、
その図にある０番のノードは'b'であり、１番のノードと２番のノードはどちらかが'a'でもう片方が'c'である
このとき、1番のノードに辺がつながっているノードは１に割り当てられた英小文字（'a'か'c')か０に割り当てられた英小文字('b')と一致するはずである
同様に２番のノードに辺がつながっているノードは２番に割り当てられた英小文字('a'か'c')か０番に割り当てられた英小文字（'b')と一致するはず

これらを集合にしたとき（上の図でいう、点線内のノード番号を集合としたとき）
両方の集合に属することができるのは'b'しかないので、それらのノードには'b'を割り当てる
そうでないものは、どちらかを'a'の集合、もう片方は'c'の集合と決めて（どっちでも良いので）割り当てる
あとは頂点集合全体を見て、'a','b','c'のいずれも割り当てられていないものがあればNoと出力し、
そうでないなら答えとなる文字列を生成して、一応入力のグラフができるかチェックして大丈夫ならそれを出力する

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX = 600;

const string YES = "Yes";
const string NO = "No";
typedef pair<int,int> ii;

int V,E;
vector<int> G[MAX];
bool mat[MAX][MAX];
bool vmat[MAX][MAX];
vector<ii> edges;
char c[MAX];

void dfs(int cur,set<int> &S) {
  rep(i,(int)G[cur].size()) {
    int next = G[cur][i];
    if( S.count(next) ) continue;
    S.insert(next);
    dfs(next,S);
  }
}

int compute() {

  if( V == 1 ) {
    cout << YES << endl;
    return puts("b");
  }
  if( (int)((V*(V-1))/2) == E ) {
    cout << YES << endl;
    return puts(string(V,'b').c_str());
  }

  rep(i,V) c[i] = '$';
  set<int> S0;
  set<int> S2;
  rep(i,(int)edges.size()) {
    int s = edges[i].first;
    int t = edges[i].second;
    rep(p,V) {
      if( s == p || t == p ) continue;
      if( !mat[p][t] && !mat[p][s] ) continue;
      if( mat[p][t] && mat[p][s] ) continue;
      int ID0,ID1 , ID2;
      if( mat[p][s] ) {
	ID0 = t, ID1 = s, ID2 = p;
      } else {
	ID0 = s, ID1 = t, ID2 = p;
      }

      S0.insert(ID1);
      S0.insert(ID0);
      S2.insert(ID1);
      S2.insert(ID2);
      rep(k,V) {
	if( k == s || k == t || k == p ) continue;
	if( mat[ID0][k] ) S0.insert(k);
	if( mat[ID2][k] ) S2.insert(k);
      }
      goto Skip;
    }
  }
 Skip:;

  if( S0.empty() ) {
    S0.insert(0);
    dfs(0,S0);
    rep(i,V) if( !S0.count(i) ) {
      S2.insert(i);
      dfs(i,S2);
      break;
    }
    for(set<int>::iterator it=S0.begin();it!=S0.end();it++) {
      c[*it] = 'a';
    }

    for(set<int>::iterator it=S2.begin();it!=S2.end();it++) {
      c[*it] = 'c';
    }
    rep(i,V) if( c[i] == '$' ) {
      return puts(NO.c_str());
    }
    puts(YES.c_str());
    rep(i,V) {
      printf("%c",c[i]);
    } puts("");
    return 0;
  }

  rep(i,V) {
    if( S0.count(i) && S2.count(i) ) {
      c[i] = 'b';
    } else if( S0.count(i) ) {
      c[i] = 'a';
    } else if( S2.count(i) ) {
      c[i] = 'c';
    }
  }
  /*
  cout << "S0::" << endl;
  for(set<int>::iterator it=S0.begin();it!=S0.end();it++) {
    cout << *it << " ";
  } puts("");

  cout << "S2::" << endl;
  for(set<int>::iterator it=S2.begin();it!=S2.end();it++) {
    cout << *it << " ";
  } puts("");
  */
  string answer = "";
  rep(i,V) {
    if( c[i] == '$' ) {
      return puts(NO.c_str());
    }
    answer += string(1,c[i]);
  }

  
  rep(i,V) REP(j,i+1,V) {
    int v1 = c[i] - 'a';
    int v2 = c[j] - 'a';
    if( abs(v1-v2) <= 1 ) {
      vmat[i][j] = vmat[j][i] = true;
    }
  }

  rep(i,V) rep(j,V) if( mat[i][j] != vmat[i][j] ) {
    return puts(NO.c_str());
  }
  puts(YES.c_str());
  return puts(answer.c_str());
}

int main(){
  scanf("%d %d",&V,&E);
  int s,t;
  rep(i,E) {
    scanf(" %d %d",&s,&t);
    --s, --t;
    mat[s][t] = mat[t][s] = true;
    G[s].push_back(t);
    G[t].push_back(s);
    if( s > t ) swap(s,t);
    edges.push_back(ii(s,t));
  }
  compute();
  return 0;
}

Typical DP Contest J : ボール

問題リンク :
J: ボール - Typical DP Contest | AtCoder

問題概要：略

解法：
期待値苦手すぎて謎だったので以下の解説記事を参考にしました
Typical DP Contest J - ボール - Lilliput Steps

ビットDP (orメモ化再帰)
まだ倒れていないものがある場所に対応するビットを1にしておきます
dp[bit] := 倒れていないものの状態がbitで、ここからすべて倒すまでに必要なボールを投げる回数の期待値

状態bitからボールを投げるとき、次に投げるボールを落とす位置をすべて試してみて、その中で最小の期待値をdp[bit]にいれる

状態bitから全て倒すために必要な期待値は、狙った場所をxとしたとき
dp[bit] = dp[bit&~(1<< ( x - 1 ) ) ] / 3 + dp[bit&~ ( 1 << x ) ] / 3 + dp[bit&~(1<< ( x + 1 ) ) ] / 3
このxを全てためしてみてその最小値をdp[bit]にいれる
ただし、x,x-1,x+1のうち、すでに倒した場所orそもそもない場所に落ちたときはdp[bit]が左辺に残ることになる
なので、そのときはその部分を左辺に以降すること

コード1(メモ化再帰):

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

const double DINF = DBL_MAX;

int n,bitmask,x[20];
double memo[1<<20];

double dfs(int state) {
  if( !state ) return 0;
  if( !equals(memo[state],DINF) ) return memo[state];
  REP(i,1,17) {
    double ex = 1;
    double same = 0;
    REP(dx,-1,2) {
      int p = i + dx; 
      int nstate = state;
      nstate = state & ~(1<<p);
      if( state == nstate ) ++same;
      else {
	ex += dfs(nstate) / 3.0;
      }
    }
    ex = ( ex * 3.0 ) / ( 3.0 - same );
    memo[state] = min(memo[state],ex);
  }
  return memo[state];
}

int main() {
  cin >> n;
  rep(i,n) {
    cin >> x[i];
    ++x[i];
    bitmask |= (1<<x[i]);
  }
  rep(i,(1<<18)) memo[i] = DINF;
  printf("%.10f\n",dfs(bitmask));
  return 0;
}

コード2(ビットDP）:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

const double DINF = DBL_MAX;

int n,x[20],bitmask;
double dp[1<<20];

int main() {
  cin >> n;
  rep(i,n) {
    cin >> x[i];
    ++x[i];
    bitmask |= (1<<x[i]);
  }
  rep(i,(1<<20)) dp[i] = DINF;
  dp[0] = 0;
  for(int state=1;state<=bitmask;state++) {
    if( state & ~bitmask ) continue;
    double mini = DINF;
    for(int p=1;p<=16;p++) {
      double ex = 0;
      double same = 0;
      bool fail = false;
      for(int dx=-1;dx<=1;dx++) {
	int np = p + dx;
	int next_state = state;
	if( (bitmask>>np) & 1 ) next_state &= ~(1<<np);
	if( next_state == state ) ++same;
	else if( equals(dp[next_state],DINF) ) { fail = true; break; }
	else ex += dp[next_state]/3.0;
      }
      if( !fail ) mini = min(mini,((1.0+ex)*3.0)/(3.0-same));
    }
    dp[state] = mini;
  }
  printf("%.10f\n",dp[bitmask]);
  return 0;
}

ここからは2016/6/10に追記:

既に解いていたことをすっかり忘れて再度解いたので解説を追加

ものを倒す順番に意味はないので左から順番にものを倒していくことを考える

左から順番にものを倒していくので、ボールを投げるべき座標は一意に定まる
その座標は、一番左にあるものの座標をxとしたとき、x+1である

この理由は次の通り
座標xにある物を倒せる座標はx-1,x,x+1のいずれか
しかし、左から順番に倒していくためx-1以下の座標にはものは存在しない
そのためx-1を狙ってボールを投げると、絶対にボールが存在しない座標x-1とx-2にボールが落ちる可能性があり、その分が無駄である
同様の理由から、xを狙ってボールを投げると絶対にボールが存在しない座標x-1にボールが落ちる可能性があり、その分が無駄である
x+1を狙ってボールを投げた場合、ボールが落ちる可能性があるのは座標x,x+1,x+2である
これらの座標にはものが存在する可能性があり、先ほどの２つと比べて無駄がない
そのためx+1を狙ってボールを投げれば良いことが分かる

x+1にボールを投げればよいということが分かった
ここで、x+1にボールを投げた際にボールの落ちる可能性のある場所の状態は次の4通りである
状態1.

状態2.

状態3.

状態4.

それぞれの状態について考える
状態1.
座標xにあるものを倒すまでに必要な投げる回数の期待値は３である
この期待値は次の様にして求まる
1回目で倒せる確率は1/3
2回目で倒せる確率は2/3 * 1/3
3回目で倒せる確率は2/3 * 2/3 * 1/3
...
n回目で倒せる確率は(2/3)^(n-1) * 1/3
期待値はi回目で倒せる確率*i (1<= i <= ∞)の総和となる
8byteのdouble型で計算することを考えると、(2/3)^500はもう0といっていいくらい小さいことが分かる
なので、先ほどの計算を1から500くらいまで愚直にやってみると良い
すると期待値が3に収束していることを確認できる
手でやるなら式をたてて極限でやれば良い

状態2.
座標x,x+1にあるものを倒すまでに必要な投げる回数の期待値は4.5である
この期待値はサンプル１にある通り（xからx+2までの範囲にたっているものの数が同じであれば状態が異なっても期待値は同じ)
x,x+1,x+2にものが１つしか立っていない状態からそれを倒すまでに必要な投げる回数の期待値は３であることから、
x,x+1,x+2にものが２つ立っている状態からものが１つ立っている状態にするために必要な投げる回数の期待値は1.5であることが分かる ( 4.5 - 3.0 = 1.5 )
この結果を用いて次の様に期待値を求めることができる

座標x+1にボールを投げたとき、
xにあるものを倒せたなら、状態１か状態５に遷移する
x+1にあるものを倒せたなら、状態１に遷移する
これらが確率1/2で起こるので、この時の期待値は
(たっているものの数を2個から1個するための期待値=1.5) +
(xにあるものを倒した後、残り全てを倒すまでに必要な期待値) / 2 +
(x+1にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 2

状態3.
状態2とほとんど同じ
x+1がx+2になるだけ

状態4.
座標x,x+1,x+2にあるものを倒すまでに必要な投げる回数の期待値は5.5
なぜなら、３個立っている状態から１個倒すまでに必要な投げる回数の期待値は１（どこに落ちても必ず１本は倒せるから）
2個立っている状態から1個倒すまでに必要な投げる回数の期待値は1.5なので
3個立っている状態から2個倒すまでに必要な投げる回数の期待値は2.5
1個立っている状態から全て倒すまでに必要な投げる回数の期待値は3なので
3個立っている状態から全て倒すまでに必要な投げる回数の期待値は 2.5 + 3 = 5.5

ものが2個立っている状態から全て倒すまでに必要な投げる回数の期待値が4.5なので、
ものが3個たっている状態からものが2個たっている状態にするまでに必要な投げる回数の期待値は1 ( 5.5 - 4.5 = 1 )
また、座標x+1にものを投げると座標x,x+1,x+2のどれか１個が倒れるので、このときの期待値は
(たっているものの数を3個から1個にするまでに必要な投げる回数の期待値=1) +
(xにあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3 +
(x+1にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3
(x+2にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3

これらを再帰的に計算すると良い

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

/*
  1->0 : 3
  2->1 : 1.5 2->0 4.5
  3->2 : 1   3->1 2.5 3->0 5.5
 */

int n,x[16];
double memo[1<<18];

double dfs(int bitmask) {
  if( !( memo[bitmask] < 0.0 ) ) return memo[bitmask];
  if( bitmask == 0 ) return 0.0;

  int use = bitmask & -bitmask;
  int x   = log2(use);
  int state = (bitmask>>x&1) | (((bitmask>>(x+1))&1)<<1) | (((bitmask>>(x+2))&1)<<2);
  if( state == 1 ) {
    memo[bitmask] = 3.0;
    return memo[bitmask] += dfs(bitmask&(~use));
  } else if( state == 3 ) {
    memo[bitmask] = 1.5;
    return memo[bitmask] += ( dfs(bitmask&(~use)) * 0.5 + dfs(bitmask&(~(1<<(x+1)))) * 0.5 );
  } else if( state == 5 ) {
    memo[bitmask] = 1.5;
    return memo[bitmask] += ( dfs(bitmask&(~use)) * 0.5 + dfs(bitmask&(~(1<<(x+2)))) * 0.5 );
  } else if( state == 7 ) {
    memo[bitmask] = 1;
    return memo[bitmask] += ( dfs(bitmask&(~use)) / 3.0 + dfs(bitmask&(~(1<<(x+1)))) / 3.0 +
                             dfs(bitmask&(~(1<<(x+2)))) / 3.0);
  }
  assert(false);
}

void compute() {
  int bitmask = 0;
  rep(i,n) bitmask |= (1<<(x[i]+1));
  rep(i,(1<<18)) memo[i] = -1.0;
  printf("%.10f\n",dfs(bitmask));
}

int main() {
  cin >> n;
  rep(i,n) cin >> x[i];
  compute();
  return 0;
}

herokuでカスタムドメインを使いたい

herokuでweb appを作ると通常xxx.herokuapp.comというurlになっている
このherokuapp.comを消してxxx.comにしたい
したのでその過程をメモ
ちなみに月1100円くらいかかる

1. ドメインを買う ( 年1300円くらい、購入するドメイン名によるけど ）
自分は
VALUE-DOMAIN バリュードメイン
で購入した
以降購入したどめいん名をxxx.comとする

2. web appのあるディレクトリにどうして
$ heroku domains:add xxx.com
を実行

3. DNSさーばを借りる ( 月1000円くらい　海外のだと$5とかで借りれる )
ルートドメインを使いたいのでALIAS（だったかな）を使えるとこでDNSサーバに登録してもらう
herokuの公式サイトにいくつか紹介されているけど、英語弱者なので日本のが良いと思い
日本のとこを探した
DNSを自由に簡単に。Dozens（ダズンズ）
ここに登録してbasicプラン（月１０００円）に入る
するとTypeでALIASを選べるようになるのでそれを使う
Recode Nameにはなにもかかず(.xxx.com)となるはず
TypeはALIASに、
Contentにxxx.herokuapp.comと書く
あとはそれで登録
登録するとDNSサーバを教えてもらえるので、（といっても固定なので登録しなくても分かるが
それをdomain-valueに言ってネームサーバに記入しておわり

第2回 ドワンゴからの挑戦状 予選 D : 庭園

問題リンク :
D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder

問題概要 :
略

解法 :
長方形を２つ選ぶので、縦か横に領域を分割して
それらの中の最大値を足したものの最大値が答えとなる
そのため、ある長方形の中の最大値について求めることができれば良い

まず、以下の問題を解こう
Frame | Aizu Online Judge
y軸を２つ選ぶというアイデアを得ましたね
では次に、以下の問題を解きましょう
https://uva.onlinejudge.org/external/126/p12640.pdf
（この解説は
UVa 12640 : Largest Sum Game - 土下座しながら探索中）

数列について、連続した部分の総和の最大値の求めかたが分かりましたね
ではもうこの問題についても分かったでしょう

つまり、y軸を２つ固定すると、その固定された範囲の各x軸については和をとってまとめることが可能で、こうするとただの数列の連続した部分列の最大値を求める問題になります

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll LLINF = LLONG_MAX;
const int MAX = 310;

ll b[MAX][MAX],sum[MAX][MAX];
ll upper[MAX], bottom[MAX];

void rotate90(int h,int w){
  swap(h,w);
  vector<vector<ll> > ret(h,vector<ll>(w,0));
  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      ret[y][x] = b[w-1-x][y];
    }
  }
  rep(i,h) rep(j,w) b[i][j] = ret[i][j];
}

inline ll calcSum(int x1,int y1,int x2,int y2) {
  ll ret = sum[y2][x2];
  if( y1-1 >= 0 ) ret -= sum[y1-1][x2];
  if( x1-1 >= 0 ) ret -= sum[y2][x1-1];
  if( y1-1 >= 0 && x1-1 >= 0 ) ret += sum[y1-1][x1-1];
  return ret;
}

ll calc(int h,int w) {
  rep(i,h) rep(j,w) {
    sum[i][j] = b[i][j];
    if( j-1 >= 0 ) sum[i][j] += sum[i][j-1];
    if( i-1 >= 0 ) sum[i][j] += sum[i-1][j];
    if( j-1 >= 0 && i-1 >= 0 ) sum[i][j] -= sum[i-1][j-1];
  }
  rep(i,h) upper[i] =  bottom[i] = -LLINF;
  rep(y1,h) REP(y2,y1,h) {
    ll maxi = -LLINF;
    ll mini = 0;
    rep(x,w) {
      maxi = max(maxi,calcSum(0,y1,x,y2)-mini);
      mini = min(mini,calcSum(0,y1,x,y2));
    }
    upper[y2]  = max(maxi,upper[y2]);
    bottom[y1] = max(maxi,bottom[y1]);
  }
  REP(y,1,h) upper[y] = max(upper[y],upper[y-1]);
  for(int y=h-2;y>=0;y--) bottom[y] = max(bottom[y],bottom[y+1]);
  ll maxi = -LLINF;
  rep(y,h-1) maxi = max(maxi,upper[y]+bottom[y+1]);
  return maxi;
}

void compute(int h,int w) {
  ll maxi = calc(h,w);
  rotate90(h,w);
  swap(h,w);
  maxi = max(maxi,calc(h,w));
  cout << maxi << endl;
}

int main() {
  int h,w;
  cin >> h >> w;
  rep(i,h) rep(j,w) cin >> b[i][j];
  compute(h,w);
  return 0;
}

herokuのサーバー上に一時ファイルを作ったこと

herokuのサーバー上に一時ファイルを作る必要があり、それが出来るようになるまでに困ったところと解決策をメモ

1. 一時ファイルを作成できるのは /tmp 内だけ

それ以外の場所にファイルを作成しようとしても無駄です

例えば、 java で一時ファイルを作るためには次のようにする

try {
  File file = new File("/tmp/X.txt"); // /tmp 内なのでOK
  PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
  pw.println("XXXXXXX");
  pw.close();
} catch(IOException e) {}

以下のようにしても一時ファイルは作成されない

try {
  File file = new File("X.txt"); // カレントディレクトリが/tmpでないならファイルは作成されない
  PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
  pw.println("XXXXXXX");
  pw.close();
} catch(IOException e) {}

2. dynosは３つある
一時ファイルがちゃんと作成されているか確認したい
では、heroku run "ls /tmp" で確認してみよう -> 見当たらない...
見当たらないのでてっきり出来ていないものかと思いきや、そういうわけではない
dynosは３つ存在するのだ
1つ目は Web Dynos, 2つ目は Worker Dynos, 3つ目は One-off Dynos (これらの詳細は下記のリンク先で確認できる)
heroku runは(多分)One-off Dynos
1.のプログラムが実行され、ファイルを書き込んでいるのは Web Dynos か Worker Dynos のどちらか (知らない)
1.のプログラム実行後に heroku run で /tmp の中身を見ても、それらのDynosは相互に影響を与えないため確認できない
heroku公式の以下のリンク先にある Types of dynos を読むとそれが分かる
Dynos and the Dyno Manager | Heroku Dev Center
経緯
一時ファイルが作成できない
/tmpにしかファイルは書き込めないらしい
/tmpにjavaでファイルを作成して、heroku runでファイルが作成されたか確認
ない
stack overflowにそれっぽい記事がある
heroku公式の説明をちゃんと読めとある、読もう
herokuは3つのdynos上で動くらしい
One-off Dynos は temporary dynos で administrative tasks を処理するために使われる...と書いてあるのでなんとなく heroku run はここっぽい
また、javaのプログラムはadministrative taskでもないしここではなさそう
Web DynosとWorker Dynosの説明を見るかぎりjavaはこのどちらかっぽい
ひょっとしてheroku runにファイルが存在しないのは、作られてないんじゃなくて作られたサーバーが違うのでは...? => その通りだったっぽい

Typical DP Contest I : イウィ

問題リンク :
I: イウィ - Typical DP Contest | AtCoder

問題概要 : 最大iwi数

解法 :
メモ化再帰 => WA
区間DP => TLE
TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いた

dp[L][R] := 閉区間[L,R]までで得られるiwiの最大値
区間DPでよくやる、長さが小さい順に値を更新をする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

string s;
int dp[301][301];

int main() {
  getline(cin,s);
  int n = s.size();
  REP(length,1,n+1) rep(sp,n-length+1) { // length : 区間の長さ, sp : 左から順に区間の値を更新
    int ep = sp + length - 1;
    REP(k,sp+1,ep) dp[sp][ep] = max(dp[sp][ep],dp[sp][k]+dp[k+1][ep]);
    if( s[sp] == 'i' && s[ep] == 'i' ) {
      REP(k,sp+1,ep) if( s[k] == 'w' ) {
        bool fail = false;
        int len = (k-1)-(sp+1)+1;
        if( len && !( len >= 3 && dp[sp+1][k-1] == len ) ) fail = true;
        len = (ep-1)-(k+1)+1;
        if( len && !( len >= 3 && dp[k+1][ep-1] == len ) ) fail = true;
        if( !fail ) {
          dp[sp][ep] = ep - sp + 1;
          break;
        }
      }
    }
  }
  cout << (int)(dp[0][n-1]/3) << endl;
  return 0;
}

Typical DP Contest H : ナップザック

問題リンク :
H: ナップザック - Typical DP Contest | AtCoder

問題概要 : 日本語なので略

解法 :
まずナップザックに入れるものを色の番号が小さい順にソートする
（同じ色のものは連続した場所に存在するようにしたいだけ）
通常のナップザックに加えて、今追加しようとしている色が既に追加されているかされていないかという情報を持たせる
下記の配列にあるstate(0か1)がその情報を表す
dp[i][state][c][w] := i番目のものを追加しようとしていて、i番目のものと同じ色を既に追加したかどうか(state), 現在の色の数(c), 重みの総和(w) としたときの最大値

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Data {
  int w,v,c;
  bool operator < ( const Data &dat ) const {
    if( c != dat.c ) return c < dat.c;
    if( w != dat.w ) return w < dat.w;
    return v < dat.v;
  }
};

int N,W,C,dp[2][2][60][10010];
Data data[101];

void compute() {
  memset(dp,-1,sizeof(dp));
  dp[0][0][0][0] = 0;
  sort(data,data+N);
  int maxi = 0;
  rep(i,N) { 
    int cur = i & 1;
    int next = !cur;
    rep(j,2) rep(k,C+1) rep(l,W+1) dp[next][j][k][l] = -1;
    Data &info = data[i];
    rep(j,2) {
      rep(k,C+1) {
	rep(l,W+1) {
	  if( dp[cur][j][k][l] == -1 ) continue;
	  dp[next][j][k][l] = max(dp[next][j][k][l],dp[cur][j][k][l]);
	  int color = k + !j;
	  if( color > C || l+info.w > W ) continue;
	  int &v = dp[next][1][color][l+info.w];
	  v = max(v,dp[cur][j][k][l]+info.v);
	  maxi = max(maxi,v);
	}
      }
    }
    if( i+1 < N && info.c != data[i+1].c ) {
      rep(k,C+1) rep(l,W+1) {
	dp[next][0][k][l] = max(dp[next][0][k][l],dp[next][1][k][l]);
	dp[next][1][k][l] = -1;
	maxi = max(maxi,dp[next][0][k][l]);
      }
    }
  }
  cout << maxi << endl;
}

int main() {
  cin >> N >> W >> C;
  rep(i,N) cin >> data[i].w >> data[i].v >> data[i].c;
  compute();
  return 0;
}