競技プログラミングにハマるプログラマのスレ 46

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2021/04/06(火) 20:44:06.98
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.gi...hub.io/AtCoderClans/

※前スレ
競技プログラミングにハマるプログラマのスレ 45
https://medaka.5ch.net/test/read.cgi/prog/1614891774/
2021/04/18(日) 13:52:17.13
最大マッチング問題2とかいう名前がついてそう
2021/04/18(日) 13:54:25.24
実際最大マッチングの一般化になってるのか
2021/04/18(日) 13:54:29.79
>>424
わりと好き
2021/04/18(日) 13:55:02.03
じゃあ問題名はBeyond Tinderで
433仕様書無しさん
垢版 |
2021/04/18(日) 13:57:07.72
>>428
ただの貪欲じゃん
2021/04/18(日) 13:57:43.83
AtCoderがマッチング業界に殴り込みをかける布石だね
2021/04/18(日) 13:58:36.31
>>430
全然なってないな
アホすぎた
2021/04/18(日) 13:59:06.69
女は下方婚しないからな
2021/04/18(日) 14:01:11.79
けんちゃんは確かにレートは低いけど心理学に詳しいから
2021/04/18(日) 14:02:08.05
ある辺に流せる容量を自由に設定できるんなら一般化だけど違う
2021/04/18(日) 14:03:15.82
人の能力はある一次元ベクトルになってて、報酬は結婚した男女の内積ってことにしたらちょっとは問題っぽくなるんじゃね？
2021/04/18(日) 14:05:26.16
レート低いって言うけどお前らよりは高いだろ
2021/04/18(日) 14:05:44.03
>>419
黄色いのは疲れよりも
水分不足の可能性の方が高いぞ

これからの時期でも暖かい飲み物で水分補給しろ
442仕様書無しさん
垢版 |
2021/04/18(日) 14:06:15.60
とはいえ最近のレート下降傾向がなあ
443仕様書無しさん
垢版 |
2021/04/18(日) 14:06:17.13
内積の和の最大化
何
制約大きくできんの？
2021/04/18(日) 14:07:04.23
https://manabitimes.jp/math/632
並び替え不等式って知ってるか？
2021/04/18(日) 14:07:52.88
>>440
思わず確認しちゃったじゃないか

頑張りが報われたのかと思ったのに
近頃下降してて悲しい
446仕様書無しさん
垢版 |
2021/04/18(日) 14:13:48.04
>>444
普通に知らなかった
降順ソート列の貪欲でいけるってことか？
やべー自明に見えねえわ
2021/04/18(日) 14:16:34.97
これAtCoderでも既出だよね？
どっかで使った記憶ある
2021/04/18(日) 14:16:53.56
並び替えのやつABC-C,Dくらいじゃないか
大小合わないやつは入れ替えても損しないので
449仕様書無しさん
垢版 |
2021/04/18(日) 14:17:45.49
いや内積だからソートしたらだめじゃん
2021/04/18(日) 14:19:47.80
元々の問題は並べ替え不等式という話してるんじゃね
ベクトルはそれこそフローとか使うのがいいんだろうか
2021/04/18(日) 14:20:39.54
のいみたんかわいいのん！
2021/04/18(日) 14:23:59.46
アルゴの話するのやめろ
453仕様書無しさん
垢版 |
2021/04/18(日) 14:25:28.76
>>439よく見たら一次元ベクトルで草
二次元以上だと普通に難しくね？
2021/04/18(日) 14:27:45.62
すまん、一次元じゃなくてM次元の間違いだわ
2021/04/18(日) 14:29:36.92
列ベクトル一次元っぽいからね
2021/04/18(日) 14:30:43.83
多分配列の次元との混同だな
457仕様書無しさん
垢版 |
2021/04/18(日) 14:32:52.12
一階テンソルという気持ちで一次元ベクトルと言いたくなるのは少しわかる
2021/04/18(日) 14:33:53.57
配列のことvectorと読んでる某言語があるので実は間違ってない
2021/04/18(日) 14:36:21.29
ベクターって固有名詞がありすぎるせいでベクトルと別の物としか考えられない
460仕様書無しさん
垢版 |
2021/04/18(日) 14:38:16.77
結局>>439はmax(N, M)N^2か？
2021/04/18(日) 15:21:34.88
一次元ベクトルに無限にツッコミが入るのに計算量の話で流れ止まるの草

