tooh’s diary

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

2/22 ウニ(Sqlupp)/AtCoder(ナップサック問題、ゲームの必勝法(ニムなど、DFS、ビット演算子、XOR))

ウニ

 f:id:saguh:20190222165744p:plain

Sqluppを解禁  鳥取りました  わいわい

楽しいしガンガン腕を動かせてうおお俺今チュナイズムやってるな~~~~~~空間を切り裂いている新音ゲーやな~~~~~~~~となれる曲ですがなかなか難しいです

鳥取るのに15回くらいかかりました  以下攻略というと仰々しいですが、自分が気をつけたところを書いていきます

画像は全てCHUNITHM譜面保管所様よりお借りしました ありがとうございましたhttp://www.sdvx.in/chunithm/04/04069mst.htm

 

f:id:saguh:20190222170444p:plain

アヘ顔おじさん

 

 

 

f:id:saguh:20190222170520p:plain

7,8小節目、難所とも言い難い所なんですけど1/5くらいの確率で失敗しました  

画像より前の部分のホールド+タップを人差し指薬指で処理するイメージを持って、そのままの流れで拘束スライドを薬指、タップを人差し指で処理すると安定します

 

 

f:id:saguh:20190222170758p:plain

37~43小節目  ホールド+タップ+エアーの認識難地帯です  ここは気合いで行くしかありません  意識したことは両端のホールドとタップは薬指、真ん中のホールドとタップは人差し指で押さえました  これは人差し指じゃなくて親指でやった方が良い人もいると思うので個人差かも

 

 

f:id:saguh:20190222171106p:plain

45~56小節目  楽しいところ  ただ巻き込みアタックが出やすいです  叩くところをちゃんと意識するのと、気持ち指を浮かせると巻き込みにくくなります

 

 

f:id:saguh:20190222171236p:plain

48,49小節目のここ、終点の判定が厳しいです  特に最後はフリックを早めに擦り始めると普通にAttackが出るので要注意

 

 

f:id:saguh:20190222171536p:plain

61,62小節目  何故かアタが出やすいです  最後は右利きの人も左手から入った方が良さそう

 

 

ここまでは前半戦です  鳥狙う時はここまででアタ換算2~3くらいに抑えとくと後が楽

後半は大きな難所が二ヶ所来ます

 

 

f:id:saguh:20190222171746p:plain

67~69小節目  後半の難所の一つ目  トランペットの音に合わせて叩くのですがここめちゃムズいね  

構造は見ればわかる通り全部右始動の階段+トリルです

僕は餡蜜が全くできないので素直に目押しするしかなかったのですが、どうしようもないのでとりあえず右手の方をガン見してました  これだけでもアタが2,3くらいに抑えられます

 

 

f:id:saguh:20190222172353p:plain

77~79小節目  難所その二です 

まずは親の顔より見たWarcry地帯  ここは3鍵が4つ、4鍵1つ、3鍵が3つになっててパワーアップしてます  やめろ

ここも餡蜜できればいいんですけど、しょうがないから前半4つは目押し、後半4つにかけて餡蜜っぽく交互押しで無理やり通しました

 

そのあと78小節目からは交互なんですが、だんだん右にずれていくので巻き込みアタックが非常に出やすいです  注意したいところ

 

ここまでアタ9で来れたら後をAJ通過すれば勝ちです

 

 

......と言いたいところですが最後にラッシュがやってきます

 

 

f:id:saguh:20190222173153p:plain

この部分、単純な交互トリルですが切れ目(緑のところ)がいやらしいところについていて抜けが出やすいです  ここをちゃんと意識してシバくようにしましょう

 

あとは回数を積めばなんとかなります  金が全てを解決する

 

 

AtCoder

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

ABC:035B/036B/037B/038B/039B

AGC:015B

 

解けなかった問題

ABC:067D

DPまとめコン:D

 

ABC067D

 

木(どのマスも経路を介せば辿っていけるグラフ)をぬりぬりしていく問題

スタートのマスは決まっていて、二人が交互に色塗りしていく

相手が塗れなくなったらこっちの勝ちという趣旨のゲーム

 

最適な戦略は、相手をなるべく塗らせないようにすればよいのだから、相手のスタートのマスに向けてできるだけ遠くまで塗った方がよい(遠くまで塗っておけば、それより近くのマスは塗ることができるので)ということ これでどっちが勝つのかを判定する

 

