🍣

【python】100日後に緑コーダーになるためのABC208 A,B,C,D問題【1日目】

2021/11/19に公開

Python

AtCoder

競プロ

tech

はじめに

100日後に緑コーダーになるためにatcoder Beginner Contest208の解説を行います。
今回はA~D問題です。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

A - Rolling Dice

解法

A個のサイコロの合計が取りうる範囲にBが存在するか判定

出題者の意図

サイコロの目の制約に気付けるか
条件分岐できるか

コード

A,B = map(int,input().split())
if B <= A*6 and B>=A:
    print('Yes')
else:
    print('No')

B - Factorial Yen Coin

解法

大きいコインから順番に使っていく

出題者の意図

while文とif文を適切に使えるか
階乗のライブラリが使えるか

コード

P = int(input())

from math import factorial
coin = 10
ans = 0
while P != 0:
    temp = factorial(coin)
    coin -= 1
    if temp>P:
        continue
    ans += P//temp
    P %= temp
print(ans)

C - Fair Candy Distribution

解法

優先度付きキューで余ったお菓子を貰える人を判定

出題者の意図

優先度付きキューを使えるか
個数管理にdefaultdictが使えるか(使わなくも解ける)

考察

まずKがNの倍数なら国民全員に平等にお菓子が配られる。
KがNの倍数でないなら余りが生じる。この余りを番号の小さい人から順番に配っていく。
番号が小さいものを優先的に処理するなら優先度付きキューが便利。
あとは誰が余りを貰うかをdefaultdictで管理して、その人たちの答えをprintするときに平等に配られられた個数+1でOK（解説を書いてる途中に余分に貰う人はsetで管理したほうが楽なことに気づきましたが、1日目なのでご愛嬌ということで）
計算量
優先度付きキュー： $O(logN)$

コード

from collections import defaultdict
from heapq import heapify, heappop
from re import split

N,K = map(int, input().split())
A = list(map(int, input().split()))
B = A.copy() #Aをコピー
heapify(B) #Bを優先度付きキュー化

sho = K//N
amari = K%N

kashi = defaultdict(int) #個数管理
for i in range(amari):
    p = heappop(B)
    kashi[p] += 1

for a in A:
    print(sho+kashi[a])

D - Shortest Path Queries 2

解法

ワーシャルフロイド法そのまま

出題者の意図

ワーシャルフロイド法をキチンと理解しているか
計算量を意識しているか

考察

最短経路アルゴリズムを考えてみる。

ダイクストラ法：単一始点最短経路。無向グラフ対応、計算量 $O((V+E)logV)$
ベルマンフォード法：単一始点最短経路。有向グラフ対応、負数対応、計算量 $O(VE)$
ワーシャルフロイド法：全点対最短経路。有向グラフのみ、計算量 $O(V^3)$
*V：頂点数、E：辺の数
何だかワーシャルフロイド法が計算量が大きい感じがする。
ここで問題の制約を確認してみる。

1≤N≤400
0≤M≤N(N−1)
M(辺の数)が非常に大きいためダイクストラ法とベルマンフォード法の計算量がぐっと上がる。ほとんどワーシャルフロイド法と変わらない計算量になってしまった。

この問題の注目すべきポイントは全ての2点間のコストを計算することである。
ダイクストラ法とベルマンフォード法は計算量がさらにあがり計算量が $O(V^4)$ になってしまう。
そのためワーシャルフロイド法で問題を解こう。

ワーシャルフロイド法では中間の点を番号の小さい順で選んでいく。
問題ではK以下の頂点を使って最短経路で始点から終点に移動するので、それぞれの中間点1つだけを考えたときの最短経路を足していくと答えになる。
※解答はpypyで提出してください。pythonだとTLEします。
計算量
ワーシャルフロイド法： $O(V^3)$

コード

N,M = map(int,input().split())

####ワーシャルフロイド法####
#計算量：N^3
## graph with N nodes and M edges
#グラフの作成
INF = 1 << 60
edges = [[INF]*N for _ in range(N)]
for i in range(N):
    edges[i][i] = 0
for _ in range(M):
    x, y, z = map(int, input().split())
    edges[x-1][y-1] = z 

def warshall_floyd(N):
    ans = 0
    for k in range(N): #中間点を固定
        for i in range(N):
            for j in range(N):
                edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
                if edges[i][j] != INF: #値が更新されたとき
                    ans += edges[i][j]
    return ans

print(warshall_floyd(N))

はじめに

対象読者

A - Rolling Dice

解法

出題者の意図

コード

B - Factorial Yen Coin

解法

出題者の意図

コード

C - Fair Candy Distribution

解法

出題者の意図

考察

コード

D - Shortest Path Queries 2

解法

出題者の意図

考察

コード

Discussion