結果
問題 | No.648 お や す み |
ユーザー | Yuki_Utaai |
提出日時 | 2018-05-28 23:10:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 535 ms / 2,000 ms |
コード長 | 2,715 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 86,848 KB |
実行使用メモリ | 80,384 KB |
最終ジャッジ日時 | 2023-10-11 22:43:33 |
合計ジャッジ時間 | 34,082 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 107 ms
77,288 KB |
testcase_01 | AC | 337 ms
78,932 KB |
testcase_02 | AC | 105 ms
77,416 KB |
testcase_03 | AC | 441 ms
79,212 KB |
testcase_04 | AC | 423 ms
79,088 KB |
testcase_05 | AC | 105 ms
77,192 KB |
testcase_06 | AC | 467 ms
79,272 KB |
testcase_07 | AC | 475 ms
79,372 KB |
testcase_08 | AC | 491 ms
79,540 KB |
testcase_09 | AC | 104 ms
77,192 KB |
testcase_10 | AC | 492 ms
79,720 KB |
testcase_11 | AC | 486 ms
79,232 KB |
testcase_12 | AC | 489 ms
79,384 KB |
testcase_13 | AC | 498 ms
79,532 KB |
testcase_14 | AC | 502 ms
79,452 KB |
testcase_15 | AC | 505 ms
79,356 KB |
testcase_16 | AC | 505 ms
79,444 KB |
testcase_17 | AC | 478 ms
79,704 KB |
testcase_18 | AC | 511 ms
79,360 KB |
testcase_19 | AC | 491 ms
79,340 KB |
testcase_20 | AC | 133 ms
77,812 KB |
testcase_21 | AC | 137 ms
78,200 KB |
testcase_22 | AC | 136 ms
78,016 KB |
testcase_23 | AC | 143 ms
78,816 KB |
testcase_24 | AC | 139 ms
77,920 KB |
testcase_25 | AC | 135 ms
78,300 KB |
testcase_26 | AC | 138 ms
78,384 KB |
testcase_27 | AC | 140 ms
78,264 KB |
testcase_28 | AC | 134 ms
78,368 KB |
testcase_29 | AC | 131 ms
78,016 KB |
testcase_30 | AC | 516 ms
79,084 KB |
testcase_31 | AC | 514 ms
79,268 KB |
testcase_32 | AC | 517 ms
79,332 KB |
testcase_33 | AC | 524 ms
79,396 KB |
testcase_34 | AC | 521 ms
79,740 KB |
testcase_35 | AC | 524 ms
79,044 KB |
testcase_36 | AC | 501 ms
79,340 KB |
testcase_37 | AC | 535 ms
79,268 KB |
testcase_38 | AC | 530 ms
79,476 KB |
testcase_39 | AC | 504 ms
79,596 KB |
testcase_40 | AC | 513 ms
79,756 KB |
testcase_41 | AC | 507 ms
79,152 KB |
testcase_42 | AC | 521 ms
79,768 KB |
testcase_43 | AC | 517 ms
79,600 KB |
testcase_44 | AC | 517 ms
79,392 KB |
testcase_45 | AC | 514 ms
79,480 KB |
testcase_46 | AC | 508 ms
79,404 KB |
testcase_47 | AC | 507 ms
79,560 KB |
testcase_48 | AC | 495 ms
79,744 KB |
testcase_49 | AC | 510 ms
79,460 KB |
testcase_50 | AC | 153 ms
77,952 KB |
testcase_51 | AC | 137 ms
78,008 KB |
testcase_52 | AC | 142 ms
78,240 KB |
testcase_53 | AC | 141 ms
78,016 KB |
testcase_54 | AC | 137 ms
78,128 KB |
testcase_55 | AC | 142 ms
77,924 KB |
testcase_56 | AC | 139 ms
78,108 KB |
testcase_57 | AC | 135 ms
78,220 KB |
testcase_58 | AC | 138 ms
78,032 KB |
testcase_59 | AC | 136 ms
78,156 KB |
testcase_60 | AC | 511 ms
80,040 KB |
testcase_61 | AC | 514 ms
80,384 KB |
testcase_62 | AC | 486 ms
79,872 KB |
testcase_63 | AC | 480 ms
80,052 KB |
testcase_64 | AC | 483 ms
79,868 KB |
testcase_65 | AC | 494 ms
79,548 KB |
testcase_66 | AC | 482 ms
80,256 KB |
testcase_67 | AC | 492 ms
79,920 KB |
testcase_68 | AC | 506 ms
80,236 KB |
testcase_69 | AC | 517 ms
79,660 KB |
testcase_70 | AC | 502 ms
80,020 KB |
testcase_71 | AC | 496 ms
79,956 KB |
testcase_72 | AC | 494 ms
79,708 KB |
testcase_73 | AC | 482 ms
80,172 KB |
testcase_74 | AC | 492 ms
80,152 KB |
testcase_75 | AC | 489 ms
79,992 KB |
testcase_76 | AC | 504 ms
79,800 KB |
testcase_77 | AC | 147 ms
77,928 KB |
testcase_78 | AC | 142 ms
77,916 KB |
testcase_79 | AC | 146 ms
78,384 KB |
testcase_80 | AC | 141 ms
78,196 KB |
testcase_81 | AC | 142 ms
78,192 KB |
testcase_82 | AC | 133 ms
78,028 KB |
testcase_83 | AC | 137 ms
78,328 KB |
ソースコード
import random #--------粒 子 群 最 適 化------------------------------ #評価関数: def criterion(x): z=-abs(k-(x*(x+1))/2) if x<0: z=-10**50 return z #粒子の位置の更新を行う関数 def update_position(x, vx): new_x = x + vx return new_x #粒子の速度の更新を行う関数 def update_velocity(x, vx, p, g, w=0.5, ro_max=1): v_max=k//3 #パラメーターroはランダムに与える ro1 = random.uniform(0, ro_max) ro2 = random.uniform(0, ro_max) #粒子速度の更新を行う new_vx = int(w * vx + ro1 * (p - x) + ro2 * (g - x)) if abs(new_vx)>v_max: new_vx=int(v_max*new_vx/abs(new_vx)) return new_vx def main(): N = 1000 #粒子の数 x_min, x_max = 0, k #粒子位置, 速度, パーソナルベスト, グローバルベストの初期化を行う ps = [random.randint(x_min, x_max) for i in range(N)] vs = [0.0 for i in range(N)] personal_best_positions = list(ps) personal_best_scores = [criterion(p) for p in ps] best_particle = personal_best_scores.index(max(personal_best_scores)) global_best_position = personal_best_positions[best_particle] T = 1000 #世代数(ループの回数) for t in range(T): for n in range(N): x = ps[n] vx= vs[n] p = personal_best_positions[n] #粒子の位置の更新を行う new_x = update_position(x, vx) ps[n] = new_x #粒子の速度の更新を行う new_vx= update_velocity(new_x, vx, p, global_best_position) vs[n] = new_vx #評価値を求め, パーソナルベストの更新を行う score = criterion(new_x) if score > personal_best_scores[n]: personal_best_scores[n] = score personal_best_positions[n] = new_x #グローバルベストの更新を行う best_particle = personal_best_scores.index(max(personal_best_scores)) global_best_position = personal_best_positions[best_particle] if k==int(global_best_position)*(int(global_best_position)+1)//2: print("YES") print(int(global_best_position)) exit() #最適解 # print((int(global_best_position)*(int(global_best_position)+1))//2) # print(max(personal_best_scores), global_best_position) return max(personal_best_scores), global_best_position #-------------------------------------------------------------- k=int(input()) best=-100000000000000 xx=0 for i in range(3): kouho_best, kouho_x=main() if best>kouho_best: best=kouho_best xx=kouho_x print("NO")