先手はマス1から始め、隣り合うマスを黒く塗り、後手はマスNから始め、隣り合うマスを白く塗っていく

 

ゲーム自体は、「最適戦略をとったときに、お互いが塗ることが可能なマス目の数を比較して、多い方が勝ち」、「マス目の数が同数になる場合は、後手が塗って同数になり、マス目をすべて塗り終えたことになるので、先手が塗れない→後手の勝ち」とルールを変えても全く同じである

 

ここまでわかれば、あとはマス1とマスNからすべてのマス目の距離を比較して、近い方の色にぬればよいことが分かる

 

具体的には、マスiとマスjの距離をd(i,j)としたとき、マスiを黒に塗るときは

d(1,i) <= d(N,i) (1からの距離の方が近い、同じなら先手が塗る)

となる場合である

 

このようなマス目を計算するのは深さ優先探索を用いることでできる

 

以前書いたDFSの記事では「経路が一筆書きできるか(木かどうか)」を判定するものだったが、今回もそれに似たものが使えて、距離のデータを保持しておく必要はない

 

さて、DFSでは最初に、隣接する島のデータを格納するリストを作る必要がある 

以下にコードを書いていく(0インデックスで数字が一つ前にずれていることに注意)

 

G = [ for _ in range(N)]  #i番目の空のリストには島iに隣接する島の番号が入る

for i in range(N-1):

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

    G[a-1].append(b-1)

    G[b-1].append(a-1)         #隣接する島のデータを入れる

 

これで島の隣接についてはよい あとは、

visited = [0]*N

visited[0] = 1

visited[N-1] = 1

visited_all = [1]*N

として、「i番目の島が訪れられたかどうか」を格納するリストを作っておく(島0と島N-1はスタート地点なので、すでに訪れられたものとした)

 

そして、

nextA = G[0]

nextB = G[N-1]

とする これはA(先手)が次に訪れるのはG[0]、つまり0番目の島に隣接した島である、というような考え方で理解できる Bについても同様

 

さらに、

black = 1

white = 1

とし、ここで黒、白で塗れるマス目の数を保持しておく

 

ここから塗る作業に入っていく

while visited != visited_all:

    l = [ ]

    for a in nextA:                 #先手が次に塗る島を考える

     if visited[a] == 0:

            visited[a] = 1

            black += 1

            for x in G[a]:                #塗り終えた島について、その島と隣り合う島を見る

                l.append(G[a])        #lに今黒く塗った島と隣り合う島のデータを入れ、

            nextA = l                      #nextAの情報を更新  ここから下は後手の話になる

    l = [ ]

    for b in nextB:

        if visited[b] == 0:

            visited[b] = 1

            white += 1

            for y in G[b]:

                  l.append(G[b])

            nextB = l

 

これをvisited == visited_allとなるまで繰り返す

ここまでくれば、あとはblackとwhiteを比較したうえで、black > whiteならば先手の勝ち、それ以外ならば後手の勝ちとすればよい

 

 

ゲームの必勝法問題はほかにもいっぱいある(はず)

石取りゲーム(ニム)を例にとって挙げてみる(蟻本のp.277に載ってる)

 

[問題]

石の山がn個あり、i番目の山にはa_i個の石がある。AとBは交互に空でない山を一つ選んで、そこから一つ以上の石をとる。最後の石を取った方を勝ちとする。Aから始めた場合、両者が最善を尽くせばどちらが勝つか。

 

石の山全部の石の個数のXOR(二進法の各桁を比較して異なっていれば1、同じなら0)を考える XOR = 00....0も0と扱う

XORを計算する際、計算して各桁を1,0のみにするのは面倒なので、二進法で表したときにそれをそのまま累積していって、各桁の偶奇を見る方法を利用する

(例)

2 XOR 5 XOR 7

は2,5,7を二進法に直すと10,101,111でそのまま足すと222になり、これは各桁が偶数なのでXORを二進数で直した結果は0が並ぶ(000)

 

2 XOR 3 XOR 3

は2,3を二進法に直すと10,11でそのまま足すと32になり、XORは10

 

最終的に自分が石をとって終わりにしたいので、自分が勝つときの最後の局面でのXORは0(0+0+......+0 = 0なのでそれはそう)

