【競プロ】寿司を食べながらSushiを解いてみた【企画】

<b>この記事は 「<a href = "https://adventar.org/calendars/6713">競プロ Advent Calendar 2021</a>」の 12 日目の記事です.</b>

こんにちは.Rute(リュート)です.<a href = "https://twitter.com/rute_not_route">Twitter(@rute_not_route)</a>
普段は, 競技プログラミングの問題の解説をYouTube上に投稿しています.

早速ですが, 今回の企画内容を発表します.
ズバリ...
<h4><font color="red">寿司</font>を食べながら<font color="red">Sushi</font>を解いてみた</font></h4>

なぜ前者の寿司が**「寿司」**で後者の寿司が**「Sushi」**なのか.
**「Sushi」を解く**と聞いて, 一部の競技プログラマーの方はもう察したかもしれませんが, 意味としてはこうなります

:::note info
<b>寿司を食べながらEDPCのJ問題「Sushi」を解いてみた</b>
:::

# 1. きっかけ
私は今年の10月から, EDPCの問題を解き続けていました.
**DP(動的計画法)の問題は,問題文のどのパラメータを変数にするかを考えて,効率良く計算できるようにする**
ということを根に持ちながら解いていました.

問題1:EDPCのA問題,「Frog 1」という問題では
**$dp[i]$ = i番目の足場に到達するまでの最小コスト**

問題2:EDPCのD問題, 「Knapsack 1」という問題では
**$dp[i][j]$ = i番目までの荷物を使って重さjの組み合わせを作った時の利益の最大値**

というように,問題文と制約からパラメータを見極めることによって
問題1では**$O(2^N)$**から$O(N)$に,
問題2では**$O(2^N)$**から$O(NW)$に
計算量を落とすことが可能となります.
(厳密には,時間計算量ではなく**空間計算量**ですが)

私は, EDPCのI問題までは問題無くACすることは出来たのですが,ある1つの問題でかなり苦労することになりました.
それが前述した**EDPCのJ問題「Sushi」**です.
<a href = "https://atcoder.jp/contests/dp/tasks/dp_j">問題はこちら</a>

わかりやすく問題文を説明すると,

>$N$皿の寿司の情報$a_1,a_2, ... a_N$が与えられます.($1 \leq a_i \leq 3$)
以降,$i$皿目の皿を**「皿$i$」**と言うことにします.
$a_i$は皿$i$に載っている寿司の数です.
$1$～$N$までの数字が等確率で出るサイコロがあります.
サイコロを振り,出た目と同じ番号の皿に寿司があった場合,その皿の寿司を1貫食べます.
これを, <b>全ての皿から寿司がなくなるまで</b>続けます.
この時の, 操作回数の期待値を計算して下さい. ただし標準誤差$10^{-9}$まで許容されます.

この問題を, 3時間かけて一度考えたのですが, これまでのI問題までに比べ問題の難易度が上がったためか, **解くことが出来ませんでした...**
そこで考えたことがあります.

**「競技プログラミングの問題, 実際に再現しながら解いたら解けるのか」**と.

<font color="Gray">(多分,1ミリもそんなことを考えたことが無い方が多いでしょうけれど)</font>

実際,競技プログラミングの問題は<b>実際に再現が出来ないもの</b>がほとんどです.
例えば,ABC229のC問題では入力の制約だと最大で<b>$3.0 × 10^{8}$[g]</b>程度のチーズを用意する必要があります. 
これは, 例えばドミノピザの$2$[kg] $(=2000)$[g]チーズピザを, <b>15万枚</b>用意しないといけません. 

この「Sushi」という問題では, 
<font color="red">$1 \leq N \leq 300$, $1 \leq a_i \leq 3 (1 \leq i \leq N)$</font>
という制約で, かつ入力例だけでも高々<font color="red">$10$皿の皿と$23$貫のお寿司を用意すれば再現が可能</font>なので, 「Cheese」という問題よりも<b>再現性が高いと考えられそうです.</b>

**ということで, 実際に入力例を作成するために, 寿司と皿を購入することにしました.**
#2. 準備

:::note info
用意するもの
<b>・寿司(23個以上)</b>
<b>・皿(10皿以上)</b>
:::
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">EDPC J問題「Sushi」の<br>入力例1, 入力例2, 入力例3(実物)です. <a href="https://t.co/4LmR7xMcvd">pic.twitter.com/4LmR7xMcvd</a></p>&mdash; Rute(リュート)🐙🔥🚲📈⌨️🌸🍓 (@rute_not_route) <a href="https://twitter.com/rute_not_route/status/1467330350884229120?ref_src=twsrc%5Etfw">December 5, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

**<お詫び>**
今回, 入力例を再現するにあたり, 机の上に横並びでおける皿の限界が<b>5皿</b> だったため, 入力例4を再現することができませんでした. 
<b>どなたか, 横に10皿以上並べることの出来る机をお持ちの方, ぜひ入力例4を再現してQiitaなどに投稿して頂きたいと思います.</b>

