🦁
【python】100日後に緑コーダーになるためのABC178 C,D,E問題【11日目】
はじめに
100日後に緑コーダーになるためにAtcoder Beginner Contest178の解説を行います。
今回はC ~ E問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。
対象読者
灰・茶コーダー
C - Ubiquity
解法
包徐原理
出題者の意図
包徐原理を理解しているか
考察
制約が大きすぎるため全探索はできない
0以外で構成させる配列や、9以外で構成される配列をベン図を用いて考えると解くことができる。
コード
N = int(input())
MOD = pow(10,9) + 7
ans = pow(10,N) -(2*pow(9,N) - pow(8,N))
print(ans%MOD)
D - Redistribution
解法
配列の項数を管理して組み合わせ
出題者の意図
組み合わせの関数が組めるか
考察
配列は3以上の値で構成されている。
前もって2だけで構成させた配列があるとして考えて、残りの数字を書く配列に1個以上配っていく
この時に組み合わせを使う
コード
S = int(input())
from math import factorial
####組み合わせ####
def comb(n,k):
if n < k:
return 0
if k == 0:
return 1
bunshi = 1
for kk in range(k):
bunshi *= n
n -= 1
return bunshi//factorial(k)
########
lmt = S//2
MOD = pow(10,9) + 7
ans = 0
for i in range(lmt):
temp = S - 2*(i+1)
ans += comb(temp-1,i)
ans %= MOD
print(ans)
E - Dist Max
解法
マンハッタン距離は45度回転
出題者の意図
マンハッタン距離の性質を理解しているか
考察
マンハッタン距離の問題は45度回転や中央値を使うことが多い。
今回は45度回転のようだ
理由はこのサイトが詳しいのでぜひ読んでみてください
コード
N = int(input())
V = []
W = []
for i in range(N):
x,y = map(int,input().split())
V.append(x+y)
W.append(x-y)
print(max(max(V)-min(V),max(W)-min(W)))
Discussion