忘れるので。
def gcd(a, b): while b != 0: a, b = b, a % b return(a)
忘れるので。
下でやると00から入力される。
for i in `seq 10 20` do mkdir $i done
for i in {001..023} do mkdir $i done
最近、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文を逆に回すのがポイント。
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それぞれが入り、通りあります。
各場合に関するABC数の和を求め、それをで割った余りを求める問題です。
i番目のBを固定して、左にAがある場合の数とCがある場合の数を求めます。
Aの場合の数についてのみ解説します。
Aの数をn、?の数をmとします。
すでにあるAからAを選ぶ場合の数は、Aの数nと?に何を入れるかのの積です。
次に?からAを選ぶ場合は、?のうちのk個がAである場合それぞれについて考えます。
?にAがk個入る場合の数は通りあり、その中のどのAを選ぶかはk通りあります。
また、残りの個の?にB,Cのいずれが入るかの通りあります。
これらをまとめると
となります。
第2項のΣは、を微分することで簡単にできます。
というわけで、
が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をインストールしたがスピーカーから音が出ない問題【解決!!】
ここにもあるが、結論を言うと、次のコマンドで初期化を行う必要があるみたいです。
sudo alsactl init
次の記事を見ながらやった。
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
メモリを斜めに差し込むときには、結構力を入れてぐっと入れないといけない。
かなり怖い。