Pythonで蟻本2-7 - GCJの問題に挑戦してみよう(1)

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

作者:秋葉拓哉,岩田陽一,北川宜稔
発売日: 2012/01/28
メディア: Kindle版

【2021.05.04〜2021.05.05】

Minimum Scalar Product
Crazy Rows
Bribe the Prisoners
Millionaire

Minimum Scalar Product

【入力1】

3
1 3 -5
-2 4 1

【出力1】

-25

【入力2】

5
1 2 3 4 5
1 0 1 0 1

【出力2】

【コード】

n = int(input())
v1 = sorted(list(map(int, input().split())))
v2 = sorted(list(map(int, input().split())), reverse=True)
print(sum([v1[i]*v2[i] for i in range(n)]))

Crazy Rows

最も条件が厳しいところから順に決めていくのがポイントです．

ある行に配置できるものは，その下の行にも配置できるため，上の行に配置するほど難しいです．よって，上の行から順に決めていきます．

手順は，①決める行iを上から順に1つ選び，②i行に配置できる最も近い行jを選び，③行jを行iまで移動させる，です．

②において，毎回，行列の1の場所を探すのは計算のムダなので，最初に各行iで最後に1が現れる列をa[i]=jとして記憶しておきます．

【入力1】

2
1 0
1 1

【出力1】

【入力2】

【出力2】

【入力3】

【出力3】

【コード】

n = int(input())
m = [list(map(int, input().split())) for _ in range(n)]

# aの初期化
a =[-1]*n  # i行目に1がないならa[i]=-1
for i in range(n):
  for j in range(n):
    if m[i][j] == 1:
      a[i] = j

res = 0
for i in range(n):
  # i行目に持ってくる行jを見つける(必ずある)
  # pos = -1 ←不要では?
  for j in range(i, n):
    if a[j] <= i:
      # a[j]=-1も引っかかる
      pos = j
      break
  
  # j行目をi行目まで持ってくる
  for j in reversed(range(i+1, pos+1)):
    a[j], a[j-1] = a[j-1], a[j]
    res += 1
  
print(res)

Bribe the Prisoners

端以外の囚人を開放するたびに，互いに影響しない2つのブロックに分かれていきます．ブロックの大きさはどんどん小さくなっていくので，動的計画法で再帰的に計算できます．

i番目の部屋とj番目の空き部屋に挟まれたブロック（間に空室はないとする）の中にいる，$a_{i+1},...,a_{j-1}$の囚人を全て解放するときに必要な金貨の最小値をdp[i][j]とします．

このとき，0番目，Q+1番目に仮想的な空き部屋を加えることで，端の囚人を解放した際も2ブロックに分かれたとみなすことができ，統一的に処理できます．

ブロックのあり得る可能性は，両端を選ぶ組み合わせなので$(Q+2)(Q+1)/2 = O(Q^{2})$通りです．動的計画法では，各ブロックに対して，囚人を開放するパターン$O(Q)$を全て試すので，トータルの計算量は$O(Q^{3})$となります．

解放対象の$i$番目の囚人$a_{i}$の部屋番号をa[i]とします．

【入力1】

8 1
3

【出力1】

【入力2】

20 3
3 6 14

【出力2】

【コード】

p, q = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a + [p+1]

# dp[i][j], 0<=i<=Q, 1<=j<=Q+1 (j=0は使わない), i<j
dp = [['']*(q+2) for _ in range(q+1)]
## 初期化 (間に解放対象がいないなら金貨ゼロ枚)
for i in range(q+1):
  dp[i][i+1] = 0
  
for n in range(1, q+1):
  # n=ブロック内の解放対象人数
  # i,j=ブロック(左端,右端)の部屋番号
  # j = i+n+1 < q+2
  for i in range(q-n+1):
    j = i + n + 1
    
    t = float('inf')
    for k in range(i+1, j):
      # 1人開放すればブロック数が小さいdpに帰着
      # →1人開放する方法の最小値が今のブロック数の答え
      t = min(t, dp[i][k]+dp[k][j])
    
    # ①1人解放したブロックのコスト + ②1人開放するコスト
    # ②=(a[j]-1) - a[i] - 1(解放した1人の分)
    dp[i][j] = t + a[j] - a[i] - 2

print(dp[0][q+1])

Millionaire

