tooh’s diary

半角全角、常体敬体が入り乱れるカオス

2/21 AtCoder(アルファベットのリスト、二進法表記、深さ優先探索)/ウニ

 AtCoder

解くに至った問題(4問)

ABC:014B/058C/064C/070C

 

 

ABC014B

与えられた数Xの二進法表記を求めるプログラム

X = int(input())

bi = ''

p = X
for i in range(1,n+1):                 #2**n > Xとなるようにnを選ぶ
    if 2**(i-1) <= X < 2**i:
        k = i
        break
for j in range(k):
    if p >= 2**(k-j-1):
        p -= 2**(k-j-1)
        bi += '1'
    else:
    bi += '0'

 

ABC058C

aからzまでの26文字のアルファベットが入ったリストが欲しいなら、

alp = [chr(ord('a') + i) for i in range(26)]

とすればよい

 

 解けなかった問題

ABC054C

昨日のUF木を使って解く問題かな~とか安直に考えてたら、今回は除く辺のパターンが2**(N**2)くらいあるのでループで書くのがめちゃんこ難しい

ここでは深さ優先探索(DFSというらしい)を利用して解くのがよいとのこと

島N個、島と島を結ぶ橋をM本とする

(問題では島は1,2,3......と番号が振られていたが、ここでは0,1,2......と扱う)

 

N, M = map(int, input().split())
G = [[] for i in range(N)]    #G[i]は、i番目の島と結ばれている島の番号を格納する
for i in range(M):
    a, b = map(int, input().split())  #↑のやり方で、橋で結ばれた島をリストに入れていく
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
cnt = [0]            #cntは、一筆書きできる場合の数を表す
def dfs(V, s):                              #リストVに着目、sは一筆書きをスタートする島である
    V[s] = 1                                  #sの島を訪れたことを示すため、まずV[s]を1にする
    if sum(V) == N:       #全ての島を訪れ終わると、リストVの要素は1で尽くさ          

                れているハズ
        cnt[0] += 1                         #そのような場合は今回の題意に適するので、cntを+1
    else:            #リストVが1で尽くされていない場合は、
        for adj in G[s]:      #今はs番目の島を見ているため、s番目の島と結ばれた島

                  を次に考える(訪れる)
            if V[adj] == 0:                #s番目の島と結ばれた島がVのリストで0になっていたら
                dfs(V[:adj] + [1] + V[adj + 1:], adj) #その島を1(訪れたことを表す)にする

                   さらにsをadj(次に訪れた島の番号)に変更
dfs([0] * N, 0)          #今回は、これを0番目の島からスタートさせる 
print(cnt[0])

 

例えば

3 3

1 2

1 3

2 3

という入力であれば、島1,2,3が三角形のようにつながっていることになるが、

これを上のプログラムに当てはめると、

 

島0(1)から一筆書きをスタート→

V = [1,0,0]に→隣接している島は島1(2)と島2(3)なので、こいつらを次に見て、V = [1,1,0] とV = [1,0,1]と新たに二つのリストを作る→

それをもとに、V = [1,1,0]についてdfs(V,1)とV = [1,0,1]についてdfs(V,2)を行う→

dfs(V,1)については、島1(2)と隣接する島が島0(1)と島2(3)であるが、V[0] == 1だからこれはもう見ないで、V[2] == 0についてのみ考える→

結局新たにV = [1,1,1]というリストができる これはsum(V) == 3を満たしているため、島0からスタートしてすべての島を訪れたことになっている→

これは題意に適するため、カウンターを1増やす→

dfs(V,2)についても同様の事から、カウンターの値が1増える 最終的に2パターンの経路で一筆書きができることがわかる

 

また一人で作りなおしてみます

atcoder.jp

今回もまたじゅっぴーさんにお世話になりました ありがとうございました

 

 

 

 ウニ

f:id:saguh:20190222025554j:plainf:id:saguh:20190222025609j:plain

昨日二週間ぶりくらいにやって今日アプデがあったのでやってきました

マップの新曲は二つしか解禁できてないですがどっちも曲も良くて楽しかったしキャラも可愛いしで文句ありません  Techno Kitchen脳トレやめろ

 

CITRUS MONSTERが問題で、多分10回くらいやったんですけど6954で止まってしまい鳥は乗りませんでした  早いトリルとかどうやって力入れて叩けばいいっちゅうねん  気合いで乗り切るしか無いですね