More Related Content
Viewers also liked (12)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
会津合宿2015顿补测3：颁问题
- 3. 問題概要 レジの数：n（1 <= n <= 10^15） 客の人数：m（1 <= m <= 10^5） レジを通る回数：k（1 <= k <= 10^4） サゾエさんがレジを通ってから? 再びレジに並ぶまでにかかる時間：d（1<= d <= 10^4） サゾエさんの入店時間：s（0<= s <= 10^4）
- 4. 問題概要 客iがレジに並ぶ時間：a_i（0<= a_i <= 10^4） 客iが会計にかかる時間：b_i（1<= b_i <= 10^4） 客iが並ぶレジ番号：c_i（1<=c_i <= n）
- 5. 考察 n > mなのでどこかのレジは絶対に客がこない n > mの時の解はk*dになる． なのでn <= mの時を考える．
- 6. 解法 1. 各レジが空になるまでの時間を覚えておく． 2. サゾエさんと客をレジに並ぶ時間が早い順にpriorityキュー に入れる 3. キューの先頭の客が並ぶレジの会計終了時間を更新する． 4. サゾエさんの順番になったら各レジの中で会計終了時間が? 一番早いレジを選ぶ． 5. サゾエさんが次に並ぶことのできる時間がわかるので，? サゾエさんを再びキューに追加する．
- 7. 解法 1. 各レジが空になるまでの時間を覚えておく． 2. サゾエさんと客をレジに並ぶ時間が早い順にpriorityキュー に入れる 3. キューの先頭の客が並ぶレジの会計終了時間を更新する． 4. サゾエさんの順番になったら各レジの中で会計終了時間が? 一番早いレジを選ぶ． 5. サゾエさんが次に並ぶことのできる時間がわかるので，? サゾエさんを再びキューに追加する． O(m log m) O(1) O(n) O(log m)
- 8. 解法（TLE） 1. 各レジが空になるまでの時間を覚えておく． 2. サゾエさんと客をレジに並ぶ時間が早い順にpriorityキュー に入れる 3. キューの先頭の客が並ぶレジの会計終了時間を更新する． 4. サゾエさんの順番になったら各レジの中で会計終了時間が? 一番早いレジを選ぶ． 5. サゾエさんが次に並ぶことのできる時間がわかるので，? サゾエさんを再びキューに追加する． O(m log m) O(k*1) O(k*n) O(k*log m)
- 9. 想定解法 1. 各レジが空になるまでの時間を覚えておく． 2. サゾエさんと客をレジに並ぶ時間が早い順にpriorityキュー に入れる 3. キューの先頭の客が並ぶレジの会計終了時間を更新する． 4. サゾエさんの順番になったら各レジの中で会計終了時間が? 一番早いレジを選ぶ． 5. サゾエさんが次に並ぶことのできる時間がわかるので，? サゾエさんを再びキューに追加する． O(m log m) O(k*log n) O(k*log m) O(k*log n)
- 10. 想定解法 どのレジが最小の時間で会計が終わるかを毎回全て見るの ではなく，二分木で管理をする． レジの会計終了時間の更新がO(log n)になり，最小のレジ を見つけるのにO(log n)になり，全体がO((k + m)log m)
- 11. 解答例：SAMPLE sampleの場合? ans = 0 1 2 3 1 0 0 0 2 3 4 （1, 2, 3） . .
- 12. 解答例：SAMPLE 1 2 3 1 0 0 0 2 3 4 （1, 2, 3） . . sampleの場合? ans = 0
- 13. 解答例：SAMPLE 1 2 3 1 0 0 3 2 3 4 （1, 2, 3） . . sampleの場合? ans = 0
- 14. 解答例：SAMPLE 1 2 3 2 0 0 3 3 4 5 （1,1,2） . . sampleの場合? ans = 0
- 15. 解答例：SAMPLE 1 2 3 2 0 0 3 3 4 5 （1,1,2） . . sampleの場合? ans = 0
- 16. 解答例：SAMPLE 1 2 3 2 0 2 3 3 4 5 （1,1,2） . . sampleの場合? ans = 0
- 17. 解答例：SAMPLE 1 2 3 3 0 2 3 4 5 6 （2,3,1） . . sampleの場合? ans = 0
- 18. 解答例：SAMPLE 1 2 3 3 5 2 3 4 5 6 （2,3,1） . . sampleの場合? ans = 0
- 19. 解答例：SAMPLE 1 2 3 4 5 2 3 5 6 7 （3,4,2） . . sampleの場合? ans = 0
- 20. 解答例：SAMPLE 1 2 3 4 5 2 3 5 6 7 （3,4,2） . . sampleの場合? ans = 0
- 21. 解答例：SAMPLE 1 2 3 4 5 2 7 5 6 7 （3,4,2） . . sampleの場合? ans = 0
- 22. 解答例：SAMPLE 1 2 3 5 5 2 7 6 7 8 . . sampleの場合? ans = 0 （3）
- 23. 解答例：SAMPLE 1 2 3 5 5 2 7 6 7 8 . . sampleの場合? ans = 0 （3）
- 24. sampleの場合? ans = 0 解答例：SAMPLE 1 2 3 5 5 2 7 6 7 8 . . もう一度 追加する