う〜ん，難しい．明快な説明ができません．汎用性のある，システマチックな考え方をしたいのですが．．．
（遷移図など，うまい表現方法がありそうですが．．．）

最終的な目標金額をZ (=\$1,000,000) とします．
最後の1ラウンドで$Z$を得られる確率（とその最善の戦略）は

所持金が$[0,Z/2)$：確率ゼロ
所持金が$[Z/2, Z)$：確率$P$（掛け金$\in [Z/2, Z)$）
所持金が$[Z,\infty)$：確率$1$（掛け金$\in [0, Z)$）

となります．

次に，最後の2ラウンドを考えます．上の各所持金の区間にいる場合，何も賭けなければノーリスクで最終ラウンドの該当する所持金区間に遷移できます．

したがって，次ラウンドの上位の所持金区間に遷移できる確率がゼロであれば，賭けをしても意味がありません．賭け金として意味があるのは，最終ラウンドの所得金額区間の長さである$Z/2$の半分，つまり$Z/2^{2}$です（賭けに勝てば賭け金が倍になるため）．

同様に，残り$r$ラウンドあるときに，確率が変わる所得金額区間が$Z/2^{r}$刻みであるとします．残り$r+1$ラウンドあるときを考えると，残り$r$ラウンドの上位所得金額区間に遷移するために意味のある賭け金は$Z/2^{r+1}$の倍数となります．よって，残り$r+1$ラウンドあるときの確率が変わる所得金額区間は$Z/2^{r+1}$刻みに$2^{r+1}+1$分割されることがわかります．

上の結果を受けて，所得金額区間$I_{i}$を

\begin{aligned}
I_{i}
=
\begin{cases}
\, [iZ/2^{M}, (i+1)Z/2^{M}) & (i=0,1,...,2^{M}) \\
\, [Z, \infty) & (i=2^{M}+1)
\end{cases}
\end{aligned}

と定めます（$r$ラウンドでは$2^{r}$を考えれば十分なような？）．

残り$r+1$ラウンドあるときの所得金額$\in I_{i}$の場合に，最終的に$Z$を得る確率の最大値nxt[i]を求めることを考えます．これは，残り$r$ラウンドの結果が求まっていれば，賭け金$j Z/2^{M}$を全通り試すことで算出できます．

具体的には，残り$r$ラウンドの各所得金額区間$I_{i}$での確率prv[i]が求められていれば，賭け金$j Z/2^{M}$で勝ったときと負けたときを考え，

\begin{aligned}
\mathrm{nxt\,}[i]
=\max_{j} \bigl\{ p\cdot \mathrm{prv\,}[i+j] + (p-1)\cdot \cdot \mathrm{prv\,}[i-j] \bigr\}
\end{aligned}

と計算できます．

ここで，賭け金として許される$j$は

\begin{aligned}
\begin{cases}
\, i+j \leq n\\
\, i-j \geq 0
\end{cases}
\Leftrightarrow
\begin{cases}
\, j\leq n-1 \\
\, j\leq i
\end{cases}
\end{aligned}

より$j\leq \min(i, n-1)$となります（コード中のjubはj_{upper bound}の意味？）．

【入力1】

1
0.5
500000

【出力1】

0.5

【入力2】

3
0.75
600000

【出力2】

0.84375

【コード】

from copy import deepcopy

m = int(input())
p = float(input())
x = int(input())

n = 1<<m # 2^m

# 残り0ラウンド(最終ラウンド後)では
# $1M持ってるときだけ確率1，それ以外の確率は0
prv = [0]*(n+1)
prv[n] = 1

nxt = ['']*(n+1)

for r in range(m):
  # 残りr+1ラウンドのとき，所得金額区間I_iの確率を最大化
  for i in range(0, n+1):
    # 賭け金を全通り試す
    jub = min(i, n-i)
    t = 0
    for j in range(jub+1):
      t = max(t, p*prv[i+j] + (1-p)*prv[i-j])
    nxt[i] = t  # 残りr+1ラウンド・区間I_iの確率
  # prv, nxt = nxt, prv でも良い
  prv = deepcopy(nxt)  # prv = nxt は不可
  
i = x*n//1000000  # x ∈ I_i (i=0~2^m)
print(prv[i])

【メモ】
prv = nxt だと参照渡しになりバグる（例えば入力2）．
prv, nxt = nxt, prv の動作がよくわからない，nxtにprvを代入しても使わないので，deepcopyにしておいた．