Binary indexed tree(BIT)をやった
これhttp://hos.ac/slides/20140319_bit.pdfを見ながら、これの基本問題をやった。
やり方はこれを見れば十分です。
問題設定はこちら。
N個の変数v_1, ..., v_n。
Q個のクエリ。
各クエリはv_a_jにw_jを加えるという操作。
answerは各クエリに対してv_1 + ... + v_aを求める。
クエリごとにどんどんv_1, ..., v_nは更新される。
入力は
N Q v_1 v_2 … v_N v_a_1 w_1 v_a_2 w_2 ... v_a_Q w_Q
という形で与えられるとする。
次のようなプログラムになる。
#x-1となっているのは、リストが0番目からになっているから。 #x&(-x)で2進数で表した場合の最も下位にある1の位置を取り出すことができる。 #例えば,10 = 1010なら10を返し、7 = 111なら1を返す。 N, Q = map( int, input().split()) V = list( map( int, input().split())) def add(A,a,w):#リストに値を追加する関数 x = a while x <= N: A[x-1] += w x += x&(-x) def sums(A,a):#k番目までの和 x = a S = 0 while x != 0: S += A[x-1] x -= x&(-x) return S A = [0]*N for i in range(1,N+1): add(A,i,V[i-1]) #for i in range(1,N+1): #確認用 # print(suma(A,i)) for _ in range(Q): v, w = map( int, input().split()) add(A,v,w) print(sums(A,v))
プログラムで気をつけることは、2進数で見たときの動きを意識すること。
2分探索
atcoderで2分探索に気づけないので、覚えるために、書き残しておく。
問題はABC063のD問題。
D - Widespread
解説はこれ。
https://atcoder.jp/img/arc075/editorial.pdf
大事なのは中のコメントのみ(##以下)。
ついでだけど、遅かったので、少し修正した。#以下は改善前。
N, A, B = map( int, input().split()) hmax = 0 H = [ int( input()) for _ in range(N)] hmax = max(H) L = 0 R = hmax//B + 1 add = A-B #以下よりも早い while R-L != 1:#L != R: now = (L+R)//2 need = 0 for i in range(N): r = H[i] - now*B if r > 0: need += (r-1)//add+1 if need <= now:##うまくいくとき R = now else:##うまくいかないとき L = now#+1 ##うまく行かないので+1している.これがないと無限ループが発生する。 print(R)
shellのfor文でファイルを作る
忘れるので。
下でやると00から入力される。
for i in `seq 10 20` do mkdir $i done
for i in {001..023} do mkdir $i done
動的計画法(1)
最近、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
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それぞれが入り、通りあります。
各場合に関する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になった。