ABC200

소개



만나서 반갑습니다.

현재는 교토에 살고 있는 대학원생입니다. atcoder에 관한 투고를 실시하고 싶다고 생각합니다.

최근 지난달까지 취활을 하고 있었습니다. 다랑이라는 것으로, 심지어 단단한 취활이 코로나에 의해 한층 더 베리 하드가 된다고는 불안해졌습니다. 그러나 특히 넘어지지 않고 안전하게 끝낼 수있었습니다.

내부 결정을받은 기업에게 감사드립니다.

atcoder의 현재 속도는 아래 그림과 같은 느낌입니다. 불행히도 불행히도 한가로운 성장 속도이지만 최선을 다할 것입니다.



자습을하고 재활하고 나서 ABC에 참가할까 고민했지만, 실천있는 것만으로는 기념해야 할 ABC200에 참가했습니다.

ABC200[ h tps // 아 t 여기 r. jp / 이런 sts / 아 bc200 ]

전체 감상



A, B, C 문제는 15분 정도로 해답할 수 있었습니다. 그러나 D문제는 전혀 모르고 1시간 생각한 후 포기하고 목욕에 들어갔습니다.

순위를 도중에 본 느낌, 다른 사람도 D문제로 고전하고 있는 것처럼 보였습니다.

각 문제의 감상



A 문제



100으로 나눠서 나누어질 수 있을지 1을 더할지 판별했습니다.
n=int(input())
if n%100==0 :
    print(n//100)
else :
    print(n//100+1)

B 문제



조작대로 구현했을 뿐입니다. 200의 배수라면 200으로 나누고, 그렇지 않으면 1000배를 곱한 후 200을 더했습니다.
n,k=map(int,input().split())
for i in range(k) :
    if n%200==0 :
        n=n//200
    else :
        n=n*1000+200

print(n)

C 문제



200이라는 숫자가 나오면 나오는 것은 200번째이기 때문일까라고 생각하면서 C문제를 풀었습니다.

"차이를 취했을 때 200으로 나눌 수 있는 조합의 개수는"이라는 문제였습니다. 차이를 취해 200으로 나눌 수 있다는 것은, 바꿔 말하면 「200으로 나눈 때, 나머지가 같은 숫자 중에서 2조를 선택한 경우의 수」일까라고 생각했습니다.

그래서 count라는 리스트를 만들고, 나머지가 i가 되는 숫자가 수열에 있으면 count의 인덱스 i에 1을 더해 개수를 세었습니다.

마지막으로 count 리스트내에 2 이상의 숫자 n이 나오면, nC2로 계산했습니다.
n=int(input())
a=list(map(int,input().split()))
count=[0]*200
ans=0

for i in a :
    count[i%200]+=1
for i in count :
    if i==0 or i==1 :
        continue
    else :
        ans+=i*(i-1)/2
print(int(ans))

D 문제



이것에 관해서는 풀고있는 동안은 확실히 몰랐습니다. 수열 B, C는 뭔가 개수도 다른 경우가 있는 것 같고 무엇이든 있는 것인가? 라고 생각해, 어떻게 하면 좋은지 전혀였습니다.

해설을 읽으면 아무래도 비둘기 둥지 원리를 사용하는 것 같습니다. 경쟁 프로보다는 더 이상 수학입니다,,,
8종류의 나머지가 존재하면, 2**8=256으로 일단 256종류의 숫자가 나오기 때문에, 적어도 나머지는 0부터 199까지 존재하고, 256-200=56으로 56개는 어딘가 너무 입는 것 같습니다.

처음에는 256종류의 숫자에 대해, 원래 모두 다른 나머지(0에서 199의 나머지가 출현)가 되는 보증은 있는가? 라든지, 그 경우 8 종류의 선택 방법에도 무언가조차 조건이 있는 것은? 라든지, 불필요한 일을 생각했습니다.

여기의 범위에 대해서는 고교 수학 A의 정수 분야에 대해서 다시 학습하는 것이 좋을 것 같아,,,
n=int(input())
a=list(map(int,input().split()))
m=min(n,8)
count=[0 for _ in range(200)]

for i in range(1,2**m) :
    cnt=0

    #----enumerateはインデックスと要素を出力----#
    for j,k in enumerate(a) :
        if i>>j&1 :
            cnt+=k
    cnt%=200
    if count[cnt]==0 :
        count[cnt]=i

    #----同じ余りが二つある場合----#
    else :

        #----先にi番目について----#
        print("Yes")
        blst=[]
        clst=[]
        for l in range(m) :
            if i>>l&1 :
                blst.append(l+1)
        i=count[cnt]

        #----次にcount[cnt]に書かれている順番について----#
        for o in range(m) :
            if i>>o&1 :
                clst.append(o+1)
        print(len(blst),*blst)
        print(len(clst),*clst)
        exit()

print("No")

E, F 문제



아직 저에게는 푸는 것은 빠른 것 같습니다. 정진하고 나서 언젠가 풀어줍니다.

수론 쓰기 전에는 풀 수 있게 되고 싶다 (욕망)

마지막으로



오랜만의 ABC였습니다만, 생각 외에 풀었습니다. 요율도 오르고 만만세입니다. 9월 이후는 수론이 본격적으로 시작되어, 그쪽의 코드를 써야 하기 때문에, 아마 ABC에 참가할 수 있는 빈도는 내려갈까.

7월중에는 꼭 초록까지 가고 싶네요.

좋은 웹페이지 즐겨찾기