AtCoder Regular Contest 105

Aしか解けなかった...

atcoder.jp

A - Fourtune Cookies

takuroooooo.hatenablog.com

この記事で練習したbit全探索を使ってAC 解説読むと等符号の関係(A<=B<=C<=D)からA+D=B+CとA+B+C=Dのにパターンだけを確認すればよいらしい。

提出したコード

arr = list(map(int,input().split()))
 
n = len(arr)
for bit in range(1<<n):
  x = 0
  y = 0
  for i in range(n):
    if bit & (1<<i):
      x += arr[i]
    else:
      y += arr[i]
  if x == y:
    print('Yes')
    exit(0)
print('No')

B - Max-=min

他の人は結構解けていたみたいだけど、解けなかった... 与えられた数列のgcdを計算すればよいとのこと。

解説みてACしたコード

import math
import functools
N=int(input())
A=list(map(int,input().split()))
ans = functools.reduce(math.gcd, A)
print(ans)

これと全く同じ問題が過去のABCで出ていた。 atcoder.jp

解けた人のコメントを読むと

• N=2を手計算していたらユーグリッドの互除法と同じ操作であることに気づいた
• N=2でいくつかパターンを計算したら答えあがgcdあることに気づいた

といった感じなので簡単な例で試すってこととgcdの性質をちゃんと理解していることが必要だと思った。(0<=x<=yのときgcd(x,y)==gcd(x,y-x)は同じになるなど)

gcdの記事があったのでこれ読んで勉強してみよう。 qiita.com