一流の団子職人
解説：星井智仁問題概要
N色の団子がそれぞれM個ずつ 合計NM個ある
NM個ある団子を色が相異なるようにN個ずつM組に分けたい
使う団子を団子チェッカーにいくつか指定すると作れる串の数を教えてくれる
ただし団子チェッカーを使える回数は50000回以下である

1

小課題

1. N=4, M=4
2. N=100, M=10
3. N=200, M=25
4. N=400, M=25

2

小課題

1. N=4, M=4
2. N=100, M=10
3. N=200, M=25
4. N=400, M=25

3

小課題１ N=4 M=4N=4, M=4団子はNM=16個ある
全通り試せるかな

4

小課題１ N=4 M=4N=4, M=4団子はNM=16個ある
全通り試せるかな
162 =65536>50000

試せない

5

小課題１ N=4 M=4N=4, M=4
団子はNM=16個ある
全通り試せるかな

C4=1820≦50000
試せる
166

小課題

1. N=4, M=4
2. N=100, M=10
3. N=200, M=25
4. N=400, M=25

7

小課題２ N=100 M=10
N=100, M=10
団子はNM=1000個ある
23
1000C10≈2×108

小課題２ N=100 M=10
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり=１つでも欠けていると判定されない

この範囲だと0

この範囲だと1

9

10

発想を逆転させよう小課題２ N=100 M=10
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり=１つでも欠けていると判定されない→全選択し、いくつか取り除いて判定

11

小課題２ N=100 M=10
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり=１つでも欠けていると判定されない→全選択し、いくつか取り除いて判定

最悪はざっくりN×M2/2=50000回
これはざっくり見積もりすぎで、もうちょっと回数は少ない

12

小課題

1. N=4, M=4
2. N=100, M=10
3. N=200, M=25
4. N=400, M=25

13

小課題３ N=200 M=25
小課題２:全選択し、いくつか取り除いて判定

最悪はざっくりN×M2/2回

14

小課題３ N=200 M=25
小課題２:全選択し、いくつか取り除いて判定

最悪はざっくりN×M /2
2

15

小課題３ N=200 M=25
小課題２:全選択し、いくつか取り除いて判定

最悪はざっくりN×M2/2

16

小課題３ N=200 M=25
小課題２:全選択し、いくつか取り除いて判定

平均

はざっくりNMlogeN回

ランダムに選ぶと調和級数に落ちる 27000回くらい

これを撃墜するジャッジがこの世に存在する気がしないので、書いてみると通ります17

小課題３ N=200 M=25あまりに酷い解法を紹介してしまったのでマシな解法も紹介します18

小課題３ N=200 M=25
思い出そう
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり
この範囲だと0

この範囲だと1

19

小課題３ N=200 M=25
思い出そう
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり
この団子の持つ意味は？
この範囲だと0

この範囲だと1

20

小課題３ N=200 M=25
思い出そう
団子チェッカーで「団子１串作れる」と判定される条件→すべての色が揃う必要あり
この団子の持つ意味は？
この範囲だと0→初めて現れる色の団子

この範囲だと1

21

小課題３ N=200 M=25
二分探索で「初出の団子」の位置がlog(NM)回でわかる

この団子の持つ意味は？
この範囲だと0→初めて現れる色の団子

この範囲だと1

22

小課題３ N=200 M=25
二分探索で「初出の団子」の位置がlog(NM)回でわかる

この範囲+だと0

この範囲+だと123小課題３ N=200 M=25
二分探索で「初出の団子」の位置がlog(NM)回でわかる
繰り返すとNlog(NM)回で1本の串団子が作れる
この範囲+

だと0

この範囲+だと124

小課題３ N=200 M=25

25

団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる（スライドでは二分探索をしていない）
使う
←知りたい

余り

クエリの結果1

小課題３ N=200 M=25

26

団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる（スライドでは二分探索をしていない）
使う
←知りたい

余り

クエリの結果1

小課題３ N=200 M=25

27

団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる（スライドでは二分探索をしていない）
使う
←知りたい

余り

クエリの結果1

小課題３ N=200 M=25

28

団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる（スライドでは二分探索をしていない）
使う
←知りたい

余り

クエリの結果2

小課題３ N=200 M=25

29

団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる（スライドでは二分探索をしていない）
使う
←知りたい

余り

クエリの結果2

小課題３ N=200 M=25
団子が1串作れたら残ったそれぞれの団子について全体から取り除いて質問してどの色であるか二分探索ができる

Nlog(NM)+NMlogN=41000 くらい
回

30

小課題

1. N=4, M=4
2. N=100, M=10
3. N=200, M=25
4. N=400, M=25

31

小課題４ N=400 M=25
串をM本用意して 串に団子を刺していくことを考える
未確定

この後に説明する操作をすると 上図のように単調性をもつように串に団子を刺せる32

小課題４ N=400 M=25
串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する
未確定

この後に説明する操作をすると 上図のように単調性をもつように串に団子を刺せる33

小課題４ N=400 M=2534

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定←どこに刺せるか知りたい小課題４ N=400 M=2535

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

5がある→値がずれない小課題４ N=400 M=2536

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

4がある→値がずれない小課題４ N=400 M=2537

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

3がある→値がずれない小課題４ N=400 M=2538

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

2がある→値がずれない小課題４ N=400 M=2539

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

2がない→値が大きいほうにずれる小課題４ N=400 M=2540

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

1がない→値が大きいほうにずれる小課題４ N=400 M=2541

串をM本用意して 串に団子を刺していくことを考える
どこの串に刺せるかを二分探索する (スライドだと二分探索していない)
未確定

使
う
クエリの結果←どこに刺せるか知りたい

1がない→値が大きいほうにずれる小課題４ N=400 M=25NMlogM=45000くらい
未確定←どこに刺せるか知りたい42

得点分布 JOI0243722100

得点分布 JOIG

0445100