動的計画法(1)

atcoder プログラミング python

最近、AtCoder 版！蟻本 (初級編)をやってる。
めっちゃ多い。
多重な動的計画法の実装がうまくいったから、見せびらかそうと思って、記事を書いてる。
本当は解説しようと思ったけど、めんどくさくなった。
問題はABC015のD問題D - 高橋くんの苦悩です。
解説はAtCoder Beginner Contest 015 解説です。
pythonは通らなくて、pypyで通した。

W = int(input())
N, K = map( int, input().split())
dp = [[0 for _ in range(W+1)] for _ in range(K+1) ]
for k in range(N):
    a, b = map( int, input().split())
    for i in range(K,0,-1):
        for j in range(W,0,-1):
            if a <= j:
                dp[i][j] = max( dp[i][j], dp[i-1][j-a] + b)
print(dp[K][W])

dp[i][j]で枚数i枚以下で、幅j以下での重要度の最大値を表している。
for文を逆に回すのがポイント。

二次元累積和

プログラミング atcoder

ABC106のD問題の解説の二重累積和がよくわからなかったので、簡単に証明をつけた。
まず、{A = (a_{ij})}を二重配列と考えます。
{A}の各列の累積和を取ったものを{B = (b_{ij})}とします。
すると、
{b_{ij} = \sum_{k=1}^i a_{ij}}
となります。
次に、{B}の各行の累積和を取ったものを{C = (c_{ij})}とします。
すると、
{c_{ij} = \sum_{l=1}^j b_{il} = \sum_{l=1}^j \sum_{k=1}^i a_{kl}}
となります。
というわけで、{C}の各成分が{A}の{i\times j}の長方形に囲まれた部分の成分の和になります。
納得。

ABC104

atcoder python

ABC104のD問題

ABC104のD問題で'B'を固定する解法についての解説。
D: We Love ABC - AtCoder Beginner Contest 104 | AtCoder
問題は次のようなものです。
ABCからなる文字列Tに対し、i < j < k番目の文字がそれぞれA, B, Cになるような(i, j, k)の組み合わせの数をABC数と呼びます。
ABC?からなる文字列Sが与えられたときに、?はABCそれぞれが入り、 {3^Q}通りあります。
各場合に関するABC数の和を求め、それを {10^9+7}で割った余りを求める問題です。

解説

i番目のBを固定して、左にAがある場合の数とCがある場合の数を求めます。
Aの場合の数についてのみ解説します。
Aの数をn、?の数をmとします。
すでにあるAからAを選ぶ場合の数は、Aの数nと?に何を入れるかの {3^m}の積です。
次に?からAを選ぶ場合は、?のうちのk個がAである場合それぞれについて考えます。
?にAがk個入る場合の数は { _nC_k}通りあり、その中のどのAを選ぶかはk通りあります。
また、残りの {(n-k)}個の?にB,Cのいずれが入るかの {2^{n-k}}通りあります。
これらをまとめると
{n \times 3^m + \sum_{k=1}^n \ _nC_k \times k \times 2^{n-k}}
となります。
第2項のΣは、 {(2+x)^n}を微分することで簡単にできます。
というわけで、
{n\times 3^m + n \times 3^{n-1}}
がAの場合の数となります。
Aの場合の数とCの場合の数の積がi番目にBがあるときのABC数の合計になります。
プログラムは次のものになります。

S = input()
L = len(S)
Q = 10**9 + 7
anum = [ 0 for _ in range(L+1)] #i番目までのAの個数の合計
cnum = [ 0 for _ in range(L+1)] #i番目までのCの個数の合計
hnum = [ 0 for _ in range(L+1)] #i番目までの?の個数の合計
for i in range(1,L+1):
    if S[i-1] == 'A':
        anum[i] = anum[i-1] + 1
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'B':
        anum[i] = anum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1]
    elif S[i-1] == 'C':
        anum[i] = anum[i-1]
        cnum[i] = cnum[i-1] + 1
        hnum[i] = hnum[i-1]
    else:
        anum[i] = anum[i-1]
        cnum[i] = cnum[i-1]
        hnum[i] = hnum[i-1] + 1
