🦁

【python】100日後に緑コーダーになるためのABC178 C,D,E問題【11日目】

1 min read

はじめに

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

対象読者

灰・茶コーダー

C - Ubiquity

https://atcoder.jp/contests/abc178/tasks/abc178_c

解法

包徐原理

出題者の意図

包徐原理を理解しているか

考察

制約が大きすぎるため全探索はできない
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

https://atcoder.jp/contests/abc178/tasks/abc178_d

解法

配列の項数を管理して組み合わせ

出題者の意図

組み合わせの関数が組めるか

考察

配列は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

https://atcoder.jp/contests/abc178/tasks/abc178_e

解法

マンハッタン距離は45度回転

出題者の意図

マンハッタン距離の性質を理解しているか

考察

マンハッタン距離の問題は45度回転や中央値を使うことが多い。
今回は45度回転のようだ
理由はこのサイトが詳しいのでぜひ読んでみてください

https://kagamiz.hatenablog.com/entry/2014/12/21/213931

コード

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

ログインするとコメントできます