Pythonで蟻本2-2 - 貪欲法

蟻本2-2は貪欲法です．

背景：蟻本をやります - 競プロはじめました
テキスト：

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

硬貨の問題

【入力】
3 2 1 3 0 2
620
【出力】
6 (1円玉0枚, 5円玉2枚, 10円玉1枚, 50円玉2枚, 100円玉0枚, 500円玉1枚)

【コード】

c = list(map(int, input().split()))
a = int(input())

v = [1, 5, 10, 50, 100, 500]
ans = 0
ans2 = []  # 追加
for p in v[::-1]:
  t = min(a//p, c[v.index(p)])
  a -= t*p
  ans += t
  ans2.append(t)  # 追加

# 追加
ans3 = [str(p) + '円玉' + str(q) + '枚' for p, q in zip(v, ans2[::-1])]
print('{} ({})'.format(ans, ', '.join(ans3)))

区間スケジューリング問題

【入力（わざと順番を入れ替えています）】
5
4 6 8 1 2
7 9 10 3 5
【出力】
3 (仕事1, 3, 5を選択)

【コード】

n = int(input())
s = list(map(int, input().split()))
t = list(map(int, input().split()))

inv = sorted([[a, b] for a, b in zip(t, s)])

ans, fin = 0, 0
ans_list = [] # 追加
for a, b in inv:
  if fin < b:
    ans += 1
    ans_list.append(str(sorted(s).index(b)+1)) # 追加
    fin = a
    
print('{} (仕事{}を選択)'.format(ans, ', '.join(ans_list)))

【ポイント】
「私」がある仕事を終えた後，終了時刻が最も早い仕事に飛びくことで，こなせる仕事が他の人より少なくなり得るか？を考えると，これはありえません．

なぜなら，他の仕事を選んだ人がその仕事を終えたときには，「私」はさらに次の仕事を選べており，その仕事は（まだ始まってないかもしれないが）他の人が選ぶどの仕事よりも早く（あるいは同時に）終了するからです．つまり，「私」は選んだ各仕事の終了時刻において，他の人以上の仕事をこなしています．

Best Cow Line

【入力】
6
ACDBCB
【出力】
ABCBCD

【コード】

n = int(input())
s = input()

ans = ''
while len(s) > 0:
  if s < s[::-1]:
    ans += s[0]
    s = s[1:]
  else:
    ans += s[::-1][0]
    s = s[:len(s)-1]
    
print(ans)

Saruman's Army

【入力（最終行：わざと順番を入れ替えています）】
6
10
20 30 50 1 7 15
【出力】
3

【コード】

n = int(input())
r = int(input())
x = sorted(list(map(int, input().split())))

i, ans = 0, 0
while i < n:
  s = x[i]
  while i < n and x[i] <= s+r:
    i += 1
  p = x[i-1]
  while i < n and x[i] <= p+r:
    i += 1
  ans += 1
    
print(ans)

【ポイント】
whileを使った素直な書き方が参考になります．if で分岐させようとすると，複雑になってしまいます．

Fence Repair

【入力】
3
8 5 8
【出力】
34
【コード】

n = int(input())
l = sorted(list(map(int, input().split())))

ans = 0
while len(l) > 1:
  ans += l[0] + l[1]
  del l[:2]
  l.append(ans)
  l.sort()

print(ans)

【ポイント】
書籍のコードについて：
最も短い2つの板を特定した後，①t=L[mii1]+L[mii2]を配列に追加する，②L[mii1]とL[mii2]を配列から除く，③mii1, mii2≠N-1なら次のステップで参照しないL[N-1]の値をL[i] (0 ≦ i < N-2)のどこかに移動させる，という3つの操作が必要です．これらは，L[mii1]に和tを上書きし，L[mii2]にL[N-1]を上書きすることで同時に達成できます．ここで，mii2=N-1でも問題なく処理ができます．しかし，mii1=N-1だと，L[mii1]=L[N-1]をtで上書きした後に，L[mii2]がL[N-1]を参照できずtが代入されてしまって問題になります．したがって，これを避けるため，mii1=N-1の場合にmii1とmii2を入れ替える処理がされています．

アルゴリズムの説明（二分木を使う方法）：
バラバラにした板を，部品と呼びます．このとき，「各部品由来のコスト＝部品のコスト（板の長さ）×節点の深さ」となります．これは，二分木の各葉○を部品のコスト（板の長さ）の和でバラして書けば理解できます．つまり，ある葉がA+B+Cだとすると，その上の葉にもA+B+Cが現れます．よって，各部品にかかるコストは，最も深い葉から最も上位の葉まで1回ずつ現れます．

その上で，このアルゴリズムの正しさは次のように説明できます．

まず，二分木の分岐のさせ方は色々考えられますが，何か1つ固定します．このとき，末端の葉には，各部品（のコスト）が1回ずつ現れます．あとは各部品の配置をどう決めるかですが，上の結果から，コストが最小となるとき，最も安い部品が最も深いところに配置されます．ここで，最も深い葉は，最後に2つに分割する板なので，かならずペアで現れます．よって，最も安い部品2つをこの2つの葉に対応させれば良いことがわかりました．ここまでで，最後に分割される2部品が決定したわけですが，この2部品を分割する前のステップに戻れば，1つ部品が減っただけで同じ問題になります．よって，また安い2部品を見つけて同じ処理をすればよいのです．さらに，ここまでの考え方は，はじめに固定した「二分木の分岐のさせ方」には依存しないのです！

アルゴリズムの説明（二分木を使わない方法）：
二分木を使わなくても，簡単に説明できそうだと思って考えたのですが，ちょっと思いつきませんでした．そのうち，考えてみたいです（忘れるパターン）．