Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-13

2004 TCCC Online Round 4

18:18

Dynamic Programming: From novice to advancedからの練習問題。

Easy - BadNeighbors

円状の数列 - つまり数列の最初と最後が隣り合っている - が与えられる。要素同士が隣り合わないような取り方で、値の合計を最大化せよ。たとえば(1 3 4 3)だったら 6 = 3 + 3。

DP的に考える。stateは数列を左から見ていき、i番目までのサブ数列での最適解とする。各stateの持つ情報は、state[i]を使った場合の最適解と、state[i]を使わない場合の最適解の2種類。j<iでのstate[j]とstate[i]との関係については、state[i]を使う場合、使わない場合それぞれについて場合分けして考える。j=i-1(jとiが隣り合っている場合)のみ特別に場合分けして処理したけど、スマートな書き方がありそう。</ppp>

あとは数列が円状になっていることをどう処理するか。どうもいい方法が思いつかなかったので、editorialを見てみた。いわく、与えられた数列の最初の1要素がないもの、最後の1要素がないものの2つをつくり、それぞれを処理すればおっけいとのこと。なるほどー!たしかにこの2要素が同時に存在することはないもんな。かしこいなあ。

class BadNeighbors {
  int r(vector <int> donations)
  {
    int maxDonates[41][2];

    for (int i=0; i<donations.size(); i++)
      {
	maxDonates[i][0] = donations[i];
	maxDonates[i][1] = 0;

	for (int j=0; j<i; j++)
	  {
	    if (i-j == 1)
	      {
		maxDonates[i][0] = max(maxDonates[i][0], maxDonates[j][1] + donations[i]);
		maxDonates[i][1] = max(maxDonates[i][1], max(maxDonates[j][0], maxDonates[j][1]));
	      }
	    else
	      {
		maxDonates[i][0] = max(maxDonates[i][0], max(maxDonates[j][0] + donations[i], maxDonates[j][1] + donations[i]));
		maxDonates[i][1] = max(maxDonates[i][1], max(maxDonates[j][0], maxDonates[j][1]));
	      }
	  }
      }

    return max(maxDonates[donations.size()-1][0], maxDonates[donations.size()-1][1]);
  }

public:
  int maxDonations(vector <int> donations)
  {
    vector <int> tmp1 = donations;
    tmp1.erase(tmp1.begin());
    vector <int> tmp2 = donations;
    tmp2.erase(tmp2.end()-1);

    return max(r(tmp1), r(tmp2));
  }
}

2003 TCCC Semifinal Round 3

15:48

Dynamic Programming: From novice to advancedからの練習問題。

Easy - ZigZag

与えられた数列のサブ数列の中から、ジグザグになっているものの最大長を求める.ジグザグな数列とはこんなやつ: 1 5 3 19 2

チュートリアルに従って、まずはstateの定義。state iはi番目までのサブ数列での、ジグザグの最大長(最適解)とする。各stateは、最大長の値と、そこまでのサブ数列の最後の値(のインデックス)と、ジグザグの方向(sequence[i-1] < sequence[i] と、sequence[i-1] > sequence[i]のどちらなのか)を持っておけばよさそう。次にstate間の関連性を考える。チュートリアルの例題と同じように考え、state[i-1]とstate[i]を調べ、ジグザグになっていたら最大長に+1する、という方法で考えた。

実装する。でもテストケース#5が通らない。そうかある要素がジグザグになっていたとしても、あえてそれをスキップすることで、最終的に最長になるパターンも考えられる。チュートリアルは単調増加の数列を探していたけど、それとは違うもんな。てことはstateでもっておく情報をもっと増やす必要がありそう。うーん。他の人のコード見てみる。

ポーランドebdさんという人のコードがエレガントで感動する。なるほど、state[i]ごとに、j<iな全てのjについて最大長にならないか調べることによって、スキップに対応している。あと2次元配列を使ったジグザグの調べ方がとてもエレガント。今の自分ではとても思いつかんな…</ppp>

まだDPの考え方に慣れてないです。今回の敗因は、stateの最適解と思っていた値が、全然最適解じゃなかったところです。

class ZigZag {
public:
  int longestZigZag(vector <int> sequence)
  {
    int ret = 0;
    int zigzag[51][2];

    for (int i=0; i<sequence.size(); i++)
      {
	zigzag[i][0] = zigzag[i][1] = 1;
	for (int j=0; j<i; j++)
	  if (sequence[j] < sequence[i])
	    zigzag[i][0] = max(zigzag[i][0], zigzag[j][1]+1);
	  else if (sequence[j] > sequence[i])
	    zigzag[i][1] = max(zigzag[j][0], zigzag[j][0]+1);

	ret = max(ret, max(zigzag[i][0], zigzag[i][1]));
      }

    return ret;
  }
}