この記事は「競プロ Advent Calendar 2021」の 12 日目の記事です.

こんにちは.Rute(リュート)です.Twitter(@rute_not_route)
普段は, 競技プログラミングの問題の解説をYouTube上に投稿しています.

早速ですが, 今回の企画内容を発表します.
ズバリ...

寿司を食べながらSushiを解いてみた

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

寿司を食べながらEDPCのJ問題「Sushi」を解いてみた

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」です.
問題はこちら

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

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

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

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

(多分,1ミリもそんなことを考えたことが無い方が多いでしょうけれど)

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

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

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

2. 準備

用意するもの ・寿司(23個以上) ・皿(10皿以上)

EDPC J問題「Sushi」の
入力例1, 入力例2, 入力例3(実物)です. pic.twitter.com/4LmR7xMcvd
— Rute(リュート)🐙🔥🚲📈⌨️🌸🍓 (@rute_not_route) December 5, 2021

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

寿司を用意したところで, 私は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]$を計算すると上記の式となりますが, ここで注意すべきなのは$dp[i][j][k]$ という項が左辺と右辺に来ていてややこしくなっているということです.
この問題を解消するために, $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}$

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

$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}$

以上の式を立てて各$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)]$を計算しました.

解答コード(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))

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

考察をどのように行ったかに関しては, このQiita記事で書くと長くなりますので, 動画にてご覧ください.

4. まとめ

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

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

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

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

寿司を食べながらSushiを解いてみた

1. きっかけ

2. 準備

3. 解答

4. まとめ