ABC178

久々の激冷え2完…

毎度ながら場合の数の計算にめっぽう弱い私だが今回ももれなく弱さを発揮してしまった。
かなり手遅れ状態だったため、5問目の方が簡単なのでは？と思い解こうとするもダメ。正答者数からすれば取れそうではあるのだが。

ABC178　C

考えたこと
全体は10のN乗。ここまではわかる。これしかわからなかった。単純な計算式があるんだろうなとは思っていたが全く思いつかなかった。

答え
0を全く使わないパターンが9のN乗、9を全く使わないパターンが9のN乗あり、両方を使わないパターンがここに被るように8のN乗あるためこれを足す。ウームわからん。
なお素直に行くとタイムアウトの為、繰り返し二乗法などを使って短縮する必要もある。これ下位茶パフォですかそうですか…

N=int(input())
 
 
 
div=10**9+7
def po(x,n,M):
    res=1
    if n>0:
        
        res= po(x,n//2,M)
    if n%2==0:
        res=(res*res)%M
    else:
        res=(((res*res)%M)*x)%M
        
      
    return res
 
A=po(10,N,div)
B=po(9,N,div)
C=po(8,N,div)
ans=(A-2*B+C)%div
print(ans)

ABC178 D

考えたこと
C問題がわからないのにまたも場合の数の問題である。わかるわけもない。
これも当たり前ながら2以下は3以上から答えが増えていき、一気に増加していきそう（小学生並みの発想）

答え
え？DPなんですか？
実験をしっかりしていれば答えにたどり着いたかもしれないが、上位陣は何食べたら1分とかで解けるの？

N=int(input())
 
DP=[-1]*10000
 
DP[0]=1
DP[1]=0
DP[2]=0
mod=10**9+7
 
for i in range(3,N+1):
    DP[i]=(DP[i-3]+DP[i-1])%mod
 
print(DP[N])

いうほどDPだろうか？考察がすべての問題だなあ。とりたいがとれないなこれは。

ABC178　E

CDEの中で一番簡単そうに見える。実際かなり簡単な気もする。
なお解けなかった模様。式変形に全く気付かず、愚直にやってWAであきらめた。
検索すれば答えが出てきていたのかもしれないが、それはまた違う気もするが、それもまたありな気もする。

N=int(input())
minz=10**11
minw=10**11
maxz=-10**11
maxw=-10**11
for i in range(N):
 
    a,b=map(int,input().split())
    if  a+b>maxz:
        maxz=a+b
 
    if a+b<minz:
        minz=a+b
 
    if  a-b>maxw:
        maxw=a-b
 
    if a-b<minw:
        minw=a-b
 
    
 
print(max((maxz-minz),(maxw-minw)))