ans = 0
czen = cnum[L] #全部のCの個数
hzen = hnum[L] #全部の?の個数
for i in range(1,L+1):
    if S[i-1] == 'B' or S[i-1] == '?':
        A = ((anum[i-1]*pow(3,hnum[i-1],Q))%Q + (hnum[i-1]*pow(3,max(0,hnum[i-1]-1),Q))%Q)%Q
        C = (((czen - cnum[i])*pow(3,hzen - hnum[i],Q))%Q + ((hzen - hnum[i])*pow(3,max(0,hzen - hnum[i]-1),Q))%Q)%Q
        K = (A*C)%Q
        ans = (ans + K)%Q
print(int(ans))
おまけ

powではなく**でやってたときは、TLEになった。

Let's noteでlinuxを使用する際に、音が出ない話

思い立って調べてみたら、こんな記事があった。
Let's NoteにLinuxをインストールしたがスピーカーから音が出ない問題【解決!!】
ここにもあるが、結論を言うと、次のコマンドで初期化を行う必要があるみたいです。

sudo alsactl init

メモリを増設した

PC関連

次の記事を見ながらやった。
Let's Note CF-SX2のメモリを増設して8GBにする | ノート100YEN.com
増設したのはこれ。
https://www.amazon.co.jp/gp/product/B00CQ35HBQ/ref=oh_aui_detailpage_o00_s00?ie=UTF8&psc=1
メモリを斜めに差し込むときには、結構力を入れてぐっと入れないといけない。
かなり怖い。

オセロをつくった

プログラミング python

pythonでオセロのプログラムを書いた。
functions_othello.pyに使う関数をまとめた。

from functions_othello import *
turn = 'black' #黒
B = board() #盤面生成
BP, able = check(B,turn)
show_double(B,BP,turn)
while able != 0:
    B, turn = place(B,BP,turn)
    BP, able = check(B,turn)
    show_double(B,BP,turn)        
    if able == 0:
        if turn == 'black':
            BP, able = check(B,'white')
            if able == 0:
                break
            else:
                turn = 'white'
                print('黒を置ける場所はありません')
                show_double(B,BP,turn)
        else:#white
            BP, able = check(B,'black')
            if able == 0:
                break
            else:
                turn = 'black'
                print('白を置ける場所はありません')
                show_double(B,BP,turn)
cnt_black_stone = 0
cnt_white_stone = 0
for i in range(8):
    for j in range(8):
        if B[i][j] == 'black':
            cnt_black_stone += 1
        elif B[i][j] == 'white':
            cnt_white_stone += 1
show(B)
if cnt_black_stone > cnt_white_stone:
    print('黒○ の勝ち')
elif cnt_black_stone < cnt_white_stone:
    print('白● の勝ち')
else:
    print('引き分け')

Bは現在の盤面を表し、'black'、'white'、'null'が入った8×8のリストです。
BPは石を置くことのできる位置を表し、'able'、'null'が入った8×8のリストです。
turnは黒と白のどちらの番であるかを表し、'black'または'white'です。

board()はオセロの初めの盤面を構成する関数です。

def board():
    B = [['null' for i in range(8) ] for i in range(8)]
    B[3][3] = 'white'
    B[3][4] = 'black'
    B[4][3] = 'black'
    B[4][4] = 'white'
    return B

show(B)は現在の盤面をオセロ風に表示する関数です。

def show(B):
    BQ = ['null']*10
    for i in range(1,9):
        s = chr(97 + i - 1) + '|'
        for j in range(8):
            if B[i-1][j] == 'white':
                s += '● '
            elif B[i-1][j] == 'black':
                s += '○ '
            else:
                s += '  '
            s += '|'
        s += chr(97 + i - 1)        
        BQ[i] = s
    K = ' |'
    for i in range(1,9):
        K += ' ' + str(i)
        K += '|'
    BQ[0] = K
    BQ[9] = K
    for i in range(10):
        print(BQ[i])

check(B,turn)は現在の盤面と番を入力することで、置ける位置と置ける枚数を返す関数です。

