[WEEK04] DAY26 & TMI

1939 じゅうりょうせいげん

コード#コード#

import sys
from collections import deque

# 최대 중량 찾기
# 최소, 최대에서 가능한 이분탐색
# bfs에서 중간값을 기준으로 
    

n,m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    start, end, weight = map(int, sys.stdin.readline().split())
    graph[start].append([end, weight])
    graph[end].append([start, weight])

start_island, end_island = map(int, sys.stdin.readline().split())

min_weight , max_weight = 1, 10000000000

def bfs(mid_weight): 
    queue = deque()
    queue.append(start_island)
    visited = set()
    visited.add(start_island)

    while queue:
        start = queue.popleft()
        for end, weight in graph[start]:
            if end not in visited and weight >= mid_weight:
                visited.add(end)
                queue.append(end)

    if end_island in visited:
        return True
    else:
        return False

result = min_weight

while min_weight <= max_weight:
    mid_weight = (min_weight + max_weight)//2
    if bfs(mid_weight): 
        result = mid_weight
        min_weight = mid_weight+1
    else:
        max_weight = mid_weight-1

print(result)

DP

.

2746菲博纳奇数2(DP)

コード#コード#

import sys
n = int(sys.stdin.readline())

dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n])

.

1904 タイル (DP)

コード#コード#

import sys
n = int(sys.stdin.readline())
if n == 1:
    print(1)
elif n == 2:
    print(2)

else:
    dp = [0] * 1000001

    dp[0] = 1
    dp[1] = 2
    for i in range(2, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746

    # result = dp[n-1] % 15746
    print(dp[n-1]%15746)

フィボナッチ数列点火式を利用して、
最初は速度が遅すぎてifn=1とn=2を加えると中断します
.

4週目から

2021.11.26 FRI
今回のDP問題は前回の11053成長最長の部分数列問題を応用して解くことができる問題が多いようです.
どのように応用すればいいか、インフラを見てみるべきだと思います.
以前にアップロードされた11053問のDPプールのバージョンに関する問題はすべて簡単です.
ここにはフィボナッチ数列の物語が書かれていて、11053題自体ももう一度見ることができます.

今日の物語

第1、第2週目には、他の理科生との理系思考の流れの速度の違いを見た.
私はコード、コンピュータエンジニアリング、つまりこの分野を開発するのが簡単すぎるのではないかと心配しています.
私も一定の論理的思考を持っていて、4年間理工科を勉強した人の考えとは大きく違います.
与えられたアルゴリズム問題でよく遭遇する数学分野の障害は大きく,よく知られていないが.
それでも不安を感じる必要はないと思い、ずっと愚かに信じていた.
生まれてからのささやかな成果があって、今回も私を信じてくれました.
結論はやってこそ進歩がある
構造を見て、問題が要求する考え方を認識し始めた.
そして他人の新しい思考の流れを認識し、それを私のものにします.
このままでは、以前の心配は今でも少しは省けると思います.
ほほほ
がんばってください.