ABC247A~DをPythonで解く！

はじめに

ABC247に参戦しA~D問題を完答できたためシェアします！

A Move Right

問題

0101のような0,1で作られる4文字の文字列を右に１つずらした場合の文字列を求めよ(意訳)

解答

左から3つ目までを取り出し左に0をつければよいです。
0101 → 0010

S = input()
print('0'+S[:3])

B Unique Nicknames

問題

N人、人がおりi番目の人の名字・名前は$s_i,t_i$で与えられます。
N人のニックネームを次のルールで名付けます。
1.それぞれのニックネームは名字$s_i$か名前$t_i$
2.他の人の名字・名前に無いニックネームを名付けなければならない
このルールのもと全員にニックネームを付けられるか

解答

ルール2から、それぞれの人は唯一の名字・名前をもっていないとニックネームをつけてもらえません。
したがって、名字・名前をカウントし唯一の名字と名前を持たない人がいる場合Noとなります。
また、ルール2が満たされていればルール1を満たすように選べます。
注意点として、名字と名前が同じ場合にカウントを重複させないようにしましょう。

from collections import defaultdict
N = int(input())
name = [input().split() for _ in range(N)]
named = defaultdict(int)
for i in range(N):
    if name[i][0] == name[i][1]:
        named[name[i][0]] += 1
    else:
        named[name[i][0]] += 1
        named[name[i][1]] += 1
for i,j in name:
    if named[i] == 1 or named[j] == 1:
        continue
    else:
        print('No')
        break
else:
    print('Yes')

C 1 2 1 3 1 2 1

問題

$S_1=1,\ S_n=S_{n-1}\ n \ S_{n-1} \ (n=2,3,...,N)$を満たす文字列を出力してください。

例 (N=3)
$S_1=1$
$S_2=S_1 \ 2 \ S_1 = 1 \ 2 \ 1$
$S_3=S_2 \ 3 \ S_2 = 1 \ 2 \ 1 \ 3 \ 1 \ 2 \ 1 $

解答

再帰関数を用いて$S_n = S_{n-1} \ n \ S_{n-1}$を実行したらよいです。
ただし$n=1$のときは1を返します。

import sys
sys.setrecursionlimit(100000)

def Num(num):
    if num == 1:
        return '1'
    return Num(num-1) + ' ' + str(num) + ' ' + Num(num-1)
N = int(input())
print(Num(N))

D Cylinder

問題

筒にボールを入れる。もしくは出すQ回のクエリを処理してください。
クエリは
1 x c
2 c
で与えられ先頭が1の場合は筒にボールを入れる。2の場合は筒の左からボールを出します。
ただし、出す処理において筒に入っているボールより多く取り出すことはありません。

解答

筒に入っているボールより多く取り出すことはないため、筒にボールをすべて入れてから取り出す処理をしても逐次取り出す場合と変わりません。そこで、
・ボールの数字をもつ配列ball
・ボールの累積個数を持つ配列num
・ボールの数字×ボールの個数の累積和をもつ配列Sum
・取り出すボールの累積和を持つ配列queries
を用意し、まずクエリを保存します。
例えば、
4
1 2 2
1 3 3
2 3
1 0 2
2 3
のクエリに対してそれぞれの配列は
ball = [2,3,0]
num = [2,5,7]
Sum = [4,13,13]
queries = [3,6]

なぜnum,Sum,queriesを累積和にしたか

以下の図のように、各処理ごとに合計値を計算するため累積和の配列を用意しています。
1回目の取り出し

2回目の取り出し

n回目の取り出し

iをどう求めるか

num[i] < n回目までに取り出されたボールの数(queries[n]) <= num[i]となるiを二分探索により求めます。
numは累積和であり、昇順となっているため二分探索が有効です。

求めたiを用いて上図のようにn回目に取り出す合計値を求めれば終了です。

def bisect(x):
    ok = len(num)
    ng = -1
    while ok-ng>1:
        mid = (ok+ng)//2
        if x<= num[mid]:
            ok = mid
        else:
            ng = mid
    if x < num[ok]:
        return Sum[ok]-ball[ok]*(num[ok]-x)
    else:      
        return Sum[ok]

Q = int(input())
ball = []
num = [0]
Sum = [0]
queries = [0]
for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        ball.append(query[1])
        Sum.append(Sum[-1]+query[1]*query[2])
        num.append(num[-1]+query[2])
    else:
        queries.append(queries[-1]+query[1])
num = num[1:]
Sum = Sum[1:]
queries = queries[1:]
pre = 0
for i in queries:
    q = bisect(i)
    ans = q-pre
    pre = q
    print(ans)