[Python] ABC015 D DP 100点
問題 D – 高橋くんの苦悩 回答 動的計画法を使います。 Python では TLE ですが、PyPy では間に合いました。 W = int(input()) N, K = map(int, input().split()) AB =...
「アルゴリズム」一覧
[Python] ABC015 D メモ化再帰 100点
問題 D – 高橋くんの苦悩 回答 defaultdict defaultdict を使ってみましたが、残念ながらＴＬＥでした。 import collections W = int(input()) N, K = map(int, ...
[Python] ABC015 D 全探索 0点
問題 D - 高橋くんの苦悩 回答 TLE で 0点ですが、まずは再帰的に行う全探索を考えます。 p32 です。 W = int(input()) N, K = map(int, input().split()) AB = de...
[Python] ABC015 C 幅優先探索
幅優先探索で実装します。 問題 C - 高橋くんのバグ探し 回答 N, K = map(int, input().split()) T = cur_vals = for n in range(N): new_vals = [...
[Python] ABC015 C メモ化再帰
この問題ではメモ化再帰を使う必要はないのですが、前述の問題を、練習のためメモ化再帰を使って解きなおします。 問題 C - 高橋くんのバグ探し 回答 defaultdict defaultdict をメモに使ってみます。 .fo...
[Python] ABC014 C いもす法
問題 C - AtColor 回答 いもす法を使います。 いもす法 改札にチケットを何枚入れれば良いのかを、いもす法で解いてみた 累積和は itertools の accumulate を使います。 itertools.accum...
[Python] ABC013 D 100点
問題 D – 阿弥陀 回答 ダブリング ダブリングとは、 2倍することをlogN 回繰り返すことで Nに到達できることを利用する手法です。 繰り返し 2 乗法 ( バイナリ法 ) あみだくじにはダブリングの手法が適用できま...
[Python] ABC012 D ワーシャルフロイド
問題 D - バスと避けられない運命 ワーシャルフロイド ワーシャル–フロイド法（英: Warshall–Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。 出典: フリー百科事典『ウィキペデ...
[Python] ABC012 D ダイクストラ法
問題 D - バスと避けられない運命 回答 ダイクストラ法を使います。 Python では TLE でしたが、PyPy では AC でした。 import collections import sys import heapq N, ...
[Python] defaultdict を使った隣接リスト
隣接リスト グラフを表現する方法に隣接リストがあります。 ここでは、defaultdict オブジェクトを使うことで、より簡単に隣接リストを表現することを考えます。 defaultdict オブジェクト ほとんと辞書と同じですが、 存在しない...