ということは、ここから逆算して、自分の手番が終了したときに常にXORを0にできれば必ず勝てる(逆に、相手の手番が終了したときXOR != 0であればよい)

 

さて、これが通用する理由は二つあり、

①XOR != 0で回ってきたらXOR == 0にして返せる

②XOR == 0で回ってきたらどうやってもXOR != 0にしかできない

からである

 

②は、0が並んだ状態からはどこをとってもXORが0でなくなってしまう(0を0のままで返せるのは0の足し算のみ)のでわかる

 

①は、例えば2,4,5を考えたとき、2,4,5は二進法に直すと10,100,101でXORは011、これを000にする(XORを0にする)ためには、011のうち下二つの1を0にする(反転させる)必要がある

やり方は、

ア、XOR結果を二進数で見たときの一番上の1のビットが経っている山を選ぶ。つまり、今回の場合は011で、1のビットが経っているのは上から二番目。2,4,5(010,100,101)の中で上から二番目の1のビットが立っている山は2(010)なのでこれを選ぶ。

イ、選んだあと、011の下二つを反転させたいので、2(010)の下二つを反転させるように石を除く(つまり、1個除いて山を1(001)にする)。これでXORを0にして返せる

これにより、XOR != 0の状態からXOR == 0にして返せることが分かる

    

これによって、開始時のXOR結果が0であれば、Aは必ずXORを0でない形で返さねばならず、Bが最善策をとれば必ずXORを0にして返すので、Bが最後にXORを0にして勝ち。一方で、開始時のXOR結果が0でなければAの勝ちとなる

 

つまり石を動かしてアレコレやる必要もなく、最初の石の山の状態でどちらが勝つか決まっている これを考えてプログラムを書いてやればよいことになる

 

 python3で数字を二進法表記した結果を用いて演算してくれる演算子(ビット演算子)は、&、|、^がある

 

a&bはa,bを二進数に直してどちらも1なら1,異なっていれば0を返す

例えば11&14 == 10である

11,14は二進法に直すと1011,1110なので、両方1を持つ桁を1、そうでない桁は0とすると、1010となり、これを十進法に直せば10だからである

 

a|bは、二進法に直したとき少なくとも1つが1なら1を返してくれる

11|14 == 15 (1011と1110なので1110と返ってくる)

 

a^bが今回使うXORで、異なっていれば1、同じなら0を返す

11^14 == 5 (1011と1110なので0101が返ってくる)

 

紹介が終わったところで答えのコードを書く

 

n = int(input())
L = list(map(int,input().split()))
S = 0
for i in range(n):
    S ^= L[i]
if S != 0:
    print('A')
else:
    print('B')

 

これだけ 単純だね かんたん わいわい

 

 

DPまとめコンD

たぶん一番基本的な問題 いろいろ言う前にもう答えを覚えちゃった方がよさそう

重さについてのDPを使って解くのが素直

与えられた品物の個数をN、重さの制限をWとする (N+1)*(W+1)のリストdpを作ってあげる(品物の番号は0インデックスなので0~N-1)

dp =
for i in range(N+1):
    dp.append([0 for _ in range(W+1)])

縦の番号には0~Nが入り、横には0~Wが入る

それから、i番目以降の品物から重さの総和がj以下になるように選んだ時の価値の最大値をリストの中に順次入れていく

(重さと価値のデータはwvというリストに入れることにする)

リストの下の方から埋めていく

まず、リストの一番下は、N番目以降の品物を選ぶことになるので、品物がN-1番目までしかない以上は選べないので0で埋めていくしかない(すでに0で埋まっているので放置)

それから、(N-1)~0番目について、i番目以降の品物を選ぶ際のアルゴリズム

for i in range(N-1,-1,-1):         #N-1から0まで逆順に見ていく

    for j in range(0,W+1):

if j < wv[i][0]:                           #wv[i][0]が制限重量をオーバーしていたら

    dp[i][j] = dp[i+1][j]          #その品物は入らないのでdp[i+1][j]がそのまま入る

else:

    dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])      #w[i]を入れるかどうかを判定する

                                                                                         ために、それを入れた場合と入

                                                                                         れなかった場合とを比較する

print(dp[0][W])

 

これでいける 

いけませんでした 言語的な問題がありそう 計算量が10**7で、ここまでくるとpython3は厳しいのかもしれない numpyをお勉強する必要があるかもしれない