あるぱかのブログ

AtCoder茶(レート566)

AtCoder Beginner Contest 360

久々に気持ちよく勝った（？）ので書きます

atcoder.jp

A - A Healthy Breakfast

リンク：A - A Healthy Breakfast (atcoder.jp)

概要： R,M,Sからなる文字列で R,Mの順番を見て何かしら出力してね

  • 文字列に対してindex()でその文字の位置を調べる
  • index('R')とindex('M')を比べてindex('R')のほうが小さい（Rのほうが左にある）場合はYesを出力する
#ABC360 A - A Healthy Breakfast
S = input()
if S.index('R') < S.index('M'):
    print('Yes')
else:
    print('No')  

提出リンク：提出 #55046050 - AtCoder Beginner Contest 360

B - Vertical Reading

リンク：B - Vertical Reading (atcoder.jp)

概要：文字列 Sを分割して拾ってつくった文字列が文字列 Tと一致するか調べてね

A～D問題の中で一番苦戦した。

計算量気にせず書いてあることを実装すればOKだけどfor文がややこしくなって大変だった。

以下の順にfor文をネストする。

  • 文字列 Sを w文字ごとに区切ることを決める（関数fを定義して実際に区切りました）
  • 区切った文字列で c文字以上の文字列を見ることに決める
  • 区切った文字列を順番に見ていって c文字目を拾い集める
#ABC360 B - Vertical Reading
def f(s, n):
    ans = []
    while len(s) >= n:
        ans.append(s[:n])
        s = s[n:]
    if s != '':
        ans.append(s)
    return ans
S, T = map(str, input().split())
N = len(S)
for w in range(1, N):
    now = f(S, w)
    for c in range(w):
        s = ''
        for i in range((N+w-1)//w):
            try:
                s += now[i][c]
            except:
                break
        if s == T:
            print('Yes')
            exit()
print('No')      

提出リンク：提出 #55081290 - AtCoder Beginner Contest 360

C - Move It

リンク：C - Move It (atcoder.jp)

概要：同じ箱に入っている荷物を一番重いものが残るように操作してね

典型ど真ん中みたいな問題で安心。BよりCのほうが正答率高いの面白い。

全ての箱に1つずつ荷物を残すということで、箱の中にある荷物を軽い順に取り出す貪欲をやります。

  • defaultdictにlistを持たせて箱の番号と中身の重さを管理
  • 箱の中身の個数によって処理を変えるのが面倒なので、すべて取り出して一番重いものを戻す処理にする
#ABC360 C - Move It
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
W = list(map(int, input().split()))
box = defaultdict(list)
for i in range(N):
    box[A[i]].append(W[i])
ans = 0
for key in box:
    if len(box[key]) > 1:
        ans += sum(box[key])
        ans -= max(box[key])
print(ans)  

提出リンク：提出 #55063033 - AtCoder Beginner Contest 360

D - Ghost Ants

リンク：D - Ghost Ants (atcoder.jp)

概要：蟻が数直線上をトコトコするのですれ違う組数をカウントしてね

以下の処理を二分探索を使って高速に処理します。

自身を越える最小値と、自身を越えない最大値を探索するコードをライブラリ化しておくと便利です（ABC353-C、ABC355-Dで出たのに今回のコンテスト後やっとライブラリ化しました）。

本番中は丹精込めた手打ちで盛大にバグらせてWA。

  • 右向きと左向きでグループ分けする
  • 右向きグループに着目して、初期の座標と終了時（初期+2T）の間にいる左向きの蟻の数をカウントする
def upper(A, N): #超えない最大
    l = 0
    r = len(A)-1
    if A[r] <= N:
        return r
    if A[0] > N:
        return -1
    ans = 0
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] <= N:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
def lower(A, N): #超える最小
    l = 0
    r = len(A)-1
    if A[r] < N:
        return -1
    if A[0] >= N:
        return 0
    ans = r
    while l+1 < r:
        mid = (l+r)//2
        if A[mid] >= N:
            ans = mid
            r = mid
        else:
            l = mid
    return ans
N, T = map(int, input().split())
S = input()
X = list(map(int, input().split()))
right = []
left = []
for i in range(N):
    if S[i] == '1':
        right.append(X[i])
    else:
        left.append(X[i])
right = sorted(right)
left = sorted(left)
ans = 0
for i in range(len(right)):
    l = lower(left, right[i])
    r = upper(left, right[i]+2*T)
    if l >= 0 and r >= 0 and l <= r:
        ans += (r-l+1)
print(ans)  

提出リンク：提出 #55112663 - AtCoder Beginner Contest 360