今日は蟻本のCh.2 貪欲法のあたりから。ここまではまぁそれなりに読み進めましたけど，はじめて詰まった感じになったのが，このFenceRepair（POJ 3253）の問題でした。

まず，問題文から直接読み取れるコストは以下である。

１．　　１５の板を７と８に切断・・・コスト１５
２－１．　７の板を３と４に切断・・・コスト７
２－２．　８の板を５と３に切断・・・コスト８
３－１．　３の板を２と１に切断・・・コスト３

ただ，冒頭の解説ではこのようなことが書いてあった。

板の切り出し方は二分木に対応する。葉の節点が切り出された１つ１つの板に対応する。葉の節点の深さはその部分の切断に関わった回数と等しいためコストは「板の長さ　×　節点の深さ」の和　に対応する。

この絵で（汚いなww）色を塗っている板は先に記載した方法で計算している個所で，15の板の上に3×2などと書かれている部分が解説中の「板の長さ　×　節点の深さ」である。確かに一致している。そのあと，なんやかやと説明があって結局，一番最後の切断の前には

(L1+L2), L3, L4, ・・・,LN
※L1<L2<L3<・・・<LNという制約の下で

となっている。これを再帰的に計算していけばコストが求まる，と書かれている。まぁそれも良い。そのあとのコードを読み解くのが少し大変だった。以下，Pythonでの実装例である（多分正しいと思う）。

##################
#                #
#  入力を受け取る   #
#                #    
##################
N = int(input())
L = [0]*N
for i in range(N):
   L[i] = int(input())

ans = 0

##################
#                #
#  メインの処理　   #
#                #    
##################
while N > 1:
   mii1 = 0 #1番短い板のid
   mii2 = 1 #2番目に短い板のid
   if L[mii1] > L[mii2]:
       L[mii1], L[mii2] = L[mii2], L[mii1]

   #このfor文ですべての板を調べて，短い2枚の板のidを取得
   for i in range(2,N):
       if L[i] < L[mii1]:
           mii2 = mii1
           mii1 = i
       elif L[i] < L[mii2]:
           mii2 = i

   #短い2枚の板をつなげた長さを取得
   t = L[mii1] + L[mii2]
   ans += t

   #次のループの準備
   if mii1 == N-1:
       mii1, mii2 = mii2, mii1

   #mii1は一番短い板なので，（その候補として）短い2枚を結合した板の長さtを格納
   L[mii1] = t
  
   #2枚の板を結合したので，Nを1減らすべきだが，N-=1する前にL[N-1]を退避する
   #mii2は結合したため不要になるので，そこにL[N-1]を格納する
   L[mii2] = L[N-1]
   #2枚の板を結合したので，Nを1減らす
   N-=1

#答えの出力
print(ans)

と少しコメントを足してみたがわかりやすいかというとそうでもないが自分では理解した（つもり）。特にわかりにくかったのが，一番最後のあたりの

   L[mii2] = L[N-1]

これである。はて？という感じでしたが図を書けばまぁ納得しました。whileのループをN>1の条件で回しているのでNを減らして（板の枚数を減らす，リストLの要素数を減らす）いかないとループが終了しません。しかし，各回の処理終了時点で，次のループに不要になるのはL[mii1]とL[mii2]であって，L[N-1]は必要です。したがって単純にN-=1とするとL[N-1]が失われてしまいます。そこで不要となったL[mii2]にL[N-1]を退避させることで，安心してN-=1とすることができます。