ニート歴10年からの数学日記

2008年〜2009年の高一の冬休みから無職。最長で4ヶ月ほどの中断アリ。

ジュニア算数オリンピック グラフの問題

【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックのグラフの問題について考察していく。今回は最初の問題で実際のpython3も使った。
 

 

06年度トライアル問題 問題1

『図の各数字は2つの○の間を移動するとっきの所要時間(単位:分)を示しています。AからBまで移動するときにかかる最も短い時間を求めなさい。

458B
6937
546
4655
496
5879
A478
 

#[隣接する節点の番号, 移動のコスト]
graph = [
    [[1, 4], [4, 6]],
    [[0, 4], [2, 5], [5, 9]],
    [[1, 5], [3, 8], [6, 3]],
    [[2, 8], [7, 7]],
    [[0, 6], [5, 5], [8, 4]],
    [[1, 9], [4, 5], [6, 4], [9, 6]],
    [[2, 3], [5, 4], [7, 6], [10, 5]],
    [[3, 7], [6, 6], [11, 5]],
    [[4, 4], [9, 4], [12, 5]],
    [[5, 6], [8, 4], [10, 9], [13, 8]],
    [[6, 5], [9, 9], [11, 6], [14, 7]],
    [[7, 5], [10, 6], [15, 9]],
    [[8, 5], [13, 4]],
    [[9, 8], [12, 4], [14, 7]],
    [[10, 7], [13, 7], [15, 8]],
    [[11, 9], [14, 8]]
]

#PQは本当はPriority Queue、つまり優先度キューだったが、今回は実装で怠けるためにリストにしたので、決して実際に使ってはいけない
def singleSourceShortest(graph, start, goal):
    vertex_amount = len(graph)
    dist = [float("inf")] * vertex_amount   #その節点に行くまでのコスト
    pred = [-1] * vertex_amount   #どこから来たか
    PQ = []   #優先度リスト 探索する際にその時のdist[v]を節点の優先度として使う

    dist[start] = 0
    for v_index in range(vertex_amount):
        PQ.append((v_index, dist[v_index]))
    PQ.sort(key=lambda x: x[1], reverse=True)   #こう書くらしい(公式ドキュメントの「ソート HOW TO」曰く)


    while(PQ != []):
        u_tuple = PQ.pop()
        u_index = u_tuple[0]
        u = graph[u_index]

        for v in u:
            v_index = v[0]
            w = v[1]
            newLen = dist[u_index] + w
            if newLen < dist[v_index]:
                dist[v_index] = newLen
                pred[v_index] = u_index
                PQ = [i for i in PQ if i[0] != v_index]
                PQ.append((v_index, dist[v_index]))
        PQ.sort(key=lambda x: x[1], reverse=True)

    now_v = goal
    print("goal")
    while(pred[now_v] != -1):
        print("↑")
        now_v = pred[now_v]
        print(now_v)


singleSourceShortest(graph, 12, 3)
$ python3 ダイクストラ.py
goal
↑
2
↑
6
↑
5
↑
4
↑
8
↑
12

 

12年度トライアル問題 問題8

『次の立体を頂点Aからスタートして返上を通ってAにもどってくるような方法は、全部で何通りありますか。ただし、同じ辺を2度通ってはいけません。

(図は省略 ABCDの三角錐)』
 

#pythonでは無い

graph := [
    "A" : ["B", "C", "D"],
    "B" : ["A", "C", "D"],
    "C" : ["A", "B", "D"],
    "D" : ["A", "B", "C"]
];   #辞書、()にするか[]にするか迷うな

def visit_v(graph, current_v, start) {
    or(next_v in graph[current_v]) {   #orにおいて、データを共有するかどうかという設定項目が必要か
        graph[current_v].remove(next_v);
        graph[next_v].remove(current_v);

        current_v := next_v;

        if(current_v != start) {   # || graph[current_v] != [] を入れるべきか
            current_v := visit_v(graph, current_v, start);
        }
    }

    return current_v;
}

start := "A";
current_v := "A";

current_v := visit_v(graph, current_v, start);

current_v == "A";

print(数);


こんな感じだろうか。
return文が必要だと気付いて付け足した。これで大丈夫かな。しかしやっぱりpythonは良かったなあ。