留学生のプログラミング勉強日記

化学系学部から情報系大学院への進学する学生です

10月20日の勉強

2024.10

1.競技プログラミング4問

1.

https://www.acmicpc.net/problem/17626

import math
a = int(input())
dplist = [0] + [math.inf] * 50000
numlist = [k * k for k in range (1, 224)]
for i in numlist:
    for j in range(len(dplist)):
        if i + j >= 50001:
            break
        dplist[i + j] = min(dplist[i + j], dplist[j] + 1)
print(dplist[a])

典型的なDP問題でリストを設計すると解けた

2.

https://www.acmicpc.net/problem/18870

import sys
num = int(sys.stdin.readline())
numlist = list(map(int, sys.stdin.readline().split()))
numset = set(numlist)
numsetlist = sorted(list(numset))

numsetdict = {}

for i in range(len(numsetlist)):
    a = numsetlist[i]
    numsetdict[a] = i

answerlist = [0] * num

for i in range(num):
    ansnum = numlist[i]
    ansnum = numsetdict.get(ansnum)
    answerlist[i] = ansnum
    
for i in answerlist:
    print(i, end = ' ')

今までのプログラミングでは主にlist型で解決していたので、この問題にもリストを用いて試したが、時間複雑度問題があった。

その問題を解決するため、dictに関する関数をあるブログから学んで、参考にしたブログの内容をColabにマークダウン形式で書いといた。

その内容を下に示す。

https://eumgill98.tistory.com/101 より

dict

| Operation           | Example         | Class    | Notes                                |
|---------------------|-----------------|----------|--------------------------------------|
| 1. Store            | d[k] = v        | O(1)     | 데이터 저장                           |
| 2. Length           | len(d)          | O(1)     | 딕셔너리 길이 출력                    |
| 3. Delete           | del d[k]        | O(1)     | 요소 제거                             |
| 4. Get/Set Default  | d.get(k)        | O(1)     | key에 따른 value 확인                |
| 5. Pop              | d.pop(k)        | O(1)     | pop                                  |
| 6. Pop Item         | d.popitem()     | O(1)     | 랜덤하게 선택해서 pop                |
| 7. Clear            | d.clear()       | O(1)     | s = {}와 유사 / 딕트 초기화           |
| 8. View             | d.keys()        | O(1)     | 키 목록 확인                          |
| 9. Construction     | dict(...)       | O(len(...)) | (key, value) 튜플 개수만큼 생성  |
| 10. Iteration       | for k in d:     | O(N)     | 전체 딕셔너리 순회                    |

set

| Operation           | Example          | Class          | Notes                                  |
|---------------------|------------------|----------------|----------------------------------------|
| 1. Add              | s.add(5)         | O(1)           | 집합 요소 추가                          |
| 2. Containment      | x in/not in s    | O(1)           | 포함 여부 확인                          |
| 3. Remove           | s.remove(..)     | O(1)           | 요소 제거                               |
| 4. Discard          | s.discard(..)    | O(1)           | 특정 요소 제거                          |
| 5. Pop              | s.pop()          | O(1)           | 랜덤하게 하나 pop                       |
| 6. Clear            | s.clear()        | O(1)           | s = set()와 유사                        |
| 7. Construction     | set(...)         | O(len(...))    | 길이만큼 생성                           |
| 8. Check ==, !=     | s != t           | O(len(s))      | 전체 요소 동일 여부 확인               |
| 9. ≤, <             | s <= t           | O(len(s))      | 부분 집합 여부 확인                    |
| 10. ≥, >            | s >= t           | O(len(t))      | 부분 집합 여부 확인                    |
| 11. Union           | s, t             | O(len(s) + len(t)) | 합집합                              |
| 12. Intersection    | s & t            | O(len(s) + len(t)) | 교집합                              |
| 13. Difference      | s - t            | O(len(s) + len(t)) | 차집합                              |
| 14. Symmetric Diff  | s ^ t            | O(len(s) + len(t)) | 여집합                              |
| 15. Iteration       | for v in s:      | O(N)           | 전체 요소 순회                         |
| 16. Copy            | s.copy()         | O(N)           | 복제                                   |

list

| Operation           | Example          | Class          | Notes                                  |
|---------------------|------------------|----------------|----------------------------------------|
| 1. Index            | l[i]             | O(1)           | 인덱스로 값 찾기                        |
| 2. Store            | l[i] = 0         | O(1)           | 인덱스로 데이터 저장                    |
| 3. Length           | len(l)           | O(1)           | 리스트 길이                             |
| 4. Append           | l.append(5)      | O(1)           | 리스트 뒤에 데이터 저장                |
| 5. Pop              | l.pop()          | O(1)           | 가장 뒤의 데이터 pop                   |
| 6. Clear            | l.clear()        | O(1)           | l = []                                 |
| 7. Slice            | l[a:b]           | O(b-a)         | 슬라이스되는 요소 수 만큼 비례          |
| 8. Extend           | l.extend(...)    | O(len(...))    | 확장하는 리스트의 길이만큼              |
| 9. Construction     | list(...)        | O(len(...))    | 리스트 길이만큼 생성                   |
| 10. Check ==, !=    | l1 == l2         | O(N)           | 전체 리스트가 동일한지 확인            |
| 11. Insert          | l[a:b] = ...     | O(N)           | 데이터 삽입                             |
| 12. Delete          | del l[i]         | O(N)           | 데이터 삭제                             |
| 13. Containment     | x in/not in l    | O(N)           | 포함 여부 확인                         |
| 14. Copy            | l.copy()         | O(N)           | 복제                                   |
| 15. Remove          | l.remove(...)    | O(N)           | 제거                                   |
| 16. Pop             | l.pop(i)         | O(N)           | 제거된 값 이후를 전부 한칸씩 당겨줌     |
| 17. Extreme Value   | min(l)/max(l)    | O(N)           | 전체 데이터를 확인해야 함              |
| 18. Reverse         | l.reverse()      | O(N)           | 뒤집기                                 |
| 19. Iteration       | for v in l:      | O(N)           | 전체 데이터 확인 방법                  |
| 20. Sort            | l.sort()         | O(N Log N)     | 파이썬 기본 정렬 알고리즘              |
| 21. Multiply        | k * l            | O(k * N)       | 리스트의 곱은 리스트 개수 늘어남       |

