28か月前公開・28か月前更新・0 pv・7 min read

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

ABCAtCoderPythonABC261

https://picsum.photos/seed/0445546044b34a0cb3c0171a981673b1/1200/630

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))

提出 #33432020

B - Tournament Result*

[0...N-1]

の二数の組み合わせ

i,j

について、

A_{i,j}

と

A_{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()

提出 #33439452

C - NewFolder(1)*

C問題のCはCounterのC。

collections.Counterで

S_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()

提出 #33442512

D - Flipping and Bonus*

D問題のDはDPのD。

DP設計するのに手間取ってパフォ落としました。

i

回目のコイントスでカウンタ

j

時の最大スコアを

dp_{i,j}

と定義します。

またカウンタ

j

時のボーナスを

B_j

とします。すなわち

B_{C_i} = Y_i

です。

また設定されていない場合は0にしておきます。

i

回目のコイントスが表であるとき、

i-1

回目よりカウンタが1増えて

X_{i}

のスコアと

B_j

のボーナスを得るので

dp_{i,j} = dp_{i-1,j-1} + X_{i} + B_j

です。このとき、カウンタが1増えるので

j \geq 1

です。

コイントスが裏の場合、スコアは得られずカウンタが0になるため、

i+1

回目のカウンタ

j=0

のスコアが

i

回目でまでで得られるスコアのうち最大のものなります。よって

dp_{i,0} = \max_{j>0}dp_{i-1,j}

です。

よって、次のようになります。

i

回目のカウンタは

i

を超えないことに注意です。（最初に全部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()

提出 #33482266

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()

提出 #33483214

これをACしたあと、Kiri氏のユーザー解説を見てしめやかに爆発四散しました。

s_0 := 0

と

s_1 := 2^{30}-1

に対して随時操作を行い、各bitを2変数から適宜選択するだけです。

シンプルですごい。

解説 #4495