AtCoder Beginner Contest 054 C One stroke pass

問題

https://beta.atcoder.jp/contests/abc054/tasks/abc054_c

無向グラフについて、一筆書きの経路が有るかを判定する。

やった方法

節点の数が少ないので、今回は深さ優先探索を行った。

コード

簡単な部分について、内包表記を少しずつ取り入れるようにしています。

n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

for _ in range(m):
    a, b = map(int,input().split())
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)

                visited[node_] = 0
dfs(0,l)
print(ans)

AtCoder Beginner Contest 030 C-飛行機乗り

問題

https://beta.atcoder.jp/contests/abc030/tasks/abc030_c

　条件を満たしつつ飛行機をうまく乗り継いで、最善で往復した場合にどれだけ往復できるかを試す。

　試していないが、毎回、今いる空港の次にいる空港で、条件を満たすもので最小の便を探した場合、TLEすると考えられる。

　今回は、簡単な工夫ではあるものの、delを用いて探索要素を減らすことで解決しようとした。

　最善をつくすと言う意味で貪欲法？になるのだろうか。 

コード

　Pythonを用いた。

　次の空港に乗り継ぐ表現として、今回は二次元配列の2番目に0,1を用いた。

　改善できる部分は多そう。。。

a,b = map(int,input().split())
x,y = map(int,input().split())

a_port = list(map(int,input().split()))
b_port = list(map(int,input().split()))

all_d = []

for i in range(len(a_port)):
    all_d.append([a_port[i], 1])

for j in range(len(b_port)):
    all_d.append([b_port[j] , 0])
    
all_d_s = list(sorted(all_d, key=lambda x: x[0]))

counts = 0
times = a_port[0]
here = 1

while times <= max(b_port):
    jj = 0
    countsbefore = counts
    for j in range(len(all_d_s)):
        if times < all_d_s[j][0]:
            if all_d_s[j][1] == (here + 1) % 2 and all_d_s[j][1] == 0 and all_d_s[j][0] - times >= x :
                here = (here + 1) % 2
                times = all_d_s[j][0] 
                counts += 1
                jj = j
            elif all_d_s[j][1] == (here + 1) % 2 and all_d_s[j][1] == 1 and all_d_s[j][0] - times >= y :
                here = (here + 1) % 2
                times = all_d_s[j][0] 
                counts += 1
                jj = j
            else:
                pass
        else:
            continue
    if here <= jj:
        del all_d_s[here:jj]
    if counts == countsbefore:
        break
    
print((counts +1 ) // 2)                
    

改善点あればコメント頂けると大変嬉しいです。。。

AtCoder Beginner Contest 019 C

問題

https://beta.atcoder.jp/contests/abc019/tasks/abc019_3

2の倍数の種類を数え上げる。

単純に行う、つまり例えば、リストをソートして小さいものから順に二倍して探索するなどした場合、TLEしてしまう。

やった方法

2で割り続けて発生する、異なる奇数を全て数え上げれば良い。おおよそlog(max(a))で終わる見込みが持てる。

コード

Pythonです。C++は修行中

n = int(input())
a = list(set(map(int,input().split())))
al = []
while True > 0:
    for i in range(len(a)):
        if a[i] % 2 == 1:
            al.append(a[i])
            a[i] = 0
        elif a[i] != 0 :
            a[i] = a[i] // 2
        else:
            None
    b = list(set(a))
    if 0 in b:
        b.remove(0)
    if b == []:
        break
    else:
        a = b

print(len(list(set(al))))

改善点があれば教えて頂けると幸いです。