寿司を用意したところで, 私はYouTube上にて配信をすることにしました.(後述するYouTube動画より閲覧することが可能です)

#3. 解答
12:30, 当初より30分遅れてしまいましたが, 配信を開始しました.
開始30分くらいは今回購入した寿司に関するトークを行いましたが, 進捗がないことに気づきさっさと問題を解くことにしました.

実際, 1ヶ月前の配信にてある程度DPテーブルの方針は定まっていました.
**$dp[i][j][k] = $**

- 寿司が皿に全く乗っていない状態から,
- 寿司が1貫乗っている皿が$i$枚,
- 寿司が2貫乗っている皿が$j$枚、
- 寿司が3貫乗っている皿が$k$枚

**ある状況にするまでの操作回数の期待値**
となるようにDP遷移を行うようにします.
この時の$dp[a.count(1)][a.count(2)][a.count(3)]$が答えになります.

ここまでを思い出し, 式を定義してみることにしました.

遷移式は,以下のような式によって定義することができます.

$dp[i][j][k] = dp[i][j][k] * \frac{N-i-j-k}{N} + dp[i+1][j][k] * \frac{i}{N} + dp[i-1][j+1][k] * \frac{j}{N} + dp[i][j-1][k+1] * \frac{k}{N} + 1$

式の説明を行います.
まず, 毎回以下の確率によってそれぞれの状況への遷移が行われます.

|確率　　|遷移先　　　　　　|
|---|---|
|$ \frac{N - i - j - k}{N}$|$dp[i][j][k]$|
|$ \frac{i}{N}$|$dp[i+1][j][k]$|
|$ \frac{j}{N}$|$dp[i-1][j+1][k]$|
|$ \frac{k}{N}$|$dp[i][j-1][k+1]$|

これをもとに, $dp[i][j][k]$を計算すると上記の式となりますが, ここで注意すべきなのは<font color="red">$dp[i][j][k]$ という項が左辺と右辺に来ていてややこしくなっている</font>ということです.
この問題を解消するために, $dp[i][j][k]$を左辺にまとめると,このような式となります.

$dp[i][j][k] = dp[i+1][j][k] * \frac{i}{i+j+k} + dp[i-1][j+1][k] * \frac{j}{i+j+k} + dp[i][j-1][k+1] * \frac{k}{i+j+k} + \frac{N}{i+j+k}$

分数をひとまとめにすると, こんな感じです！！(投げやり)

<font color="red">$dp[i][j][k] = \frac{i*dp[i+1][j][k] + j*dp[i-1][j-1][k] +  k*dp[i][j-1][k+1] + N}{i+j+k}$</font>

以上の式を立てて各$dp[i][j][k]$を計算し, $dp[a.count(1)][a.count(2)][a.count(3)]$を出力すればよいです.

dpに関してはメモ化再帰か再帰関数で書くか悩みましたが, $dp[i][j][k] = 0$の間で再帰的に計算する関数を立てて$dp[a.count(1)][a.count(2)][a.count(3)]$を計算しました.

<details><summary>解答コード(Python)</summary><div>

```python
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int,input().split()))
dp = [[[0 for _ in range(N+1)]for _ in range(N+1)]for _ in range(N+1)]
S = 0
T = 0
U = 0
for i in range(N):
  if A[i] == 1:
    S += 1
  elif A[i] == 2:
    T += 1
  else:
    U += 1
def f(i,j,k):
    #print(i,j,k)
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    if i - 1 >= 0:
    	B = f(i-1,j,k) * i 
    else:
        B = 0
    if j -1 >= 0:
    	C = f(i+1,j-1,k) * j 
    else:
        C = 0
    if k - 1 >= 0:
    	D = f(i,j+1,k-1) * k 
    else:
        D = 0
    dp[i][j][k] = (B + C + D + N)/(i+j+k)

    return (B + C + D + N)/(i+j+k)
print(f(S,T,U))
```

</div></details>

本番で用意した寿司の個数は40貫でしたが, 結局のところ<b>16貫</b>を食べた段階でACすることができました.
(ちなみに余った寿司は食べきりましたのでご安心下さい)

考察をどのように行ったかに関しては, **このQiita記事で書くと長くなりますので, 動画にてご覧ください.**
<iframe width="560" height="315" src="https://www.youtube.com/embed/8yJE4Ca7tlI" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

#4. まとめ
個人的な感覚なのですが,<b>寿司</b>を食べながら競技プログラミングの問題を解くと, <b>従来よりも問題に対する考察がしやすくなったと思っています.</b>
ただし, 寿司に含まれる糖質の量は10貫で75g程度となっております. そのため, 糖質制限などを取り入れている方は, 入力例4を再現するだけで<b>23貫</b>の寿司が必要になりますのでご注意下さい.

皆さんも, この機会に<b>寿司</b>を食べながら問題を解いてみてはいかがでしょうか.特に「Sushi」という問題では, 実際の入力例を再現することが出来る, というメリットがあります.

今回は企画に関する記事だったため, 通常のQiita記事よりも短い構成で記述しました. ここまで読んで頂き, ありがとうございました.