📝

AtCoder Beginner Contest 276 レポート

2022/11/06に公開

AtCoder

Python 3

tech

摘要

ABCDE5完でした．
DEで無駄なWAを出して時間を溶かさなければもう少しレートを上げられたと思います．

ABC276

コンテスト名: AtCoder Beginner Contest 276
順位: 1226th / 8495
パフォーマンス: 1332
レーティング: 1180 → 1196 (+16)
コンテスト参加回数: 62

A - Rightmost

A - 問題

文字列 $S$ で最後に'a'が現れる位置を求めよ．

A - 解法

特筆事項なし．
後ろから見ていけばもっとよかった．

A - ACコード

def main():
    S = input()

    ans = -1
    for i, s in enumerate(S):
        if s == 'a': ans = i+1

    print(ans)


if __name__ == '__main__': main()

B - Adjacency List

B - 問題

$N$ 頂点の無向グラフについて，各頂点の隣接リストを求めよ．

B - 解法

特筆事項なし．

B - ACコード

def main():
    N, M = map(int, input().split())
    graph = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].add(b)
        graph[b].add(a)

    for g in graph[1:]:
        ans = len(g), *sorted(g)
        print(*ans)


if __name__ == '__main__': main()

C - Previous Permutation

C - 問題

$(1, 2, \dots, N)$ の順列を辞書順に並べた時，与えられた $P \neq (1, 2, …, N)$ の一つ前の順列 $Q$ を求めよ．

C - 解法

末尾の増加区間を調べて並び替える．
後ろから見ていけばもっとよかった．

C - ACコード

from bisect import bisect


def main():
    N = int(input())
    P = list(map(int, input().split()))

    l, r = 0, 0
    for i in range(1, N):
        if P[i-1] < P[i]: r += 1
        else: l, r = i, i

    tail = sorted(P[l:])
    idx_h = bisect(tail, P[l-1])-1
    head = tail[idx_h]
    tail[idx_h] = P[l-1]
    tail.reverse()

    ans = P[:l-1] + [head] + tail
    print(*ans)


if __name__ == '__main__': main()

D - Divide by 2 or 3

D - 問題

正整数列 $A = (a_1, a_2, \dots, a_N)$ に対して，各要素を2または3で何回割ることで全て等しくすることができるか判定せよ．

D - 解法

各 $a_i$ について，

a_i = 2^{p_i} * 3^{q_i} * {r_i} (r_i \not\equiv 0 \bmod 2, r_i \not\equiv 0 \bmod 3)

を満たす $(p_i, q_i, r_i)$ を求める．
$r_i$ がただ一つに定まるとき， $\sum (p_i - min(p) + q_i - min(q))$ が答え．

問題文をよく読まずに， $r = 1$ という条件を勝手に考えて2WA．

D - ACコード

def main():
    N = int(input())
    A = list(map(int, input().split()))

    arr = [[0]*N for _ in range(2)]
    st = set()
    for i, ai in enumerate(A):
        while not ai % 2:
            ai //= 2
            arr[0][i] += 1
        while not ai % 3:
            ai //= 3
            arr[1][i] += 1
        st.add(ai)

    if len(st) > 1: ans = -1
    else:
        arr[0].sort(), arr[1].sort()
        ans = sum(arr[0]) - arr[0][0]*N + sum(arr[1]) - arr[1][0]*N

    print(ans)


if __name__ == '__main__': main()

E - Round Trip

E - 問題

$H$ 行 $W$ 列のマス目について，スタート地点から障害物のマスを通らず，かつ同じマスを二度通ることなく長さ4以上の経路で戻ることができるか判定せよ．

E - 解法

スタート地点も障害物とみなした上で，スタート地点に隣接する二つのマスを結ぶ経路があるかをDFSにより調べるだけ．
方針は秒で思いつき，実装も特に手間取ることなくサクッとできたつもりがWA．
原因はスタート隣接マスについて障害物マスの除外し忘れ．

E - ACコード

from itertools import combinations
from collections import deque


def main():
    global H, W, C, dr
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    dr = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    nbh = set()
    for i in range(H):
        for j in range(W):
            if C[i][j] != '.': continue
            for di, dj in dr:
                if 0 <= i+di < H and 0 <= j+dj < W and C[i+di][j+dj] == 'S': nbh.add((i, j))

    if len(nbh) < 2: ans = 'No'
    else:
        for (si, sj), (gi, gj) in combinations(nbh, 2):
            d = dfs((si, sj), (gi, gj))
            if d > 0:
                ans = 'Yes'
                break
        else: ans = 'No'

    print(ans)


def dfs(s, g):
    si, sj, gi, gj = *s, *g
    dist = [[-1]*W for _ in range(H)]
    dist[si][sj] = 0

    deq = deque([s])
    while deq:
        i, j = deq.popleft()
        for di, dj in dr:
            if 0 <= i+di < H and 0 <= j+dj < W and C[i+di][j+dj] == '.' and dist[i+di][j+dj] == -1:
                dist[i+di][j+dj] = dist[i][j] + 1
                deq.append((i+di, j+dj))

    return dist[gi][gj]


if __name__ == '__main__': main()

F - Double Chance

F - 問題

長さ $N$ の整数列 $A$ について，次の試行を $N$ 回行い，その得点の期待値 $(\bmod 998244353)$ を求めよ．

$i (1 \leq i \leq N)$ 回目の試行: A[:i]から無作為に整数を2回選び，その最大値を得点とする．

F - 検討

方針は正しく立てられていたと思う．
$i$ 回目の期待値ans[i]は，

2回ともA[:i-1]から選ぶ場合
2回ともA[-1]を選ぶ場合
A[:i-1], A[-1]から1回ずつ選ぶ場合

の3パターンを考えればよく，最後のケースについて，
「Fenwick Treeなんか使って区間和が取れれば良さそう」
まで考えるも実装できず．

        ans[i] = (
            ans[i-1] * pow(i, 2, MOD) +
            (sum(max(ar, ai) for ar in arr)-ai) * 2 + # ここで区間和使いたかった
            ai
        ) * pow(i+1, -2, MOD) % MOD

感想

結果だけ見れば5完，パフォーマンス1332と及第点と言えそうです．
ただ，C, D問題で細かい問題文の読み落としや実装ミスがあったところは反省が必要ですね．
F問題については，Fenwick TreeやBITなどまだまだ使い慣れていないデータ構造の訓練をこれからしていきたいなと思います．