今日の精進(20200109)

やる気を出さねば…

入れ替え

思ったよりも大変だった。
5回毎に一番左の数字が一番右に、30回ごとにもとの形に戻るので、30で割った回数だけもとの数字をずらす。そのあと30で割ったあまりで問題文通りの操作を行う。

# coding: utf-8  
N = int(input())  
S = list(map(str, range(1,7,1)))  
t1 = N // 30  
t2 = N % 30  
t1 //= 6  
S = S[t1:] + S[:t1]  
idx = 0  
while t2 > 0:  
    t2 -= 1  
    S[idx], S[idx+1] = S[idx+1], S[idx]  
    if idx < 4:  
        idx += 1  
    else:  
        idx = 0  
print("".join(S))  

755

全探索をやっても間に合わないので計算量を削減する必要がある。使える数字は3,5,7なので、それを足した値を深さ優先探索で求めていく。DFSがintの変数を持っていけないことに注意。

# coding: utf-8  
N = int(input())  
l = [0]  
def dfs(v, N):  
    if int(v)<= N:  
        flag = True  
        if v.count("3") <= 0:  
            flag = False  
        if v.count("5") <= 0:  
            flag = False  
        if v.count("7") <= 0:  
            flag = False  
        if flag:  
            l[0] += 1  
    else:  
        return  
    dfs(v + "7", N)  
    dfs(v + "5", N)  
    dfs(v + "3", N)  
dfs("0", N)  
print(l[0])  

bridge

解説AC。こういうのできるようになりたい…
すべての辺を格納したあと、ある辺を取り除いた時にすべての頂点を回れるかをDFSで探索する。探索できていない頂点がある場合問題で定義される「橋」になるので、カウントする。

# coding: utf-8  
N, M = map(int, input().split())  
graph = [[False for i in range(N)] for j in range(N)]  
visited = [False for i in range(N)]  
def dfs(v):  
    visited[v] = True  
    for k in range(N):  
        # 橋がなければわたらない  
        if not graph[v][k]:  
            continue  
        # すでに訪れていたら渡らない  
        if visited[k]:  
            continue  
        dfs(k)  
A, B = [], []  
for i in range(M):  
    a, b = map(int, input().split())  
    a -= 1  
    b -= 1  
    A.append(a)  
    B.append(b)  
    # 橋をTrueとして表す  
    graph[a][b] = True  
    graph[b][a] = True   

ans = 0  
# a, bの橋が通れないとして都度DFSを実行  
for a, b in zip(A, B):  
    graph[a][b] = False  
    graph[b][a] = False  
    visited = [False for i in range(N)]  
    dfs(0)  
    bridge = False  
    for j in range(N):  
        if not visited[j]:  
            bridge = True  
    # 渡れない島があったら+1  
    if bridge:  
        ans += 1  
    graph[a][b] = True  
    graph[b][a] = True  
print(ans)