結果
| 問題 | No.648 お や す み |
| ユーザー |
 Yuki_Utaai
|
| 提出日時 | 2018-05-27 23:57:50 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,995 bytes |
| コンパイル時間 | 146 ms |
| コンパイル使用メモリ | 12,800 KB |
| 実行使用メモリ | 18,720 KB |
| 最終ジャッジ日時 | 2024-06-30 07:27:50 |
| 合計ジャッジ時間 | 3,903 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
18,720 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
ソースコード
import random
#--------粒 子 群 最 適 化------------------------------
#評価関数:
def criterion(x, y):
z=-abs(k-(x*(x+1))/2)
if x<0:
z=-10000000000
return z
#粒子の位置の更新を行う関数
def update_position(x, y, vx, vy):
new_x = x + vx
new_y = y + vy
return new_x, new_y
#粒子の速度の更新を行う関数
def update_velocity(x, y, vx, vy, p, g, w=1, ro_max=1,v_max=100):
#パラメーターroはランダムに与える
ro1 = random.uniform(0, ro_max)
ro2 = random.uniform(0, ro_max)
#粒子速度の更新を行う
new_vx = int(w * vx + ro1 * (p[0] - x) + ro2 * (g[0] - x))
if abs(new_vx)>v_max:
new_vx=int(v_max*new_vx/abs(new_vx))
new_vy = w * vy + ro1 * (p[1] - y) + ro2 * (g[1] - y)
return new_vx, new_vy
def main():
N = 1000 #粒子の数
x_min, x_max = 0, k
y_min, y_max = 0, 0
#粒子位置, 速度, パーソナルベスト, グローバルベストの初期化を行う
ps = [[random.randint(x_min, x_max), random.uniform(y_min, y_max)] for i in range(N)]
vs = [[0.0, 0.0] for i in range(N)]
personal_best_positions = list(ps)
personal_best_scores = [criterion(p[0], p[1]) for p in ps]
best_particle = personal_best_scores.index(max(personal_best_scores))
global_best_position = personal_best_positions[best_particle]
T = 600 #世代数(ループの回数)
for t in range(T):
for n in range(N):
x, y = ps[n][0], ps[n][1]
vx, vy = vs[n][0], vs[n][1]
p = personal_best_positions[n]
#粒子の位置の更新を行う
new_x, new_y = update_position(x, y, vx, vy)
ps[n] = [new_x, new_y]
#粒子の速度の更新を行う
new_vx, new_vy = update_velocity(new_x, new_y, vx, vy, p, global_best_position)
vs[n] = [new_vx, new_vy]
#評価値を求め, パーソナルベストの更新を行う
score = criterion(new_x, new_y)
if score > personal_best_scores[n]:
personal_best_scores[n] = score
personal_best_positions[n] = [new_x, new_y]
#グローバルベストの更新を行う
best_particle = personal_best_scores.index(max(personal_best_scores))
global_best_position = personal_best_positions[best_particle]
if k==(global_best_position[0]*(global_best_position[0]+1))//2:
print("YES")
print(int(global_best_position[0]))
exit()
#最適解
# print(max(personal_best_scores), global_best_position)
return max(personal_best_scores), global_best_position[0], global_best_position[1]
#--------------------------------------------------------------
k=int(input())
best=-100000000000000
xx=0
yy=0
for i in range(3):
kouho_best, kouho_x, kouho_y=main()
if best>kouho_best:
best=kouho_best
xx=kouho_x
yy=kouho_y
print("NO")