AtCoder Beginner Contest 261 まとめ

AtCoder Beginner Contest 261の個人的に実装できた解法まとめです。

特筆がなければPyPy3です。

*がついてるものは時間内にACできた問題になります。

atcoder.jp

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

atcoder.jp

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

atcoder.jp

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

atcoder.jp

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のボーナスを得るので

\displaystyle{ dp\_{i,j} = dp\_{i-1,j-1} + X\_{i} + B\_j }

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

コイントスが裏の場合、スコアが得られずカウンタが0になるため、i+1回目のカウンタj=0のスコアがi回目でまでで得られるスコアのうち最大のものなります。よって

\displaystyle{ 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()

atcoder.jp

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

atcoder.jp

これをACしたあと、Kiri氏のユーザー解説を見てしめやかに爆発四散しました。シンプルですごい。

atcoder.jp