def check(B,turn):#BPとして置ける部分をマークしたものを出力したい
    #turn = 'black'の場合で解説を書く
    able = 0
    BP = [['null' for i in range(8) ] for i in range(8)]
    #縦横斜めで順番にcheckしていく
    for i in range(8):#横
        a = -1
        k = 0
        t = 2
        for j in range(8):
            stone = B[i][j]
            if stone == 'null':
                if t == 1:
                    if a >= 1:
                        BP[i][j] = 'able'
                        able += 1
                        k = j
                        a = 0
                        t = 0
                    else:
                        t = 0
                        k = j
                else:
                    a = 0
                    k = j
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[i][k] = 'able'
                    able += 1
                    k = j
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1

    for j in range(8):#縦
        a = -1
        k = 0
        t = 2
        for i in range(8):
            stone = B[i][j]
            if stone == 'null':
                if t == 1:
                    if a >= 1:
                        BP[i][j] = 'able'
                        able += 1
                        k = i
                        a = 0
                        t = 0
                    else:
                        t = 0
                        k = i
                else:
                    a = 0
                    k = i
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[k][j] = 'able'
                    able += 1
                    k = i
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1

    for i in range(8):#斜め右上
        a = -1
        k = 0
        t = 2
        for j in range(8-i):
            stone = B[i+j][j]
            if stone == 'null':
                if t == 1:
                    if a >= 1:
                        BP[i+j][j] = 'able'
                        able += 1
                        k = j
                        a = 0
                        t = 0
                    else:
                        t = 0
                        k = j
                else:
                    k = j
                    a = 0
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[i+k][k] = 'able'
                    able += 1
                    k = j
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1

    for j in range(1,8):#斜め左下
        a = -1
        k = 0
        t = 2
        for i in range(8-j):
            stone = B[i][i+j]
            if stone == 'null':
                if t == 1:
                    if a >= 1:
                        BP[i][i+j] = 'able'
                        able += 1
                        k = i
                        a = 0
                        t = 0
                    else:
                        t = 0
                        k = i
                else:
                    a = 0
                    k = i
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[k][k+j] = 'able'
                    able += 1
                    k = i
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1
                    
    for i in range(8):#斜め左上
        a = -1
        k = 0
        t = 2
        for j in range(8-i):
            stone = B[7-i-j][j]
            if stone == 'null':
                if t == 1:
                     if a >= 1:
                         BP[7-i-j][j] = 'able'
                         able += 1
                         k = j
                         a = 0
                         t = 0
                     else:
                         t = 0
                         k = j
                else:
                    k = j
                    a = 0
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[7-i-k][k] = 'able'
                    able += 1
                    k = j
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1

    for j in range(1,8):#斜め右下
        a = -1
        k = 0
        t = 2
        for i in range(8-j):
            stone = B[7-i][i+j]
            if stone == 'null':
                if t == 1:
                    if a >= 1:
                        BP[7-i][i+j] = 'able'
                        able += 1
                        k = i
                        a = 0
                        t = 0
                    else:
                        t = 0
                        k = i
                else:
                    a = 0
                    k = i
                    t = 0
            elif stone != turn:#white
                if t == 1 or t == -1:
                    a += 1
                elif t == 0:
                    a = 1
                    t = -1
            else:#black
                if t == -1 and a >= 1:
                    BP[7-k][k+j] = 'able'
                    able += 1
                    k = i
                    a = 0
                    t = 1
                else:
                    a = 0
                    t = 1

    return BP, able

show_able(BP)は置ける場所を三角で表示する関数です。必要はない。

def show_able(BP):
    BPQ = ['null']*10
    for i in range(1,9):
        s = chr(97 + i - 1) + '|'
        for j in range(8):
            if BP[i-1][j] == 'able':
                s += '△ '
            else:
                s += '  '
            s += '|'
        s += chr(97 + i - 1)        
        BPQ[i] = s
    K = ' |'
    for i in range(1,9):
        K += ' ' + str(i)
        K += '|'
    BPQ[0] = K
    BPQ[9] = K
    for i in range(10):
        print(BPQ[i])

place(B,BP,turn)は石をどこに置くかの入力を求めて、それが置けるかどうか判断して、実際に現状の盤面Bを更新する関数です。
更新はupdate(B,turn,x,y)に任せた。

def place(B,BP,turn):#turnの人が入力してそれを盤面に反映する
    while True:
        if turn == 'black':
            S = list(input('黒○ の番です。置きたい位置を入力してください。(例:5d)'))
        else:
            S = list(input('白● の番です。置きたい位置を入力してください。(例:5d)'))
        x, y = ord(S[1])-97, int(S[0]) -1
        if BP[x][y] == 'able':
            if turn == 'black':
                B = update(B,turn,x,y)
                turn = 'white'
            else:#white
                B = update(B,turn,x,y)
                turn = 'black'
            return B, turn
        else:
            print('そこは置けません')
            show_double(B,BP,turn)
            pass

