留学生のプログラミング勉強日記 (original) (raw)
10月17日の勉強
1.競技プログラミング7問
1.
https://www.acmicpc.net/problem/17219
import sys a, b = map(int, sys.stdin.readline().split()) passdict = {} for i in range(a): c, d = sys.stdin.readline().split() passdict[c] = d for i in range(b): e = sys.stdin.readline().strip() if e in passdict: print(passdict[e])
e = int(input)からe = sys.stdin.readline().strip()に変えたら3000msから300msまでさがった笑。
2.
https://www.acmicpc.net/problem/11279
import heapq import sys heaplist = [] def push(a): global heaplist heapq.heappush(heaplist, [-a , a]) def pop(): global heaplist print(heapq.heappop(heaplist)[1]) num = int(input()) for i in range(num): a = int(sys.stdin.readline().strip()) if a == 0 and len(heaplist) == 0: print("0") elif a == 0: pop() else: push(a)
heapqライブラリについて勉強できた。
大学院入試の時にヒープデータ構造についてはかなり勉強したと考えたが、実際コードで取り組もうと思ったら無理だった笑
また、heapqはmin-heap(最小木)であるが、heaplistに[-a, a]として追加することでmaxheapのコードもできることが分かった。
3.
https://www.acmicpc.net/problem/1927
import heapq import sys heaplist = [] def push(a): global heaplist heapq.heappush(heaplist, a) def pop(): global heaplist print(heapq.heappop(heaplist)) num = int(input()) for i in range(num): a = int(sys.stdin.readline().strip()) if a == 0 and len(heaplist) == 0: print("0") elif a == 0: pop() else: push(a)
同じくheapqを応用することで解けた。
4.
https://www.acmicpc.net/problem/11286
import heapq import sys heaplist = [] def push(a): global heaplist heapq.heappush(heaplist, [abs(a) ,a]) def pop(): global heaplist print(heapq.heappop(heaplist)[1]) num = int(input()) for i in range(num): a = int(sys.stdin.readline().strip()) if a == 0 and len(heaplist) == 0: print("0") elif a == 0: pop() else: push(a)
5.
https://www.acmicpc.net/problem/11723
import sys num = int(input()) numset = set() def add(a): global numset numset.add(a) def remove(a): global numset numset.discard(a) def check(a): if a in numset: print("1") else: print("0") def toggle(a): if a in numset: numset.remove(a) else: numset.add(a) def all(): global numset numset = set(range(1, 21)) def empty(): global numset numset = set() for i in range(num): ex = sys.stdin.readline().split() if len(ex) == 2: defwhat = ex[0] whichnum = int(ex[1]) else: defwhat = ex[0] whichnum = None if defwhat == "add": add(int(whichnum)) elif defwhat == "remove": remove(int(whichnum)) elif defwhat == "check": check(int(whichnum)) elif defwhat == "toggle": toggle(int(whichnum)) elif defwhat == "all": all() elif defwhat == "empty": empty()
前回間違ってた問題解けた!!
もっとよさそうなコードもありそうだけど解いたことに意味があると考えてる。
6.
https://www.acmicpc.net/problem/11047
import sys n, k = map(int, input().split()) coin_list = [] how_many = 0 for i in range(n): coin_list.append(int(sys.stdin.readline())) for i in range(n): many = k // coin_list[n - 1 - i] k -= coin_list[n - 1 - i] * many how_many += many print(how_many)
dpぽく解いたけど貪欲法らしい。
7.
https://www.acmicpc.net/problem/11659
import sys n, m = map(int,input().split()) num_list = [0] nums = list(map(int, sys.stdin.readline().split()))
for i in range(n): num_list.append(num_list[i] + nums[i])
def answer(a, b): answer_a = num_list[a - 1] answer_b = num_list[b] return (answer_b - answer_a) for i in range(m): fir, sec = map(int, sys.stdin.readline().split()) print(answer(fir, sec))
前回に解けなかった問題、解け方はあってたけどまたコードを組む実力の問題だった(´;ω;`)
また、そろそろ時間複雑度も考えて問題を解けないと。。
大学院入試ではアルゴリズムの時間複雑度だけ考えてもできる問題が多かったが、リストや集合、dictionaryなどのファイルの形式によっての参照時間も考えないといけないことを気づいた。
反省
Kaggleやるって言ったのに競技プログラミングだけやっちゃった。
しかし、研究室でかくしてやるんでずっと集中して勉強することが困難であるため、週末頑張ろうと思ってる(後回し)
1. 競技プログラミング5問題
1.
https://www.acmicpc.net/problem/2775
num = int(input()) for i in range(num): a = int(input()) b = int(input()) num_list = [] for i in range(b + 1): num_list.append(i) if a == 0: print(b) else: for i in range(a): for j in range(b): num_list[j + 1] = num_list[j] + num_list[j + 1] print(num_list[b])
2.
https://www.acmicpc.net/problem/1181
一回目の答え:4120ms(Python 3使用)
num = int(input()) strlist = [] for i in range(num): a = input() if a in strlist: continue else: strlist.append(a) strlist.sort() strlist.sort(key = lambda x: len(x)) for i in strlist: print(i)
二回目:1280ms(PyPy 3使用)
num = int(input()) strlist = [] for i in range(num): a = input() if a in strlist: continue else: strlist.append(a) strlist.sort() strlist.sort(key = lambda x: len(x)) for i in strlist: print(i)
入力例
13 but i wont hesitate no more no more it cannot wait im yours
このように、入力の数が多いとpypyの方が有利であることが分かった。
+)sysライブラリー使用してみたが、時間はほぼ変わらなかったため、縦に長い(入力の数が多い)時はPyPyを使うべきだと考えた。
3.
https://www.acmicpc.net/problem/10828
num = int(input())
answerlist = []
def push(a):
global answerlist
answerlist.append(int(a))
def top():
global answerlist
if len(answerlist) == 0:
print("-1")
else:
print(answerlist[len(answerlist) - 1])
def pop():
global answerlist
if len(answerlist) == 0:
print("-1")
else:
print(answerlist[len(answerlist) - 1])
answerlist.pop()
def size():
global answerlist
print(len(answerlist))
def empty():
global answerlist
if len(answerlist) == 0:
print("1")
else:
print("0")
for i in range(num):
com = input().split()
if len(com) == 2:
a, b = com
else:
a = com[0]
b = None
if a == "pop": pop() elif a == "size": size() elif a == "empty": empty() elif a == "top": top() elif a == "push": push(b)
sysを使わなかったら396ms, sysを使用すると128msがかかった。
この問題の入力は
14 push 1 push 2 top size empty pop pop pop size empty pop push 3 empty top
2番目の問題のように縦長いが、sysを導入することで大きく結果が出せる時間に影響があった。
その理由は先ほど考察した内容と矛盾するため、自分では不明である。
4.
https://www.acmicpc.net/problem/1463
num = int(input()) num_list = [0] * (num + 1) for i in range (2, num+1) : num_list[i] = num_list[i-1] + 1 if i % 2 == 0: num_list[i] = min(num_list[i], num_list[i//2] + 1) if i % 3 == 0 : num_list[i] = min(num_list[i], num_list[i//3] + 1) print(num_list[num])
5.
https://www.acmicpc.net/problem/11399
import sys num = int(input())
people_list = list(map(int, sys.stdin.readline().split())) people_list.sort() answer = 0 for i in range(num): answer += people_list[i] * (num - i) print(answer)
考察と反省
sysを使用してコードの実行時間がちょっと増えることはあったが、場合によってはsysライブラリーを使用しないと実行時間に大きく損することが多かったため、今度からはsysライブラリを用いて入力をもらおうと考えてる。
反省:Kaggleのタイタニックのチュートリアルを様々なブログを参考して行ったが、その内容が完全には理解できなかったため、今日はそのリフレッシュとして競技プログラミングの練習を行った。
次の日からはKaggleにも力を入れたい。(Kaggleはまだ基礎固めさえもできてないんで)
1. 競技プログラミング 一問題(連続した日をくずたくなかったんで)
https://www.acmicpc.net/problem/1964
ただの数学問題。
五角形が大きくなることと伴って点の数を45678で割った余りをprintするとOk.
計算は数列として点の数を並ぶと、順で1 + 4, 1+ 4 +7 , 1+ 4 + 7 + 10 であったため、
(n (n + 1)) / 2を3倍したものにnを足して、1を足すことをそのままコードにぶち込んだ(よくはないけど)
多分時間の余裕があったら(ただ連続した日を崩したくないなどの理由ではなかったら笑)
全ての五角形から被る点の数を引くことをリストして表すのではないかと考えはいる。
n = int(input()) print(int((((3 * n * (n + 1))/2) + n + 1) % 45678))
2. Kaggleの勉強会
大学院試験も終わったため、Kaggleの勉強を始めようと考え、Kaggle勉強会を再開した。
しかし、前のKaggleの勉強会ではプログラミングに関しての知識がほぼ0かつ院試のための行列の勉強で頭がいっぱいであったため、実質初心者のままである。
よって、前回より何倍かは頑張らないと差が生じると考えるので、今度からKaggleの勉強も頑張っていきたいと思ってる。
今日はpandasのライブラリの基本操作(データ把握に使う)について勉強した。
その操作と結果、考察を下に示す。
事前準備
!pip install kaggle from google.colab import files files.upload()
Kaggleをインストール また、zipファイルをアップロードする。
!mkdir ~/.kaggle !cp kaggle.json ~/.kaggle/
!chmod 600 ~/.kaggle/kaggle.json
Kaggle Apiの設定(具体的にはわからない)
!kaggle competitions download -c titanic
from zipfile import ZipFile file_name = "/content/titanic.zip"
with ZipFile(file_name, 'r') as zip: zip.extractall() print('done')
注意
file_nameはダウンロードしたzipのファイル名にすること
import pandas as pd
train = pd.read_csv('./train.csv', index_col='PassengerId') test = pd.read_csv('./test.csv', index_col='PassengerId')
Pandasをインポート、また、データを読み取る。
注意
train, testを読むときに、Index_colはタイタニックの場合Idではなく、PassengerIdであったので他のファイルも同じ操作を行う際、考慮すること。
データの種類を把握する
train.head()
.head()
でエクセルのデータぽくデータの行と列の一部を見ることができる
train.info() print('#'*40) test.info()
.info()
でデータの順、non-null count, Dtypeを見ることができる。
0 Survived 891 non-null int64
1 Pclass 891 non-null int64
2 Name 891 non-null object
3 Sex 891 non-null object
4 Age 714 non-null float64
5 SibSp 891 non-null int64
6 Parch 891 non-null int64
7 Ticket 891 non-null object
8 Fare 891 non-null float64
9 Cabin 204 non-null object
10 Embarked 889 non-null object
参考にしたポストSubinium Tutorial Titanic (Beginner)(韓国語)によると、headでColumnの要素を表として見ることが可能になる。
.head()
の出力からデータのColumn中で分析に必要なさそうなColumnを把握し、後そのColumnをなくす。
また.info()
からはColumnの数と#, Non-null Count, Dtypeなどのさまざまな情報を見ることできる。
追記
.head()
は上の5項目だけを見せる。参考したブログ(韓国語)
.info()
の代わりにtrain.columns
でColumnを見ることが可能。
.info()
との違いは、下に示されているtrain.column
の出力を見ると、dtypeがobjectだけであることが分かる。
よって、.info()
の方がデータ別のDtypeを分かることが可能であるため、より正確にデータを持つと考える。(ただの素人が見た結果からの意見)
Index(['Survived', 'Pclass', 'Name', 'Sex', 'Age', 'SibSp', 'Parch', 'Ticket', 'Fare', 'Cabin', 'Embarked'], dtype='object')
.shape
はデータの行と列の数を出力する。
train.shape
.describe()
はデータのColumn別の統計量が分かる(mean, std, min, maxなど)
Survived Pclass Age SibSp Parch Fare
count 891.0000 891.0000 714.0000 891.0000 891.0000 891.0000 mean 0.383838 2.308642 29.699118 0.523008 0.381594 32.204208 std 0.486592 0.836071 14.526497 1.102743 0.806057 49.693429 min 0.000000 1.000000 0.420000 0.000000 0.000000 0.000000 25% 0.000000 2.000000 20.125000 0.000000 0.000000 7.910400 50% 0.000000 3.000000 28.000000 0.000000 0.000000 14.454200 75% 1.000000 3.000000 38.000000 1.000000 0.000000 31.000000 max 1.000000 3.000000 80.000000 8.000000 6.000000 512.329200
df['Column'].value_counts()
はdfのColumnに出る要素の頻度が分かる。
また、.value_counts()
を.value_counts(normalize=True)
に変えると、割合として出力する。
train['Age'].value_counts()
train['Survived'].value_counts(normalize =True)
.unique()
はそのColumnで唯一な値を出力する
train['Age'].unique()
array([22. , 38. , 26. , 35. , nan, 54. , 2. , 27. , 14. , 4. , 58. , 20. , 39. , 55. , 31. , 34. , 15. , 28. , 8. , 19. , 40. , 66. , 42. , 21. , 18. , 3. , 7. , 49. , 29. , 65. , 28.5 , 5. , 11. , 45. , 17. , 32. , 16. , 25. , 0.83, 30. , 33. , 23. , 24. , 46. , 59. , 71. , 37. , 47. , 14.5 , 70.5 , 32.5 , 12. , 9. , 36.5 , 51. , 55.5 , 40.5 , 44. , 1. , 61. , 56. , 50. , 36. , 45.5 , 20.5 , 62. , 41. , 52. , 63. , 23.5 , 0.92, 43. , 60. , 10. , 64. , 13. , 48. , 0.75, 53. , 57. , 80. , 70. , 24.5 , 6. , 0.67, 30.5 , 0.42, 34.5 , 74. ])
0.42や23.5などわけわからない年齢が出ているが、実際のデータにも同じ値があったため、.unique()
によって唯一値をarray
として出力していると考えられる
考察(2024 . 10 . 16)
前の段階で、色々なPandasライブラリの基本操作(データ種類把握用)について勉強した。
それより、未知のデータセットのデータの把握するにはどの順番でデータを把握したらいいかについて考えた。
その結果を下に示す。
.info()よりどのようなデータがあるか確認(.columnでもいいと考えるが、Dtype, non-null countなど.columnでは分からない情報があるため。)
.shapeでデータの数(行の数)を把握する。
.head()で5個のデータを把握し、必要なさそうでColumnを把握し、後にドロップする。
ドロップした後、種類が多いデータ(ここでは['Age'])を.describe()より平均値などを把握する。
['survived']など平均値で示すとより分かりにくいのは`.value_counts()を使用。
unique値はドロップするかしないか自分で考えて決める。
上述した順番はデータセットによっては良くないと考える。
例えば、性別によって結果が違うなどであると、性別を先に分離してから分析を行った方が良いと考える。(同じColumnのsexであるが、その値をまた分離する必要がある)
よって、データによってドロップするデータを増やしたり、Columnを要素の数を少なくしてから分析を行うことを自分で決めてデータの分析を行ったらより良い結果が得られると考える。
競技プログラミング4問題
https://www.acmicpc.net/problem/15829
num = int(input()) str1 = input() list_str = list(str1) for i in range (num): list_str[i] = ord(list_str[i]) - 96 answer = 0 for i in range(num): answer += (list_str[i] * (31 ** i)) print(answer % 1234567891)
ord()
の使い方について分かるようになった。
https://www.acmicpc.net/problem/10814
num = int(input()) answer_list = [] for i in range(num): a, b = input().split() a = int(a) answer_list.append((a,b)) answer_list.sort(key=lambda x: x[0]) for i in range(num): print(answer_list[i][0], answer_list[i][1])
.sort(key =)
を設定することでリストの要素別にソードできることが分かった。 また、lambda x: ~
を設定することでdef
を使わず、関数を使用することができることが分かった。
https://www.acmicpc.net/problem/11050
import math a , b = map(int, input().split()) c = 1 if b == 0: print("1") else: for i in range(b): c *= a - i print(int(c/math.factorial(b)))
Pythonのmath
にファクトリアル機能があることが分かった。
https://www.acmicpc.net/problem/11651
import sys dot_list = [] num = int(input()) for i in range(num): a, b = map(int, sys.stdin.readline().split()) dot_list.append((a,b)) dot_list.sort(key = lambda x: x[0]) dot_list.sort(key = lambda x: x[1]) for i in range(num): print(dot_list[i][0], dot_list[i][1])
問題2の応用。
1.K-meansクラスタリングに関する考察課題
以下考察
k-meansクラスタリングの結果より、考察を行った。
まず、基準にした点の組み合わせが変化すると、クラスタリングの結果も伴って変化することが分かった。(初期クラスター中心が変化するとクラスタリング結果が違う可能性あり)
次に、基準の点が同じであると、結果も一致することが分かった。(初期クラスター中心が同じだと結果の再現性を有する)
また、k-meansクラスタリングでは、クラスタ結果の点の座標が同じだと、クラスタリング結果も一致することが分かった。
例えば、結果の[0, 1, [[2.39, 4.16], [7.32, 7.18]]]の場合と[11, 17, [[2.39, 4.16], [7.32, 7.18]]]は最初に基準にした点は各々(0,1), (11,17)であるが、結果は同じで、クラスタリングされた点の集合も同じだった。
これより、クラスタリングの結果として出る点の組合を出力すると
- (2.536, 4.436) , (7.689, 7.178)
- (3.625, 7.15) , (5.675, 4.683)
- (7.689, 7.178) , (2.536, 4.436)
- (2.39, 4.16) , (7.32, 7.18)
- (7.32, 7.18) , (2.39, 4.16)
で5通りがあった。
しかし、
よって、今回の考察では5つのクラスタリングの結果を以下の3つの通りとして結果を扱う。
- (2.536, 4.436) , (7.689, 7.178)
- (3.625, 7.15) , (5.675, 4.683)
- (7.689, 7.178) , (2.536, 4.436)
- (2.39, 4.16) , (7.32, 7.18)
- (7.32, 7.18) , (2.39, 4.16)
クラスタリング結果の頻度を出力すると
[68, 2, 22, 53, 45]より
で主に2つのパータンになることがわかる。
パータン1.の場合は
[0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 15] [5, 6, 7, 8, 9, 16, 17, 18, 19] パータン3.の場合は
[0, 1, 2, 3, 10, 11, 12, 13, 14, 15] [4, 5, 6, 7, 8, 9, 16, 17, 18, 19] これより、クラスタリング結果は変わったが、kが同じであると、有意だと考えるくらいな差はないと思う。(個人的な見解)
パータン2.の場合は
[0, 1, 2, 3, 4, 5, 6, 7] [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 上述したパータン2は初期クラスター中心の点が(1, 13) , (3, 15)であるとパータン2の結果が導出されるが、検証のため、その点の座標を再現性確認用コード(chat gpt使用)に代入し、実行すると(3, 15)の場合がパータン3と同じ結果が導出された。
これは、自分がコードを作成する際に、クラスタリングを行った後のクラスター中心の距離がその一段階前の点とのx, y座標の距離が0.1未満であるとクラスタリングをやめるように設定したためだど考え、点別に何回def cluster_once()を行ったかを調べた。
[229, 4, 96, 194, 195]より
まず、問題のパータン2では、(1, 13)が2回(3, 15)が2回クラスタリングを行ったため、クラスタリングの回数が少ないことが分かった。
よって、(3,15)の場合は単に
クラスタリングを行った後のクラスター中心の距離がその一段階前の点とのx, y座標の距離が0.1未満であるとクラスタリングをやめる
ことから問題が生じたと考え、クラスタリングをやめる距離の差を0.00000001未満まで下げてみてが、クラスタリングの回数には変化なしで結果も変化しなかったため、いまだにその理由は不明である。
kクラスタリングの短所
kクラスタリングはクラスタの点の座標の中心を基準にするため、線状のデータをクラスタリングするにはよくないと考えた。
また、半径が違う二つの円の関しても内側と外側として分けることは難しいと考えた。(距離の平均で計算するため)
kの設定
また、kの数を設定できるようにコードを組んだため、様々なkの数でクラスタリングを試した。
無駄にkを増やしてみると、データの分類があいまいになることが分かった。
よって、kを決める際にはどの目的で、どのように要素を分類したいかを確実にすることが必要であると考えた。
特に、データが専門的な情報を要する時(化学分子データ、金融データ)はそのデータをよく理解している(因果関係やデータの傾向が生じる要因を分かる人)人と十分相談してから決めることも良いと考えた。
最後に、kの数を6に設定した結果を下に示す(再現性確認用コード(chat gpt使用)から変形した)
2.競技プログラミング練習(3つ)
https://www.acmicpc.net/problem/2920
答えのコードを下に示す
num = list(map(int,input().split())) ascending_list = [1, 2, 3, 4, 5, 6, 7, 8] descending_list = [ 8, 7, 6, 5, 4, 3, 2, 1] if num == ascending_list: print("ascending") elif num == descending_list: print("descending") else: print("mixed")
https://www.acmicpc.net/problem/16212
import sys num = int(input()) num_list = list(map(int,sys.stdin.readline().split())) num_list.sort() for i in num_list: print(i, end = ' ')
https://www.acmicpc.net/problem/14916
import math num = int(input()) num_list = [0] + [math.inf] * (num)
i = 1 while (5 * i) < len(num_list): num_list[5 * i] = i i += 1 for k in range (num - 1): num_list[k + 2] = min(num_list[k + 2], num_list[k] + 1) if num_list[num] != math.inf: print(num_list[num]) else: print(-1)
プログラミング問題2つ
答えのコードは
def find(k): n = 1 if k == 1: return 1 else: while k > n * (n + 1)/2: n += 1 return n num = int(input()) d =int( find(num) * (find(num) + 1) / 2 - num) e = find(num)
if e%2 == 0: print("{}/{}".format(e - d,1 + d)) else: print("{}/{}".format(1 + d,e - d))
答えのコードは
a = int(input()) b = int(input()) c = int(input())
num = a * b * c num_list = list(map(int, str(num))) for i in range(10): print(num_list.count(i))
化学系から情報系へ進学するまでのタイムライン
2021年 韓国から日本の大学へ入学(化学系)
一回生(2021年)
前期はコロナのため家で引きこもったままゲームしてた。
後期からは貯金がなくなる、周りがバイト、授業、サークルなど色々頑張ることから影響をもらいコンビニ夜勤を始まる
二回生(2022年)
コンビニ夜勤をやめて韓国から日本へ留学を準備する学生の家庭教師バイトをし始めた。
2回生になってから日本語能力にもだんだん自信を持ち始め、2022年末にある日韓通訳バイトを始めてトライしてから単発の通訳バイトもし始めた。
三回生(2023年)
理系の韓国留学生は少ないが、B2Bの通訳は大体理系の学生希望であったため、日韓メーカー間のビジネス通訳をし始めた。
お陰で、様々な業界の仕事に接することができ、自分が好きな仕事について考え始めてた。
化学が嫌いになったことではないが、IT業界の仕事と雰囲気、自分の好みなどが気に入り、大学院から情報系に行くことを決め、TOEICを受けた(795点)。
また、情報系の大学院入試科目が化学と違うため、その基礎である数学から勉強をし始めた。
四回生(2024年)
研究室に配属された(コアタイム 9:30 ~ 17:30)。
平日毎日17時30分までは卒業研究のための演習実験、研究室の雑用などで忙しくなったため、毎日夜22時から午前2時に大学院進学のための勉強をしてた。(きつかった)
全く関連のない分野の研究と勉強を並行したため、大変だったが、無事に行きたい研究室に合格した。
現在
院試のため、数学や専門科目に関しては勉強してたが、実際コードを作る経験(実技)が少なかった。(アルゴリズムの問題はマーク式だったため、解けるが自分では書けない)
また、勉強した知識が実際どう使えるかについてはわからなかった。(情報理論のエントロピーや新語処理のフーリエ変換の計算は出来るが、どこに使えるかについてはわからない)
上述した理由で、勉強する必要性を感じて現在(24.9月末~)プログラミング練習をしてる。
今後の予定