と思ったらtwitterでめっちゃ言及されてて草
赤コーダーが最大マッチングから改善できないっていうならそうなんだろうか
2021/04/18(日) 15:28:16.03
439 自体はソート+貪欲で終わり
２次元ベクトルの内積はシラネ
内積に何かいい性質あったっけ
463仕様書無しさん
垢版 |
2021/04/18(日) 15:33:41.32
逆にどういう性質があったら改善するんだろうか
なんか面白そうな問題作れそう
2021/04/18(日) 15:46:18.00
このスレは水色以下ばっかなんだから最大マッチングなんてわかるわけないだろ
2021/04/18(日) 16:02:00.75
ダメだお金が一瞬にして飛んだ
俺の明日からの生活費どころか今月のクレカ請求すらもうない
死ぬしかないかも
466仕様書無しさん
垢版 |
2021/04/18(日) 16:10:40.62
しねば？
2021/04/18(日) 16:11:58.85
生活保護を受けながら競プロして生きるのも悪くないと思う
2021/04/18(日) 16:12:45.15
>>466
よくそんな事を軽々しく言えるな
お前が死ねボケ
2021/04/18(日) 16:13:54.01
>>465
こういう人生底辺競プロer見ると本当に安心する
2021/04/18(日) 16:21:25.50
下を見て安心してると引き摺り込まれるから注意
2021/04/18(日) 16:22:52.75
お金に困ってて1時間いくらでマンツーマンで競プロ教えますみたいな
サービスやる人いたら教わってみたいけど
教えられるほど強い人は高学歴で家庭教師とかのほうが割がいいから
やる人いないって感じなのかな
2021/04/18(日) 16:26:48.67
難しい問題の話になると流れ止まって、ゴミカス底辺が出てくると流れが加速するって
お前らほんとに灰コーダーなんだな
2021/04/18(日) 16:27:11.88
当たり前だろいまさら何言ってるんだ
2021/04/18(日) 16:29:07.05
難しい問題の話はTwitterでやれよってなるからね
475仕様書無しさん
垢版 |
2021/04/18(日) 16:29:22.82
灰コーダーなら死んでもいいや
2021/04/18(日) 16:29:31.26
灰1割
茶3割
緑2割
水2割
青1割
暖色1割
ぐらいの割合とみた
2021/04/18(日) 16:30:53.34
ここに居座るくらいだから一年以上続けてるやつ多いと思ってるんだけど、どうなんだろう
478仕様書無しさん
垢版 |
2021/04/18(日) 16:33:04.04
難しいどころか最大マッチングすらおそらく一人しか言及してないのがこのスレのレベルなのでは？
2021/04/18(日) 16:35:26.00
旧帝理系ぐらいの人が1年間そこそこの時間割いて取り組んだら大体水色あたりになりそう
2021/04/18(日) 16:36:32.24
自明な最大マッチング解に対する言及で何が分かるのか
481仕様書無しさん
垢版 |
2021/04/18(日) 16:38:13.93
何回も言うけどここは暖色未満お断りなんで
底辺の話はtwitterでやってください
2021/04/18(日) 16:40:10.86
つーかお前らマジのマジで黄色未満なの？
競プロスレに書き込むほどの熱意があるのに黄色にもなれないってどういうことなん？
教えて
483仕様書無しさん
垢版 |
2021/04/18(日) 16:41:39.82
教プロスレに書き込むほどには熱意がない
熱意があったら精進するし
2021/04/18(日) 16:44:18.21
問題解いた後の息抜きタイムで書き込みにきてるんじゃないのか…
趣味にすら本気になれずにグダグダ5chってしょーもない人生だな
2021/04/18(日) 16:47:42.76
息抜きタイムなんて設けてる時点で本気さが足りない
ほら精進してこい
2021/04/18(日) 16:50:27.75
原因不明で1個だけ通らなくてWAになる苛立ちをぶつけにくるのがここ
487仕様書無しさん
垢版 |
2021/04/18(日) 16:51:49.78
>>485
馬鹿の考える精進で草
ハチマキ巻いて徹夜してそう
2021/04/18(日) 16:55:22.80
それってあなたの感想ですよねｗ
2021/04/18(日) 16:57:07.59
出たーーーーひろゆき仕草w
490仕様書無しさん
垢版 |
2021/04/18(日) 16:57:47.02
暖色未満は書き込むなよ
2021/04/18(日) 17:05:11.02
最大マッチングから改善できないから書くことなかったというだけでその意味で別にこのスレに低めのレート上限を与える情報でもないのでは？
最大マッチングすら話題に上らないんならおいおいという感じだが
492仕様書無しさん
垢版 |
2021/04/18(日) 17:12:14.37
そもそものいみが言及するほどの問題とは思わなかったが
単に無理筋の設定だから見慣れないってだけなのかな
493仕様書無しさん
垢版 |
2021/04/18(日) 17:17:44.57
>>490
将来暖色になるだろう意識高い子たちに
じゃんじゃん書き込んで貰わなくっちゃ
2021/04/18(日) 17:20:53.01
問題設定自体はシンプルで面白い方だと思う
2021/04/18(日) 17:21:13.17
じゃあこれ教えて