update(B,turn,x,y)はx,y成分に石が置かれた場合の盤面の更新をする関数です。

def update(B,turn,x,y):
    S = []
    for i in range(x-1,-1,-1):#北
        if B[i][y] == 'null':
            break
        elif B[i][y] == turn:#black
            for j in S:
                B[j][y] = turn
            break
        else:#white
            S.append(i)

    S = []
    for i in range(x+1,8):#南
        if B[i][y] == 'null':
            break
        elif B[i][y] == turn:#black
            for l in S:
                B[l][y] = turn
            break
        else:#white
            S.append(i)

    S = []
    for j in range(y-1,-1,-1):#西
        if B[x][j] == 'null':
            break
        elif B[x][j] == turn:#black
            for l in S:
                B[x][l] = turn
            break
        else:#white
            S.append(j)
            
    S = []    
    for j in range(y+1,8):#東
        if B[x][j] == 'null':
            break
        elif B[x][j] == turn:#black
            for l in S:
                B[x][l] = turn
            break
        else:#white
            S.append(j)
        
    if x <= y:#右上
        S = []
        for i in range(x-1,-1,-1):
            if B[i][y-x+i] == 'null':
                break
            elif B[i][y-x+i] == turn:
                for l in S:
                    B[l][y-x+l] = turn
                break
            else:
                S.append(i)

        S = []
        for j in range(y+1,8):
            if B[x+j-y][j] == 'null':
                break
            elif B[x+j-y][j] == turn:
                for l in S:
                    B[x+l-y][l] = turn
                break
            else:
                S.append(j)

    else:#左下
        S = []
        for j in range(y-1,-1,-1):
            if B[x-y+j][j] == 'null':
                break
            elif B[x-y+j][j] == turn:
                for l in S:
                    B[x-y+l][l] = turn
                break
            else:
                S.append(j)

        S = []
        for i in range(x+1,8):
            if B[i][y+i-x] == 'null':
                break
            elif B[i][y+i-x] == turn:
                for l in S:
                    B[l][y+l-x] = turn
                break
            else:
                S.append(i)

    if x + y <= 7:#左上
        S = []
        for i in range(x-1,-1,-1):
            if B[i][y+x-i] == 'null':
                break
            elif B[i][y+x-i] == turn:
                for l in S:
                    B[l][y+x-l] = turn
                break
            else:
                S.append(i)

        S = []
        for j in range(y-1,-1,-1):
            if B[x+y-j][j] == 'null':
                break
            elif B[x+y-j][j] == turn:
                for l in S:
                    B[x+y-l][l] = turn
                break
            else:
                S.append(j)
    else:#右下
        S = []
        for i in range(x+1,8):
            if B[i][y+x-i] == 'null':
                break
            elif B[i][y+x-i] == turn:
                for l in S:
                    B[l][y+x-l] = turn
                break
            else:
                S.append(i)

        S = []
        for j in range(y+1,8):
            if B[x+y-j][j] == 'null':
                break
            elif B[x+y-j][j] == turn:
                for l in S:
                    B[x+y-l][l] = turn
                break
            else:
                S.append(j)
    B[x][y] = turn
    return B

show_double(B,BP,turn)は前述のshow(B)とshow_able(B,BP)を合わせたものです。

def show_double(B,BP,turn):
    if turn == 'black':
        T = '△ '
    else:
        T = '▲ '
    BandBP= ['null']*10
    for i in range(1,9):
        s = chr(97 + i - 1) + '|'
        for j in range(8):
            if B[i-1][j] == 'white':
                s += '● '
            elif B[i-1][j] == 'black':
                s += '○ '
            elif BP[i-1][j] == 'able':
                s += T
            else:
                s += '  '
            s += '|'
        s += chr(97 + i - 1)        
        BandBP[i] = s
    K = ' |'
    for i in range(1,9):
        K += ' ' + str(i)
        K += '|'
    BandBP[0] = K
    BandBP[9] = K
    for i in range(10):
        print(BandBP[i])