Ccmmutty logo
Commutty IT
7 min read

AtCoder Beginner Contest 261 まとめ(A~E)

https://picsum.photos/seed/0445546044b34a0cb3c0171a981673b1/600/800

AtCoder Beginner Contest 261

ABC261の個人的に実装できた解法まとめです。
特筆がなければ言語はPyPy3です。
*がついてるものは時間内にACできた問題になります。

A - Intersection*

小さい方のRから大きい方のLを引いた値が重なった部分の長さになります。
重なってないと負になるので0とmaxをとることで0未満にならないようにします。
import sys
sys.setrecursionlimit(2**31-1)

def i2s(): return sys.stdin.readline().rstrip()
def i2ss(): return s2ss(i2s())
def i2n(): return int(i2s())
def i2nn(): return s2nn(i2s())

L1,R1,L2,R2 = i2nn()
print(max(min(R1,R2) - max(L1,L2),0))

B - Tournament Result*

[0...N1][0...N-1]の二数の組み合わせi,ji,jについて、Ai,jA_{i,j}Aj,iA_{j,i}の組み合わせがWL or LW or DDであるかを確かめます。
組み合わせにはitertools.combinationsを利用しています。
import sys
from itertools import *

def i2s(): return sys.stdin.readline().rstrip()
def i2n(): return int(i2s())

N=i2n()
A=[i2s() for _ in range(N)]

def main():
    for i,j in combinations(range(N),2):
        ab = A[i][j]+A[j][i]
        if ab not in ['WL', 'LW', 'DD']:
            return print('incorrect')
    return print('correct')

main()

C - NewFolder(1)*

C問題のCはCounterのC。
collections.CounterSiS_iを数えるだけです。Counter便利。
import sys
from collections import *

def i2s(): return sys.stdin.readline().rstrip()
def i2n(): return int(i2s())

N=i2n()
def main():
    cnt = Counter()
    for i in range(N):
        s = i2s()
        if s not in cnt:
            print(s)
        else:
            print(f'{s}({cnt[s]})')
        cnt[s] += 1
    return

main()

D - Flipping and Bonus*

D問題のDはDPのD。
DP設計するのに手間取ってパフォ落としました。
ii回目のコイントスでカウンタjj時の最大スコアをdpi,jdp_{i,j}と定義します。
またカウンタjj時のボーナスをBjB_jとします。 すなわちBCi=YiB_{C_i} = Y_iです。
また設定されていない場合は0にしておきます。
ii回目のコイントスが表であるとき、i1i-1回目よりカウンタが1増えてXiX_{i}のスコアとBjB_jのボーナスを得るので
dpi,j=dpi1,j1+Xi+Bjdp_{i,j} = dp_{i-1,j-1} + X_{i} + B_j
です。 このとき、カウンタが1増えるのでj1j \geq 1です。
コイントスが裏の場合、スコアは得られずカウンタが0になるため、i+1i+1回目のカウンタj=0j=0のスコアがii回目でまでで得られるスコアのうち最大のものなります。よって
dpi,0=maxj>0dpi1,jdp_{i,0} = \max_{j>0}dp_{i-1,j}
です。
よって、次のようになります。 ii回目のカウンタはiiを超えないことに注意です。(最初に全部Nまでループしてたら答えが合いませんでした。)
import sys
sys.setrecursionlimit(2**31-1)

def s2ss(s): return s.split()
def s2nn(s): return list(map(int, s2ss(s)))
def i2s(): return sys.stdin.readline().rstrip()
def i2ss(): return s2ss(i2s())
def i2n(): return int(i2s())
def i2nn(): return s2nn(i2s())

N,M=i2nn()
X=i2nn()
B=[0]*(N+1)
for _ in range(M):
    c,y = i2nn()
    B[c] = y
    
def main():
    dp = [[0]*(N+1) for _ in range(N+2)]
    for i in range(1,N+1):
        dp[i+1][0] = dp[i][0]
        for j in range(1,i+1):
            dp[i][j] = dp[i-1][j-1] + X[i-1] + B[j]
            dp[i+1][0] = max(dp[i+1][0], dp[i][j])
    print(dp[-1][0])
    return

main()

E - Many Operations

時間内に解けませんでした。
終了後、Twitterでbit毎に管理するというのを見かけてコードを書いたところACできました。
opr[i]にi番目のbitに対する操作を定義し、随時更新していっています。 具体的には
  • 0: 0にする
  • 1: 1にする
  • -1: そのまま(操作なし)
  • -2: bit反転
としています。初めはすべて-1です。
入力に対して、
  • AND: Xのbitが0の桁iに対応するopr[i]を0 (元のbitにかかわらず0になる)
  • OR: Xのbitが1の桁iに対応するopr[i]を1 (元のbitにかかわらず1になる)
  • XOR: Xのbitが1の桁iに対応するopr[i]の1bit目を反転
とoprを更新します。
こうすることで、opr[i]を 0 ↔ 1-1 ↔ -2 で切り替えることができ、例えばANDで0にセットされたあとにXORが適用されれば1になり、-1で操作なしであったbitならば-2で反転になり、逆に-2で反転のときはそれを打ち消して操作なしに戻すことができます。
import sys

def s2ss(s): return s.split()
def s2nn(s): return list(map(int, s2ss(s)))
def i2s(): return sys.stdin.readline().rstrip()
def i2ss(): return s2ss(i2s())
def i2n(): return int(i2s())
def i2nn(): return s2nn(i2s())

N,C=i2nn()

def main():
    p = C
    opr = [-1 for _ in range(30)]
    for i in range(N):
        t, x = i2nn()
        r = 0
        for i in range(30):
            if t == 1:
                if not x & 1 << i:
                    opr[i] = 0
            elif t == 2:
                if x & 1 << i:
                    opr[i] = 1
            elif t == 3:
                if x & 1 << i:
                    opr[i] ^= 1
                    
            if mask[i] == 1:
                r += 1 << i
            elif opr[i] < 0:
                r += (p if opr[i] == -1 else ~p) & 1 << i
        print(r)
        p = r
    return

main()
これをACしたあと、Kiri氏のユーザー解説を見てしめやかに爆発四散しました。
s0:=0s_0 := 0s1:=2301s_1 := 2^{30}-1に対して随時操作を行い、各bitを2変数から適宜選択するだけです。
シンプルですごい。

Discussion

コメントにはログインが必要です。