競技プログラミング総合スレ 64

2022/10/02(日) 17:43:58.66

↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2022/10/02(日) 17:48:55.39

あ、すまん、うっかりテンプレのコマンド部分消してしまったわ
>>950
次スレ立てるときは次のレスのテンプレからコピペしてくれ

2022/10/02(日) 17:55:37.59

コマンド先頭に書こうとしたら弾かれるわ
!extend:checked:vvvvv:1000:512
要は>>950はこれを先頭に２行つけてな
ワッチョイ表示用コマンド、詳細とかはググってくれ

2022/10/02(日) 18:53:41.67

フレームワーク使っていい競技？

2022/10/02(日) 19:35:57.30

数学っぽい問題を解くために一からアルゴリズムのコード書いていくタイプの競技だから、あんまフレームワークを活用できる機会ないかも

2022/10/02(日) 21:00:40.58

そうじゃない
そこはフレームワークなんて使うわけないだろ馬鹿
とか罵るところだろ

2022/10/02(日) 22:11:28.18

どんなフレームワークを使うつもりだったのか聞きたい

2022/10/03(月) 00:08:34.99

業プロの人ってフレームワークとかそういうフワフワした言葉大好きだよね

2022/10/03(月) 01:46:07.58

AtCoderのWebサイトは何のフレームワークで実装されてるんだろう

2022/10/03(月) 04:01:38.80

ここに書いてある

レールは続く】 Ruby on Rails Part21 【これからも
https://medaka.5ch.net/test/read.cgi/php/1545146635/103

Rails 製、「爆速すぎて笑う」　表示速度が“異常な”Webサイト「dev.to」　その仕組みは？

BuiltWith で、サイトが使っている技術を調べる

2022/10/05(水) 20:15:07.12

算数パズルにフレームワーク

2022/10/06(木) 04:14:49.38

ライブラリとフレームワークの違いもよくわからんしな

2022/10/06(木) 12:52:23.39

同じdiffでもABCかARCかAGCか、前の方に置かれたか後ろの方に置かれたか、いつごろコンテストが行われたかでだいぶ難易度変わるよな
なんかいい感じの補正できないか

2022/10/06(木) 13:07:07.83

この深層強化学習で行列積アルゴリズムを改善したというnature論文かなり注目されているな
chokudaiもRTしてたし
NNの重み埋め込んで使えば競プロでもウハウハじゃね？って思ったけど、10%とか20%の改善で競プロで劇的に役立つほどの改善じゃなさそう
とはいえ、深層学習とかも中身は結構行列演算だし、人類に相当貢献するアルゴっぽい
https://www.nature.com/articles/s41586-022-05172-4

2022/10/06(木) 14:08:36.03

この論文が特にすごいのは、発見した行列積アルゴリズムそのものよりも、AlphaZeroのやり方で優秀なアルゴリズムも発見できる、ということだけどな

2022/10/07(金) 08:03:59.07

ある工事完了に必要な作業1～6について以下の制約がある。
作業2は作業1が終わるまで開始できない。
作業3は作業1が終わるまで開始できない。
作業4は作業2と3が終わるまで開始できない。
作業5は作業3が終わるまで開始できない。
作業6は作業4と5が終わるまで開始できない。
この工事はT日以内で終えねばならず、各作業iはt_i日かかる。
しかし臨時作業員を雇うことにより作業日数を減らすことができるが、
s_i日よりは少なくはできない。また、1日減らすのにm_i万円かかる。
費用を最小にする作業計画をたてよ。

minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
x_1 + x_2 + x_4 + x_6 ≦ T
x_1 + x_3 + x_4 + x_6 ≦ T
x_1 + x_3 + x_5 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

模範解答では各作業の開始日y_iという変数も考えています。
上の解答は間違っていますか？

2022/10/07(金) 09:38:43.05

合ってると思うぞ
全パスを列挙する必要があるから制約の数が指数オーダーになるが

2022/10/07(金) 10:02:47.32

>>17
ありがとうございました。念のため本に書いてある模範解答を以下に書きます。
minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
y_1 = 0
y_1 + x_1 ≦ y_2
y_1 + x_1 ≦ y_3
y_2 + x_2 ≦ y_4
y_3 + x_3 ≦ y_4
y_3 + x_3 ≦ y_5
y_4 + x_4 ≦ y_6
y_5 + x_5 ≦ y_6
y_6 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)