소개

안녕하세요

어제는 피곤해서 오늘 기사를 쓰기로 결정했습니다. 최근 뜨거워졌습니다. 교토도 기온이 28℃까지 올라 봄의 끝 장마의 방문을 느끼고 있습니다.

알고리즘의 공부도 하고 싶습니다만, 이달중에 기본 정보 기술자 시험을 받아야 하지요. 그래서, 그쪽이 끝나는 대로 알고리즘의 공부는 본허를 넣을 수 있을까.

이번은 이런 느낌으로 Rating 참아 주었습니다. 1주일 만에 코드를 썼기 때문에 이것이 위험한 결과가 될 것이라고 생각했지만, 의외로 어떻게든 꽤 있었습니다. 역시 어떤 때라도 매주 계속해서 ABC 콘테스트는 참가하는 것이 좋네요. 이대로 내려가지 않으면 이달 중 초록 갈 수 있을 것 같습니다!


이하 ABC203의 링크입니다 [ htps : // 아 t 여기 r. jp / 이런 sts / 아 bc203 ]

전체 감상

은근하게 본 느낌 D문제가 서투른 깊이 우선 탐색이나 폭 우선 탐색의 어느 쪽인가,라고 생각했으므로 A, B, C 문제를 곧바로 끝내기로 했습니다.
A, B, C 자체는 어렵지 않고 20분이 걸릴 정도로 끝났습니다. 거기서 80 분에 걸쳐 D 문제를 생각했지만 모르겠습니다 ...
중앙값을 구하는 문제였습니다만, 우선 어디를 연못으로 하는지의 개소에서 계산을 간단하게 하지 않으면 안 될까라고 생각하기도 했습니다.

각 문제의 감상

A 문제

피곤해서 뇌사로 그대로 코드를 썼습니다.

a,b,c=map(int,input().split())

if a==b :
    print(c)
elif a==c :
    print(b)
elif b==c :
    print(a)
else :
    print(0)

B 문제

n층에서 k실의 방이 각 층에 존재한다. 각 방 번호는 i층 j번째라면 i0j가 된다.
그래서 처음에는 각 층의 100위를 더해, 1위에 대해서는 각 층 k*(k+1)//2이므로 이것을 더해 갔습니다.
어렵지 않았기 때문에 이것도 곧 풀었습니다.

n,k=map(int,input().split())
ans=0

for i in range(n) :
    ans+=(i+1)*100*k+k*(k+1)//2
print(ans)

C 문제

친구의 수가 2*10*5이므로, 소트하고 나서 for문으로 돌려도 O(4*10*5)로 계산은 시간에 맞을 것이라고 생각했습니다.
나중에 친구가있는 마을에 걸리는 돈을 계산하고 소지금에서 빼고 음수가되면 거기까지 도착할 수있는 마을의 최대 번호를 계산합니다. 친구의 마을에 붙는 경우는, 거기에서 받을 수 있는 금액분 소지금을 늘렸습니다.
보통 for문과 실장력이 묻는 문제였습니다.

n,k=map(int,input().split())
cnt=[]

for i in range(n) :
    a,b=map(int,input().split()) #aは村番号,bはお金
    cnt.append([a,b])
cnt.sort()

flag=0
for i in range(n) :
    if flag+k<cnt[i][0] :
        print(flag+k)
        exit()
    k-=(cnt[i][0]-flag)
    k+=cnt[i][1]
    flag=cnt[i][0]
if k+flag>10**100 :
    print(10**100)
else :
    print(k+flag)

D 문제

해설을 읽으면 아무래도 이분 탐색과 2차원 누적합을 이용하는 것 같네요. 솔직히 말하면 '2차원 누적 합'이라는 단어는 처음 들었습니다.
이 문제에 대해서는 좀 더 자세히 공부하고 나서 편집하고 싶다...라고 생각합니다.

N,K=map(int,input().split())
A=[]

for i in range(N):
  temp=list(map(int,input().split()))
  A.append(temp)


#2分探索法
ok=10**9
ng=-1

lim = int(K*K/2)+1

def ruise2D(border):
  # 2次元累積和
  s=[[0]*(N+1) for i in range(N+1)]
  for i in range(N):
    for j in range(N):
      s[i+1][j+1] = s[i+1][j]+s[i][j+1]-s[i][j]
      if(A[i][j] > mid):
        s[i+1][j+1] += 1

  for i in range(0,N-K+1):
    for j  in range(0,N-K+1):
      #累積和から2分探索。よくわかってない。
      if((s[i+K][j+K] -s[i][j+K] -s[i+K][j]+s[i][j])<lim):
        return True
  return False


while((ng+1)<ok):
  mid =(ng+ok)//2
  if(ruise2D(mid)):
    #基準より小さい物があれば、探索範囲の上側をカット
    ok=mid
  else:
    #基準よりすべて大きければ、探索範囲の下をカット
    ng=mid
print(ok)

E, F 문제

읽을 시간도 풀 시간도 없었어요...
전기 중 과연 E문제를 풀 수 있을까?

마지막으로

나중에 Atcoder Problem에서 D 문제의 난이도를 확인하면 파란색 수준이었습니다. 그러나, 여기가 풀릴지 어떨지에 초록 이후의 성장이 바뀌어 온다고 생각합니다. 그래서, 이번 달 하순의 기본 정보 기초의 시험이 끝나는 대로, 알고리즘의 공부 노력하겠습니다! !
이번 달에는 최선을 다하고 녹색입니다.