ABC211のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
よかったらLGTMしていただけると、私のやる気がでます！
ほしいものリスト よかったらプレゼントしてくれるとやる気が出るかもしれないです！
目次
ABC211 まとめ
A問題『Blood Pressure』
B問題『Cycle Hit』
C問題『chokudai』
D問題『Number of Shortest paths』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC211 まとめ
全提出人数: 8604人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 15分 | 6271(6047)位 |
| 400 | AB---- | 300 | 8分 | 5131(4907)位 |
| 600 | AB---- | 300 | 3分 | 4210(3986)位 |
| 800 | ABC--- | 600 | 19分 | 3262(3044)位 |
| 1000 | ABCD-- | 1000 | 75分 | 2397(2183)位 |
| 1200 | ABCD-- | 1000 | 47分 | 1695(1484)位 |
| 1400 | ABCD-- | 1000 | 30分 | 1171(962)位 |
| 1600 | ABCD-- | 1000 | 20分 | 793(588)位 |
| 1800 | ABCDE- | 1500 | 98分 | 508(337)位 |
| 2000 | ABCDE- | 1500 | 69分 | 327(178)位 |
| 2200 | ABCDE- | 1500 | 51分 | 214(87)位 |
| 2400 | ABCDE- | 1500 | 29分 | 147(40)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3937 | 97.9 % | 92.3 % | 18.2 % | 9.4 % | 0.1 % | 0.0 % |
| 茶 | 1451 | 99.5 % | 99.3 % | 57.5 % | 39.1 % | 0.6 % | 0.0 % |
| 緑 | 1143 | 99.7 % | 99.7 % | 86.4 % | 76.8 % | 2.0 % | 0.1 % |
| 水 | 669 | 99.7 % | 99.5 % | 98.4 % | 96.7 % | 23.2 % | 0.8 % |
| 青 | 361 | 100.0 % | 100.0 % | 100.0 % | 99.5 % | 45.7 % | 7.5 % |
| 黄 | 171 | 95.9 % | 95.9 % | 96.5 % | 95.9 % | 64.3 % | 37.4 % |
| 橙 | 35 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 88.6 % | 77.1 % |
| 赤 | 18 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % |
※表示レート、灰に初参加者は含めず
A問題『Blood Pressure』
問題ページ：A - Blood Pressure
灰コーダー正解率：97.9 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.7 %
考察
何も考えずに問題文の通りに書けばいいです。
コード
def main():
A, B = map(int, input().split())
print((A - B) / 3 + B)
if __name__ == '__main__':
main()
B問題『Cycle Hit』
問題ページ：B - Cycle Hit
灰コーダー正解率：92.3 %
茶コーダー正解率：99.3 %
緑コーダー正解率：99.7 %
考察
$S_i$ として与えられる文字列は必要な文字列 H,2B,3B,HR $4$ 種類のいずれかで、関係ない文字列は与えられません。与えられる文字列が何種類か数えて、$4$ 種類ならば H,2B,3B,HRがすべて $1$ つずつあります。
実装
set型を使って重複を省き、lenで $4$ 種類揃っているか判定するのが楽です。
コード
def main():
S_set = set()
for _ in range(4):
S = input()
S_set.add(S)
print('Yes' if len(S_set) == 4 else 'No')
if __name__ == '__main__':
main()
C問題『chokudai』
問題ページ：C - chokudai
灰コーダー正解率：18.2 %
茶コーダー正解率：57.5 %
緑コーダー正解率：86.4 %
競プロ典型90問の 008 - AtCounter（★4） と、文字列が異なる以外は全く同じ問題です。
考察
動的計画法です。
最終的に求めたいのは、$N$ 文字目まで見たときの chokudaiの組み合わせ数です。
chokudai を作るには、それまでにchokudaが必要です。
chokudaを作るには、それまでにchokudが必要です。
chokudを作るには、それまでにchokuが必要です。
chokuを作るには、それまでにchokが必要です。
chokを作るには、それまでにchoが必要です。
choを作るには、それまでにchが必要です。
chを作るには、それまでにcが必要です。
そこで、$i$ 文字目までに c, ch, cho, chok, choku, chokud, chokuda, chokudai それぞれが何回作れるか記録しておきます。
$i$ 文字目までに cho が $100$ 通り、chok が $10$ 通り作れるとします。そして、文字列の $i+1$ 文字目が k だとします。このとき、$i+1$ 文字目までで作れるchok は $100$ 通りの cho に kをくっつけてできる $100$ 通りと、今までに既に作れた$10$ 通りを足して $100 + 10 = 110$ 通りになります。
実装
二次元リストdp[i][j]で動的計画法をしてもいいですが、$i+1$ 文字目を決めるために必要なのは $i$ 文字目の情報だけであり、$0$ か $1$ 箇所しか変更がないため、$1$ つの $1$ 次元リストを使い回して構いません。
リストの代わりにCounterを使うことで、chokudaiの文字をそのまま添字として使うことができます。
コード
MOD = 10 ** 9 + 7
def main():
from collections import Counter
S = input()
T = '*chokudai' # 0文字目は英小文字でない適当な記号にします
dp = Counter()
dp['*'] = 1
for char in S:
if char in T:
char_prev = T[T.index(char) - 1] # charの前の文字、iの前はa、cの前は*
dp[char] += dp[char_prev]
dp[char] %= MOD
print(dp['i'])
if __name__ == '__main__':
main()
D問題『Number of Shortest paths』
問題ページ：D - Number of Shortest paths
灰コーダー正解率：9.4 %
茶コーダー正解率：39.1 %
緑コーダー正解率：76.8 %
考察
辺の長さがすべて $1$ のグラフの、頂点 $1$ から他の全頂点への最短経路の長さは、幅優先探索で求めることができます。
幅優先探索を応用して、最短経路の長さだけでなく、最短経路の組み合わせ数も別にカウントすることで解けます。
スタートからゴールまでの最短距離が $3$ だとします。このとき、答えは 『ゴールに繋がっている最短距離が $2$ の頂点への最短経路の組み合わせ数』の合計です。
『最短距離が $2$ の各頂点への最短経路の組み合わせ数』は、『各頂点につながっている最短距離が $1$ の頂点への最短経路の組み合わせ数』です。
『最短距離が $1$ の各頂点への最短経路の組み合わせ数』は、『各頂点につながっている最短距離が $0$ の頂点（スタート地点）への最短経路の組み合わせ数』です。
コード
INF = 1 << 60
MOD = 10 ** 9 + 7
def main():
from collections import deque
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
edge[a].append(b)
edge[b].append(a)
dist = [INF] * N
dp = [0] * N
dist[0] = 0
dp[0] = 1
que = deque((0,))
while que:
u = que.popleft()
curr_cost = dist[u]
next_cost = curr_cost + 1
for v in edge[u]:
# INFから更新以外ないです
if next_cost < dist[v]:
que.append(v)
dist[v] = next_cost
if next_cost == dist[v]:
dp[v] += dp[u]
dp[v] %= MOD
print(dp[-1])
if __name__ == '__main__':
main()