数列a_1,a_2,…,a_nがある
以下の2種類のクエリを処理せよ
・1 l r: 区間[l,r]内のa_iに2^(i-l)を加算
・2 l r: 区間[l,r]の要素の和を出力

サンプル
入力
4
1 3 5 7
1 1 4
2 1 3
1 3 4
2 3 4

出力
16
27
2021/04/18(日) 17:24:09.04
>>495
遅延評価セグ木で普通に出来そう
2021/04/18(日) 17:24:19.83
FEのアルゴリズムとか解けるん？
2021/04/18(日) 17:25:54.70
>>496
遅延セグ木の使い方わかってない…
何を載せるの？
2021/04/18(日) 17:33:12.04
>>498
nodeの方は普通に区間の総和で
遅延評価の方は2^(i-l)が足されるから、2^-lの総和を持っておけば、そいつに区間を[a,b)とした時の2^b-2^aをかけた奴をnodeに足してOK
2021/04/18(日) 17:34:09.38
区間の和と区間の左端と右端を保持して、作用素はlかな
501仕様書無しさん
垢版 |
2021/04/18(日) 17:37:19.84
遅延セグ苦手だから平方分割したくなっちゃうなこういうの
2021/04/18(日) 17:39:35.82
中日よっわw
2021/04/18(日) 17:53:17.71
んーなるほど
なんとなく載せるべき情報が多くないから行けるっぽいオーラがあることはわかった、ありがとう
ちゃんと理解しなきゃなー
2021/04/18(日) 18:03:19.85
>>495
この程度のザ・典型をこのスレでわざわざ質問するな低能馬鹿糞野郎
2021/04/18(日) 18:07:25.43
でもtwitterは文字制限がキツイんだよな
506仕様書無しさん
垢版 |
2021/04/18(日) 18:11:34.15
青diffくらいはありそうだしいいよ
むしろもっとこういうのを投げるなら暖色未満でもウェルカムだわ
2021/04/18(日) 18:18:24.04
遅延セグ木に乗るか？
いや乗らないなんてことはないと思うけど詰め具合は青じゃ足りんと思うわ
2021/04/18(日) 18:27:06.01
落ち着いたら乗ったわ
2021/04/18(日) 18:41:36.66
まさに羅刹王の悲嘆
2021/04/18(日) 18:45:42.93
一般的な慣用句っぽい雰囲気で難しい表現使うのやめてください
2021/04/18(日) 19:12:35.45
人工無能に注文つけても意味ないだろ
2021/04/18(日) 19:13:34.35
告知メール今頃来とるやん
2021/04/18(日) 19:18:12.30
atcoderやる気なさすぎだろwww
2021/04/18(日) 19:20:08.33
告知メールが遅いと遅刻しちゃうよね(激ウマギャグ)
2021/04/18(日) 19:23:49.69
寒色叱るな　来た道だもの
暖色笑うな　ゆく道だもの
来た道　ゆく道　二人旅
これから通る　今日の道
通り直しのできぬ道
2021/04/18(日) 19:41:41.49
日曜の夜はいつも飲んでいる
2021/04/18(日) 20:04:12.13
日曜の夜、まさに飲酒ゴールデンタイムに競プロとかしてる暇ない
2021/04/18(日) 20:08:34.10
AtCoder飲み会ゲーム
ゲームしたあとAtCoderレートの低い方が飲む
2021/04/18(日) 20:12:47.54
それだと飲みたいがために負けるまである
2021/04/18(日) 20:16:26.39
ゼロ完太陽でも一回じゃそんなに下がらないから一晩でどうこうできるものじゃなさそう
2021/04/18(日) 20:22:11.77
競プロerですら普通に酒飲む文化あるのもったいないなあ
2021/04/18(日) 20:28:00.73
飲む機会があるなら飲まない方がもったいなくね
2021/04/18(日) 20:31:35.42
アルコール無理勢だが
適度に飲んでストレス解消してるほうがレートも高くなるんかな
2021/04/18(日) 20:32:32.31
飲酒ratedしろよ楽しいぞ
2021/04/18(日) 20:34:20.42
別に飲酒が競プロに役に立つとは全く思わないけど、役に立つとかそういうもんじゃないからな、趣味嗜好は
2021/04/18(日) 20:41:11.42
お酒を飲むとお酒を飲んで以降の時間に勉強出来なくなるからイベント毎が無いとお酒飲もうと思えない
なお勉強するとは言ってない
527仕様書無しさん
垢版 |
2021/04/18(日) 20:44:26.21
500点問題作れよなんで600が2問なんだヾ(。｀Д´。)ノ
2021/04/18(日) 20:45:47.97
青水には厳しいコンテストっぽそうだから今回はパスだな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況