2020-05-13

ABC130 D - Enough Array　緑コーダーですが何か？その4

緑のしいだよ。ちきゅうにやさしいよ。

緑コーダーですが何か？第4回目だよ。素数の平方回目とはこりゃまた記念回だね気合い入れていこ

今回の問題はこれ！ ABC130 D - Enough Array

https://atcoder.jp/contests/abc130

連続する整数の総和がある数を超える組み合わせはいくつあるかという問題。

連続する和といったら累積和が定番だけど今回は制約大きいので無理

緑コーダーのわたしならもちろん楽勝だよね（？）

解法

そこで便利なのが尺取り法

ある数を超えるまでキューに追加していき、超えたら先頭から出していくという構造。めっちゃわかりやすいけど、バグが出やすいので注意

dequeだと理解しやすいけど使わなくてもできる。

すごくためになる尺取り法サイト（けんちょんさん）はこっち

https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

速度は落ちるけど二分探索でもできる。

今回は

collections の dequeを使う
dequeを使わず普通のリストだけでやってみる。
二分探索

ちなみにdequeの先頭の要素取り出す操作はO(1) だから速度は一緒だよ

すごくためになるサイトはこっち

https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

実装1

    from collections import deque
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    
    q = deque()
    s = 0
    ans = 0
    for e,i in enumerate(A):
        q.append(i)
        s+=i
        while s>=K:
            t = q.popleft()
            s-=t
            ans+=N-e
    print(ans)

実装2

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    q = []
    s = 0
    ans = 0
    c = 0
    for e,i in enumerate(A):
        q.append(i)
        s+=i
        while s>=K:
            s-=q[c]
            ans+=N-e
            c+=1
    print(ans)

解放（二分探索）

二分探索を使った方法ではまず累積和をもとめる。そのあと累積和の(それぞれの要素-K)をした上で二分探索し境界線を探す

実装3(right)

    import bisect
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]
    for i in A:
        S.append(S[-1]+i)
    ans = 0
    for i in S:
        ans += bisect.bisect_right(S,i-K)
    print(ans)

実装3(left)

    import bisect
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]
    for i in A:
        S.append(S[-1]+i)
    ans = 0
    for i in S:
        ans += N-bisect.bisect_left(S,i+K)+1
    print(ans)

あとがき

これも昔の汚い提出出てきた。。このとき初めて尺取り法を知ってかんどうしたんだっけ

https://atcoder.jp/contests/abc130/submissions/6840176

2020-05-12

ABC 128 C - Switches 緑コーダーですが何か？その３

緑のしいだよ、緑コーダーですが何か？第3回目だよ。３の倍数唯一の素数！いやーめでたい

今回の問題はこちら

ABC 128 C - Switches

https://atcoder.jp/contests/abc128/tasks/abc128_c

きたよ全探索。。。昨日のコンテストでもでて慣れてないとめっちゃじかんかかるよねこれとりまやっていきましょ

解法

制約がめっちゃ小さいので全探査して数える。 Mの値が固定ならその分for書いてもいいんだけどミスりやすいし可変にも対応できる方法は持っておいたほうがいいかな。

全探索の方法

やりかたは色々あるけど主流の２つ（わたしが２つしか知らんだけ）を

bit全探査
itertool

bitはまたまとめると思う。たくさんの人がまとめてるからそっちを見てね。 itertoolも簡潔でわかりやすいからおすすめ

実装１

方針

一度すべて受け取りスイッチに繋がってるか否かで[0 1] のリストを作る
１で作ったリストを使って内積を取り偶奇を判断する。

   N,M = map(int,input().split())
   s = []
   for i in range(M):
       dp = [0]*(N)
       k,*tmp = list(map(int,input().split()))
       for j in tmp:dp[j-1]=1
       s.append(dp)
   p = list(map(int,input().split()))
   ans = 0
   for i in range(1<<N):
       tmp = 0
       dp = [0]*M
       for I in range(M):
           for j in range(N):
               t = i>>j&1
               dp\[I] += s[I\][j] * t
       for e,i in enumerate(dp):
           dp[e] = i%2
       if dp == p:
           ans+=1
   print(ans)

実装２

方針

リストではなく数値で管理する。
内積ではなくビットの論理和を取り１の数の偶奇を判断する。

   N,M = list(map(int, input().split()))
   S = []
   for i in range(M):
       tmp = list(map(int, input().split()))
       t = 0
       for j in tmp[1:]:
           t += 1 << (j - 1)
       S.append(t)
   P = list(map(int, input().split()))
   ans = 0
   for i in range(1 << N):
       f = 0
       for s, p in zip(S, P):
           t = i & s
           c = bin(t).count('1') % 2
           if c == p:f+=1
       if f == M:
           ans += 1
   print(ans)

おまけ(itertool)

    import itertools
    N,M = map(int,input().split())
    s = []
    for i in range(M):
        dp = [0]*(N)
        tmp = list(map(int,input().split()))
        for j in tmp[1:]:dp[j-1]=1
        s.append(dp)
    p = list(map(int,input().split()))
    ans = 0
    for i in itertools.product([0, 1], repeat=N):
        tmp = 0
        dp = [0]*M
        for I in range(M):
            for j in range(N):
                dp\[I] += s[I\][j] * i[j]
        for e,j in enumerate(dp):
            dp[e] = j%2
        if dp == p:
            ans+=1
    print(ans)

