😸

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

2021/11/20に公開

Python

AtCoder

競プロ

tech

はじめに

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

対象読者

灰・茶コーダー

A - Counting

解法

四則演算

出題者の意図

四則演算ができるか
問題の制約を見て条件分岐できるか

コード

A,B = map(int, input().split())
if A>B:
    print(0)
    exit()
print(B-A+1)

B - Can you buy them all?

解法

Nまでに偶数が何個あるか

出題者の意図

商の切り捨てを使えるか
適切なif文を使えるか

コード

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

sumA = sum(A)
discount = N//2

if sumA-discount <= X:
    print('Yes')
else:
    print('No')

C - Not Equal

解法

$C$ をソートして小さい順から選んでいく。
$i$ が1増えるごとに $Ci$ を1減らしていく。

出題者の意図

$A$ の組み合わせの数が $C$ の順番に依らないことに築けるか
小さい順に選んでいったほうがより多く組み合わせが作れることに気付けるか
ソートできるか

考察

制約が $1\leqC\leq10^9$ と大きいことから全ての組み合わせを数え上げることは難しい。
簡単に方法があるはず。
$Ai{=}\llap{/\,}Aj(1≤i<j≤N)$ に注目すると、前から $Ai$ を選んでいくと後半になるにつれて選択肢が狭まっていくことがわかる。
故に小さい順から選べば $Ai$ の選択肢を多く残していくことができるので、後は $Ai$ の取りうる値の個数を掛け合わせていけば答えが求まる。

コード

N = int(input())
C = list(map(int,input().split()))
C.sort() #小さい順にソート
MOD = pow(10,9)+7 #階乗表記はpow関数が便利

ans = 1
for i in range(N):
    temp = C[i] - i 
    if temp == 0: 
        print(0)
        exit()
    ans = ans * temp
    ans = ans % MOD

print(ans)

D - Collision

解法

BFS（幅優先探索）かDFS（深さ優先探索）で色（偶奇）を付けていって、計算量 $O(1)$ でクエリを判定

出題者の意図

BFS、DFSを使えるか
木のグラフが見えるか

考察

最短経路の問題に見えるのでダイクストラ法などが思い浮かぶが、NとQの制約から当然TLEする。
クエリが与えられた瞬間に答えを出せるようになれば間に合いそうである。
ここでグラフの構造を確認すると

頂点がN個
辺がN-1本
どの頂点も繋がっている
以上からグラフが木であることがわかる。
また、ある点から他の全ての頂点までの距離の偶奇が分かっていれば、任意の2点間から出発して最短経路を通るときに、頂点か辺のどちらで出会うかが $O(1)$ で判定可能
ある頂点からBFSかDFSで距離を調べていき、その距離が偶奇かどうかを配列に保存していけばよい。

コード

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

####BFS####
#隣接リスト作成
G = [[] for _ in range(N)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
from collections import deque
#幅優先探索
def bfs(s):
    q = deque()  #キューを作成
    q.append(s)
    dist = [-1]*N
    color = [0]*N
    dist[s] = 0  #初期条件
 
    while q:
        n = q.popleft()
        for n2 in G[n]:  #取り出したキューの隣接リストを調べる
            if dist[n2] == -1:  #ノードが未探索の時
                q.append(n2)  #最初に取り出したキューから繋がっているノードをキューに追加
                dist[n2] = dist[n] + 1  #距離の情報を更新 
                color[n2] = dist[n2]%2   
    return dist,color
########   


_,ans = bfs(0)

for _ in range(Q):
    c,d = map(int,input().split())
    if ans[c-1] == ans[d-1]:
        print('Town')
    else:
        print('Road')

はじめに

対象読者

A - Counting

解法

出題者の意図

コード

B - Can you buy them all?

解法

出題者の意図

コード

C - Not Equal

解法

出題者の意図

考察

コード

D - Collision

解法

出題者の意図

考察

コード

Discussion