Codeforces Round 943 (Div. 3)

드디어 시험 다 끝난날

교내대회 회의 후 피곤해서 몬스터 한캔 빨고 스타트

친구들 집와서 치킨시켜서 쉬운거 빨리 풀고 어려운건 치킨뜯으면서 생각하며 풀려 했다.

결과

A번 풀이

문제

https://codeforces.com/contest/1968/problem/A

알고리즘 분류 

브루트포스, 수학

 

풀이

i가 1~x-1까지 gcd(i,x)+i가 max가 되는 i찾기.

다풀고나서 잘 생각해보니 max(gcd(i,x))가 x/2인것 같은데, 항상 최대값은 x가 되는거 아닌가?

gcd(x-1,x)+x-1은 x고 그럼 항상 x-1만 출력해줘도 가능했을지도,,

from sys import stdin
from math import *
input=stdin.readline

for _ in range(int(input())):
    x=int(input())
    mx=0
    ans=0
    for i in range(1,x):
        now=gcd(i,x)+i
        if mx<=now:
            mx=now
            ans=i
    print(ans)

B번 풀이

문제

https://codeforces.com/contest/1968/problem/B

알고리즘 분류 

문자열, 그리디, 투포인터

 

풀이

a의 접미사가 b의 부분 문자열이 되는 가장 긴 접미사 찾기, 이걸 해석하는게 가장 어려웠다. 영어 너무 어렵다

b는 삭제가 가능하기 때문에 LCS 구하듯이 그냥 같은거면 계속 증가시켜줘서 구해주면 된다. 태그에 투포인터도 있던데 a,b에 각각 포인터를 둬서 그런가? 또 생각 안하고 2번 문제면 2중 for 되겠지 했다 +1 TLE..

from sys import stdin
input=stdin.readline

for _ in range(int(input())):
    n,m=map(int,input().split())
    s1=input().rstrip()
    s2=input().rstrip()
    s=''
    ans=0
    idx1=0
    idx2=0
    try:
        while True:
            if s1[idx1]==s2[idx2]:
                idx1+=1
                idx2+=1
            else:
                idx2+=1
    except:
        ans=max(ans,idx1)
    print(ans)

C번 풀이

문제

https://codeforces.com/contest/1968/problem/C

알고리즘 분류 

정수론, 구성적

풀이

숫자가 컸으면 오래걸렸을 것 같다. 숫자가 작아서 규칙을 찾아서 풀었다. a(i)%a(i-1)인데 a(i)가 a(i-1)+j 인 경우 나머지가 j이니까 이 규칙을 이용해 계속 증가시켜주는 방식으로 해결했다.

from sys import stdin
input=stdin.readline

for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    ans=[501]
    for i in range(n-1):
        ans.append(ans[-1]+arr[i])    
    print(*ans)

D번 풀이

문제

https://codeforces.com/contest/1968/problem/D

 

알고리즘 분류

DFS, 게임이론, 수학

 

풀이

이 문제 되게 좋았던 것 같다. k가 크지만 n이 작으므로 n개 모두 방문했다면 더이상 방문할 필요가 없다. x1->x2->x1로 가서 점수를 얻는 이득이 없다. 점수가 x1>x2라면 x1->x1->x1이 이득이고, x1<x2인 경우 x1->x2->x2 가이득이다. 따라서 이미 갔던 곳은 다시 방문할 필요가 없다. 그래서 현재까지 이동하며 얻은 점수 + 현재 자리에서 시간이 다 지날때 까지 남아있을 때 얻을 수 있는 점수를 n개의 지점에 대해 모두 구해주면 해결 할 수 있었다.

 

from sys import stdin
input=stdin.readline

for _ in range(int(input())):
    n,k,pb,ps=map(int,input().split())
    perm=list(map(int,input().split()))
    arr=list(map(int,input().split()))
    pb-=1
    ps-=1
    mxb=0
    t=0
    now=0
    vib=[0]*n
    vis=[0]*n
    while vib[pb]==0 and t<k:
        mxb=max(mxb,now+arr[pb]*(k-t))
        now+=arr[pb]
        vib[pb]=1
        pb=perm[pb]-1
        t+=1
    mxs=0
    t=0
    now=0
    while vis[ps]==0 and t<k:
        mxs=max(mxs,now+arr[ps]*(k-t))
        now+=arr[ps]
        vis[ps]=1
        ps=perm[ps]-1
        t+=1
    if mxb>mxs:
        print("Bodya")
    elif mxb<mxs:
        print("Sasha")
    else:
        print("Draw")

E번 풀이

문제

https://codeforces.com/contest/1968/problem/E

알고리즘 분류

구성적

 

풀이

치킨 먹으면서 아무리 고민해봐도 답이 생각이 안났다.

앞에 쉽게 풀려서 기분 좋았는데ㅠㅠㅠㅠ

 

 

후기

1주뒤 div4도 장전완료