あとがき

Bitの内容はやくまとめないと特に縦と横のやつ

2020-05-11

ABC 128 D - equeue 緑コーダーですが何か？その２

しいだよ緑だよ、緑コーダーですが何か？第2回目だよ。すごい！素数回まで続けれるとはおもってなかったから感動だよ。。。しかも素数唯一の偶数の素数。これは記念回だ。。。（）

問題

ABC 128 D - equeue

https://atcoder.jp/contests/abc128/tasks/abc128_d

問題分からしてあれだね。これ何回も解いてるけどいつも実装汚くなる。特に後ろからリスト取るのとかほんとに添字管理が複雑になっちゃうのがネック。一度まとめないと。。！

解法

今回の問題で大事なことは１つ

”入れ直す作業は最後にまとめてやってもええやんか”

そうです、これです。途中にやっても最後にやっても同じならまとめてやっちゃいましょう。

基本的な方針は

T個取り出す。（TはK以下の変数）
K-Tしてみてまだ操作が残っていたらできるだけ負の値の宝石を返す。

負の宝石はあるだけ邪魔なのでできるだけ戻したいっすね。逆に正の宝石は個数制限がないのであればあるほどありがたい。

2.のやり方は色々あって、

ソートして残り操作回数分pop()する
heapqに入れてheappoq
にぶたんぷにぷに

1.が一番簡単かな、わたしは最初２思いついたけど１のほうが記述量少ないし両方書いとくね

実装１

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    m = min(N,K) #KがNより大きい場合を防ぐ
    M = 0 
    for i in range(m+1):
        for j in range(m-i+1):
            A1 = A[:i] #前から取る
            A3 = A[N-j:] #後ろから取る
            new_A = A1+A3
            new_A.sort(reverse=True)
            h = K - len(new_A)
            while h >0 and new_A:
                if new_A[-1] > 0:
                    break
                else:
                    new_A.pop()
                    h-=1
            M = max(M,sum(new_A))
    print(M)

実装２(heapqを使ったもの)

    import heapq 
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    m = min(N,K) #KがNより大きい場合を防ぐ
    M = 0 
    for i in range(m+1):
        for j in range(m-i+1):
            A1 = A[:i] #前から取る
            A3 = A[N-j:] #後ろから取る
            new_A = A1+A3
            heapq.heapify(new_A)
            h = K - len(new_A)
            while new_A  and h >0:
                q = heapq.heappop(new_A)
                h-=1
                if q > 0:
                    heapq.heappush(new_A,q)
                    break
            M = max(M,sum(new_A))
    print(M)

あとがき

途中で性の宝石とかいうパワーワード誤変換で出てきてた、新しい正確のほめことばかな？（ぴゅあ）

2020-05-10

ABC 127 D-Integer Card　緑コーダーですが何か？その１

緑のしいだよ。

緑コーダーですが何か？第一回目だよ。

ここでは緑コーダーならとけるはずの問題を自責も兼ねて定期的にといていくよ。

記念すべき１回目はこれ！

ABC 127 D-Integer Card

https://atcoder.jp/contests/abc127/tasks/abc127_d

ぱっとみ、M回操作して最大値を求めればいいんだね。

選ぶ枚数は０枚でもいいってなんか変な感じするけど、操作しなくていいということか

解法1

リストに2*Nのサイズになるまで（B,C）を入れてあげる。そしてリスト[:N]でソートする。

C = 10**9と書いてあるが、最終的にNの数は決まっておりCの数全部使う必要もないからである。たとえばBがAの最大値より大きく場合でもN個いれてやったらAの元の要素がすべて吐き出されるので安心である。

実装

    N,M=map(int,input().split())
    A = list(map(int,input().split()))
    l = [] 
    for i in range(M):
      tmp = list(map(int,input().split()))
      l.append([tmp[1],tmp[0]])
    l.sort(reverse=True)
    for i,j in l:
        A.extend([i]*j)
        if len(A)>2*N:break
    A.sort(reverse=True)
    print(sum(A[:N]))

解法2

リストの中で最小値のものとBの値を比較してBのほうが大きかったら最小値と入れ替える。

実装におけるポイントは

リストの中の最小値を取り出す方法
Cが１以上の対処
はheapqを使えばなんとかなりそう
はwhile でCをすべて使い切るか、リストの中の最小値のほうが大きくなったときにwhileからぬけたらいいね

ここでwhileとかでると思考一瞬止まるからつらい。。。。

実装

    import heapq
    N,M=map(int,input().split())
    A = list(map(int,input().split()))
    heapq.heapify(A)
    l = [] 
    for i in range(M):
      tmp = list(map(int,input().split()))
      l.append([tmp[1],tmp[0]])
    l.sort(reverse=True)
    
    for i,j in l:
      for I in range(j):
        Q = heapq.heappop(A)
        if Q<i :
          heapq.heappush(A,i)
        else:
          heapq.heappush(A,Q)
          break
    print(sum(A))

あとがき

実装１の考え方はかなり大事だから意識しとくべき実装も簡単だし実装２も重そうに見えるけどN回出し入れするだけなので速度は大丈夫heapqの使い方も見直さないとね

ちなみにこのコンテスト参加してたんだけどすごい実装汚いの成長見てくれるって人は見てね（笑）↓

https://atcoder.jp/contests/abc127/submissions/5608902