ABC291 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、初級者向け？の競技プログラミングコンテストのことです。

参加者はレーティングによってランク分けされます。私は8ランクあるうち、下から2番目のランク（茶色）のため、まだまだひよっこです。一つ上のランク（緑色）を目指して、現在精進しています。

ABCでは毎回8題の問題が出題され、後半の問題ほど、難易度が高くなります。ここでは私が戦える前半4題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC291

A – camel Case

問題

A問題

英大文字が文字列の何文字目に登場するかを調べる問題です。

解説

大文字かどうかは、isupper()メソッドで調べることができます。

コード

s = input()

for i in range(len(s)):
    if s[i].isupper():
        print(i + 1)
        exit()

B – Trimmed Mean

問題

B問題

審査員たちが選手に出した評点の平均を求める問題です。ただし、上位N個の評点と下位N個の評点を除外して、平均を求めなければなりません。あまりに高い評点や低い評点が選手の得点に影響を与えてしまうことを防ぐためですね。

解説

この問題のポイントは、審査員たちが選手に出した評点を事前にソートしておくことです。こうしておくことで、上位や下位について考えやすくなります。

審査員は500人以下ですので、ソートは十分可能です。(10^5くらいまでなら問題なし)

あとは上位下位を除いた評点の平均を素直に求めれば良いです。

コード

N = int(input())
X = list(map(int, input().split()))

X = sorted(X)  # Xを評点でソートしておく
sum = 0

for i in range(N, 4 * N):
    sum += X[i]

print(sum / (3 * N))

C – LRUD Instructions 2

問題

C問題

二次元平面上をNマス移動し、その間に同じマスに複数回訪れることがあったかを調べる問題です。

解説

集合で訪れたマスを管理しましょう。

移動後のマスが集合に登録されていなければ、集合に登録します。

移動後のマスが集合に登録されていれば、過去に一度訪れた証ですね。なので、”Yes”と出力します。

“Yes”と一度も出力することがなければ、最後に”No”と出力しましょう。

モノの存在管理をするのに集合はとても便利です。Pythonにおいて、要素の検索にリストはO(N)かかりますが、集合だとO(1)で済むためです。

コード

N = int(input())
S = input()

x, y = 0, 0
s = {(0, 0)}

for char in S:
    if char == "R":
        x += 1
    elif char == "L":
        x -= 1
    elif char == "U":
        y += 1
    else:
        y -= 1

    if (x, y) in s:
        print("Yes")
        exit()
    else:
        s.add((x, y))

print("No")

D – Flip Cards

問題

D問題

両面に数字が書かれたN枚のカードについて、隣に同じ数字が現れないような表裏の選び方が何通りあるかを調べる問題です。

解説

この問題を見たとき、中学受験数学でお馴染みの「最短経路の道順の本数」の問題を思い出しました。以下の参考リンクが非常に分かりやすいので、ぜひ見てみてください。

【参考】最短経路の道順の本数（アルゴ式への外部リンク）

ある点にたどり着く場合の数は、その手前の点にたどり着く場合の数の和になるという考え方です。これを利用して、手前の点から順次、場合の数を求めていけます。

今回のD問題も本質は同様です。

k+1枚目までのカードの表裏の選び方の場合の数は、k枚目が表になるような選び方の場合の数と、k枚目が裏になるような選び方の場合の数の和になります。（ただし、k+1枚目がk枚目と同じ数字になる場合は、足してはいけないことに注意です）

そうやって1枚目から、場合の数を求めていけばよいわけですね。

つまりこれって、、、DP（動的計画法）の問題なんです。

「D問題のDはDPのD」

コード

from sys import stdin
N = int(input())
l = [list(map(int, stdin.readline().split())) for _ in range(N)]

# dp[i][j]:i+1枚目までの表裏の選び方の数
# j=0のときi+1枚目は表とし、j=1のときi+1枚目は裏とする
dp = [[0] * 2 for _ in range(N)]
dp[0][0] = 1
dp[0][1] = 1

for i in range(1, N):
    if l[i][0] != l[i - 1][0]:
        dp[i][0] += dp[i - 1][0]
    if l[i][0] != l[i - 1][1]:
        dp[i][0] += dp[i - 1][1]
    if l[i][1] != l[i - 1][0]:
        dp[i][1] += dp[i - 1][0]
    if l[i][1] != l[i - 1][1]:
        dp[i][1] += dp[i - 1][1]
    dp[i][0] = dp[i][0] % 998244353
    dp[i][1] = dp[i][1] % 998244353

print((dp[N - 1][0] + dp[N - 1][1]) % 998244353)