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

**仕様書無しさん** · 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(日) 14:05:44.03

>>419
黄色いのは疲れよりも
水分不足の可能性の方が高いぞ

これからの時期でも暖かい飲み物で水分補給しろ

**仕様書無しさん** · 2021/04/18(日) 14:06:15.60

とはいえ最近のレート下降傾向がなあ

**仕様書無しさん** · 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
思わず確認しちゃったじゃないか

頑張りが報われたのかと思ったのに
近頃下降してて悲しい

**仕様書無しさん** · 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くらいじゃないか
大小合わないやつは入れ替えても損しないので

**仕様書無しさん** · 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

アルゴの話するのやめろ

**仕様書無しさん** · 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

多分配列の次元との混同だな

**仕様書無しさん** · 2021/04/18(日) 14:32:52.12

一階テンソルという気持ちで一次元ベクトルと言いたくなるのは少しわかる

**仕様書無しさん** · 2021/04/18(日) 14:33:53.57

配列のことvectorと読んでる某言語があるので実は間違ってない

**仕様書無しさん** · 2021/04/18(日) 14:36:21.29

ベクターって固有名詞がありすぎるせいでベクトルと別の物としか考えられない

**仕様書無しさん** · 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 自体はソート+貪欲で終わり
２次元ベクトルの内積はシラネ
内積に何かいい性質あったっけ

**仕様書無しさん** · 2021/04/18(日) 15:33:41.32

逆にどういう性質があったら改善するんだろうか
なんか面白そうな問題作れそう

**仕様書無しさん** · 2021/04/18(日) 15:46:18.00

このスレは水色以下ばっかなんだから最大マッチングなんてわかるわけないだろ

**仕様書無しさん** · 2021/04/18(日) 16:02:00.75

ダメだお金が一瞬にして飛んだ
俺の明日からの生活費どころか今月のクレカ請求すらもうない
死ぬしかないかも

**仕様書無しさん** · 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でやれよってなるからね

**仕様書無しさん** · 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

ここに居座るくらいだから一年以上続けてるやつ多いと思ってるんだけど、どうなんだろう

**仕様書無しさん** · 2021/04/18(日) 16:33:04.04

難しいどころか最大マッチングすらおそらく一人しか言及してないのがこのスレのレベルなのでは？

**仕様書無しさん** · 2021/04/18(日) 16:35:26.00

旧帝理系ぐらいの人が1年間そこそこの時間割いて取り組んだら大体水色あたりになりそう

**仕様書無しさん** · 2021/04/18(日) 16:36:32.24

自明な最大マッチング解に対する言及で何が分かるのか

**仕様書無しさん** · 2021/04/18(日) 16:38:13.93

何回も言うけどここは暖色未満お断りなんで
底辺の話はtwitterでやってください

**仕様書無しさん** · 2021/04/18(日) 16:40:10.86

つーかお前らマジのマジで黄色未満なの？
競プロスレに書き込むほどの熱意があるのに黄色にもなれないってどういうことなん？
教えて

**仕様書無しさん** · 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になる苛立ちをぶつけにくるのがここ

**仕様書無しさん** · 2021/04/18(日) 16:51:49.78

>>485
馬鹿の考える精進で草
ハチマキ巻いて徹夜してそう

**仕様書無しさん** · 2021/04/18(日) 16:55:22.80

それってあなたの感想ですよねｗ

**仕様書無しさん** · 2021/04/18(日) 16:57:07.59

出たーーーーひろゆき仕草w

**仕様書無しさん** · 2021/04/18(日) 16:57:47.02

暖色未満は書き込むなよ

**仕様書無しさん** · 2021/04/18(日) 17:05:11.02

最大マッチングから改善できないから書くことなかったというだけでその意味で別にこのスレに低めのレート上限を与える情報でもないのでは？
最大マッチングすら話題に上らないんならおいおいという感じだが

**仕様書無しさん** · 2021/04/18(日) 17:12:14.37

そもそものいみが言及するほどの問題とは思わなかったが
単に無理筋の設定だから見慣れないってだけなのかな

**仕様書無しさん** · 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かな

**仕様書無しさん** · 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は文字制限がキツイんだよな

**仕様書無しさん** · 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

お酒を飲むとお酒を飲んで以降の時間に勉強出来なくなるからイベント毎が無いとお酒飲もうと思えない
なお勉強するとは言ってない

**仕様書無しさん** · 2021/04/18(日) 20:44:26.21

500点問題作れよなんで600が2問なんだヾ(。｀Д´。)ノ

**仕様書無しさん** · 2021/04/18(日) 20:45:47.97

青水には厳しいコンテストっぽそうだから今回はパスだな

**仕様書無しさん** · 2021/04/18(日) 20:46:21.88

nosubします

**仕様書無しさん** · 2021/04/18(日) 20:46:42.76

どうせ自発的に有意義なことはできんからコンテストは出る

**仕様書無しさん** · 2021/04/18(日) 20:47:02.43

おいARCまで精神統一するつもりだったのにこのスレみちまったじゃねえか
レート下がったら責任取ってくれんのか？

**仕様書無しさん** · 2021/04/18(日) 20:47:50.37

男ならno register

**仕様書無しさん** · 2021/04/18(日) 20:52:58.11

600どちらかは取れないと青パフォ出ないだろうな

**仕様書無しさん** · 2021/04/18(日) 20:53:38.12

200点刻みなのはいいけどダイクストラするだけ見たいな問題だったら許さん

**仕様書無しさん** · 2021/04/18(日) 20:57:27.98

全完すれば配点とか意味ないしどうでもいいわ

**仕様書無しさん** · 2021/04/18(日) 21:00:54.43

撤退します

**仕様書無しさん** · 2021/04/18(日) 21:12:43.25

じゃあな

**仕様書無しさん** · 2021/04/18(日) 21:30:18.62

こうして5chに戻ってくるのだった(完)

**仕様書無しさん** · 2021/04/18(日) 21:32:19.79

半分くらいは当たるんだけどな

**仕様書無しさん** · 2021/04/18(日) 22:23:33.46

もうﾑﾘ・・・酒のんじゃおｗ