3.

https://www.acmicpc.net/problem/31460

import sys
testcase = int(sys.stdin.readline())
for i in range(testcase):
    choco = int(sys.stdin.readline())
    if choco == 1:
        print("0")
    else:
        choconum = 11 * (10 ** (choco - 2)) + 11
        print(choconum)

友達からリフレッシュ問題もらった。

癒された笑

4.

https://www.acmicpc.net/problem/6064

import math
import sys
num = int(sys.stdin.readline())
def findyear(a, b, c, d):
    lcm1 = math.lcm(a, b)
    i = 0
    if a == 1 or b == 1:
        print(max(c, d))#どっちも１の時にも注意
        return 0
    if c == d:
        print(c)
        return 0
    while a * i + c <= lcm1:
        answer = a * i + c
        if (a * i + c) % b == d or (a * i + c - d) % b == 0:#orに注意
            
            print(a * i + c)
            break 
        else:
            i += 1
    if a * i + c > lcm1:
        print("-1")

for _ in range(num):
    a, b, c, d = map(int, sys.stdin.readline().split())
    findyear(a, b, c, d)

エラーが生じる入力例が多すぎて大変だった。

特に条件分岐を無駄に増やし過ぎたこともあり、いいコードとは思わない。

ちょっと自慢

大学院試験が終わってからプログラミング練習15日目達成した

また、シルバー２とクラス３達成した。

自分が使っているサイトは問題別にランクづけられているのでゲームの感覚でプログラミング楽しんでる、最高。

2. Fuzzy c-Means(FCM)クラスタリング実装

進学予定の研究室からFCMの実装課題をもらった。

ドメインと言う概念がよくわからなくて、本とユーチューブ、ブログなどを参考してなんとなく分かるようになり、実装を行った。

未完成であるが、書けた分のコードを載せる

dots = []

pivotdot = []

pivotdot_past = []

clustered_dot = []

c = int(input("c = ?\n"))

theta = int(input("theta = ?\n"))

for i in range(len(x)):
  dots.append([x[i],y[i]]) #点をdotsに移す

for _ in range(c):
  pivotdot.append([])
which_dot = list(map(int,input("which_dot = ?\n").split()))

for i in range(c):
  pivotdot[i] = dots[which_dot[i]]

def dist(a,b):
  return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) #ノルムの2乗(前回の課題ではノルムを二乗することを忘れた)

def membership(a , b): #dot bがクラスター重心aにどのくらい属しているかメンバーシップをreturn

  global pivotdot
  global clustered_dot

  # if dots[b] in pivotdot:
  #   same = b

  # if b == same:
  #   for i in range(len(pivotdot)):
  #     clustered_dot[b][i] = 0
  #   return 0 여기 1로 되게 정리만 하면 끝임 --- 解決中

  uci = 0

  for j in range(len(pivotdot)):
    uci += (dist(dots[b], pivotdot[a]) / dist(dots[b],pivotdot[j])) ** (1 / (theta - 1))

  return 1 / uci

def clusteronce():

  global clustered_dot
  global pivotdot
  global pivotdot_past

  pivotdot_past = copy.deepcopy(pivotdot)

  clustered_dot = [[0] * c for _ in range(20)]

  #cの個数分の要素を作成
  #例えば、c = 3であると、[0, 1, 2]のリストが20個作成される。
  #二重リストの要素には各クラスターのメンバシップを入れるつもり

  for b in range(len(dots)):
    for a in range(len(pivotdot)):
      clustered_dot[b][a] = membership(a, b) #dot iがクラスターc(j)にどのくらい属しているか

  for j in range(c):
    bunsi_x = 0
    bunbo_x = 0
    bunsi_y = 0
    bunbo_y = 0
    for i in range(len(dots)):
      bunsi_x += ((clustered_dot[i][j]) ** (theta)) * dots[i][0]
      bunbo_x += clustered_dot[i][j] ** (theta)
      bunsi_y += ((clustered_dot[i][j]) ** (theta)) * dots[i][1]
      bunbo_y += clustered_dot[i][j] ** (theta)
      print(bunsi_x)
    pivotdot[j] = [bunsi_x / bunbo_x , bunsi_y / bunbo_y] #クラスター点を更新

コード汚すぎ。。

しかし、頑張って勉強してこのくらいって、もっと頑張らないと（Kaggle放置され過ぎだけど）。