😸

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

2021/11/20に公開

はじめに

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

対象読者

灰・茶コーダー

A - Counting

https://atcoder.jp/contests/abc209/tasks/abc209_a

解法

四則演算

出題者の意図

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

コード

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

B - Can you buy them all?

https://atcoder.jp/contests/abc209/tasks/abc209_b

解法

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

https://atcoder.jp/contests/abc209/tasks/abc209_c

解法

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

出題者の意図

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

考察

制約が1≤C≤10^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

https://atcoder.jp/contests/abc209/tasks/abc209_d

解法

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')

Discussion