Script antifanta21

奥深き競技プログラミングの世界 〜 第2問・解答編 〜

さて勝手に始めている競技プログラミングシリーズの解答編第2問
前回同様にだいぶ時間が空いてしまったのだがまだ引き続き忙しい時間は続きそうなので少しずつでも解答編を進めていければと思う

どんな問題だったかを確認したい場合はこちらの過去記事をどうぞ
「奥深き競技プログラミングの世界 〜 第2問・出題編 〜」

第2問 「宝の地図集め」 Lv. ★★

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 最大人数と最大日数
PEOPLE_MAX_SIZE = 50
DAY_MAX_SIZE = 30
 
# （空文字が入力されるまで…）入力された文字列をスケジュールに変換する関数
def init():
    schedule = []
 
    for i in range(PEOPLE_MAX_SIZE):
        days = input()
 
        if len(days) == 0: break
 
        schedule.append({int(day) for day in days.split()})
 
    return schedule
 
# 与えられた整数を日にちで出力する関数
def printDay(day):
    print(day)
 
# 与えられたスケジュールと日にちから新しいスケジュールを作成する関数
def meeting(schedule, day):
    meet_peoples = [days for days in schedule if day     in days]
    new_schedule = [days for days in schedule if day not in days]
 
    return [new_schedule + [meet_people] for meet_people in meet_peoples] if len(meet_peoples) > 0 else [schedule]
 
# （スケジュールが纏まるか、日にちが過ぎるまで…）全パターンのスケジュールを更新して、日にちを進めて末尾再帰を行う関数
def execute(schedules, day):
    new_schedules = []
 
    for schedule in schedules:
        #print('【%s】%s' % (str(day), str(schedule)))
 
        if len(schedule) == 1: return day
        if day > DAY_MAX_SIZE: return -1
 
        new_schedules.extend(meeting(schedule, day + 1))
 
    return execute(new_schedules, day + 1)
 
# メイン関数
def main():
    printDay(execute([init()], 0))
 
if __name__ == '__main__': main()

一見すると集合型の演算を用いることで簡単に解けそうな気もするがスケジュールのパターンが複雑でそう一筋縄ではいかないと思う
結局は幅優先探索と呼ばれる全パターンを近いところから探していくアルゴリズムを末尾再帰を用いて実装し期待する結果が得られた

execute関数のprint文を有効にすると以下のように日にちを追う毎にパターンが増えつつスケジュールが統合されていくのが分かる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1     # 入力1 (=Aのスケジュール)
2 3   # 入力2 (=Bのスケジュール)
1 2   # 入力3 (=Cのスケジュール)
3 4 5 # 入力4 (=Dのスケジュール)
 
【0】[{1}, {2, 3}, {1, 2}, {3, 4, 5}] # ← 0日目（初期状態）では{1}, {2, 3}, {1, 2}, {3, 4, 5}の4人を考えれば良い (=それぞれの元に拡散中)
【1】[{2, 3}, {3, 4, 5}, {1}]         # ← 1日目（パターン1）では{2, 3}, {3, 4, 5}, {1}の3人を考えれば良い (=AとBとDの元に収集済)
【1】[{2, 3}, {3, 4, 5}, {1, 2}]      # ← 1日目（パターン2）では{2, 3}, {3, 4, 5}, {1, 2}の3人を考えれば良い (=BとCとDの元に収集済)
【2】[{3, 4, 5}, {1}, {2, 3}]         # …
【2】[{3, 4, 5}, {2, 3}]              # …
【2】[{3, 4, 5}, {1, 2}]              # …
【3】[{1}, {3, 4, 5}]                 # ← 3日目（パターン1）では{1}, {3, 4, 5}の2人を考えれば良い (=AとDの元に収集済)
【3】[{1}, {2, 3}]                    # ← 3日目（パターン2）では{1}, {2, 3}の2人を考えれば良い (=AとBの元に収集済)
【3】[{3, 4, 5}]                      # ← 3日目（パターン3）では{3, 4, 5}の1人を考えれば良い (=Dの元に収集済 =収集完了)
3 # 出力 (=3日目で収集完了)

RECOMMENDこちらの記事も人気です。