fc2ブログ



カード

2009.07.14 19:26  パソコン甲子園 2006

パソコン甲子園 2006 カード


連鎖行列積問題の解法と同様に動的計画法で解きます。

例えば、下図のように5枚のカードの山があるとします。

パソコン甲子園 2006 カード


まず最初に、隣り合う2組の山を重ねるときの最小のコストを計算します(j = 1)。
i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。

つぎに、隣り合う3組の山を重ねるときの最小のコストを計算します(j = 2)。
i = 1, 2, 3 について計算します。

つぎに、隣り合う4組の山を重ねるときの最小のコストを計算します(j = 3)。
i = 1, 2 について計算します。

同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。
i = 1 について計算します。


各 j の値での最小コストの計算方法を考えます。
例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります:

  • カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+1)
  • カードの山[1,2]とカードの山[3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+2)
  • カードの山[1,2,3]とカードの山[4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+3 = i+j)

スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Discrete Speed

2009.07.09 22:48  ACM/ICPC 2009

Discrete Speed
ダイクストラのD。
「現在の場所、前にいた場所、速度」のノードでグラフを作りました。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




Verbal Arithmetic

2009.07.09 22:40  ACM/ICPC 2009

Verbal Arithmetic
バックトラックで解いてみました。 適当な枝刈りをすれば手元で10秒くらいorz。

優れた解法はlaycurseさんのブログを参照。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




How Many Islands?

2009.07.09 22:34  ACM/ICPC 2009

How Many Islands?
パソコン甲子園に同じような問題が出題されていたような...

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |




Next Mayor

2009.07.09 22:30  ACM/ICPC 2009

Next Mayor

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




ACM-ICPC 国内予選 2009

2009.07.09 22:26  ACM/ICPC 2009

番号問題難易度
A Next Mayor
B How Many Islands?
C Verbal Arithmetic ★★☆
D Discrete Speed ★★★
E Cards ★★★☆
F Tighten Up! ★★★★☆

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(4) | トラックバック(0) | ↑ページトップ |