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

**仕様書無しさん** · 2024/03/26(火) 23:36:10.62

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

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

前スレ
競技プログラミングにハマるプログラマのスレ 161
https://medaka.5ch.net/test/read.cgi/prog/1709363800/
競技プログラミングにハマるプログラマのスレ 162
https://medaka.5ch.net/test/read.cgi/prog/1709602428/
競技プログラミングにハマるプログラマのスレ 163
https://medaka.5ch.net/test/read.cgi/prog/1709897526/
競技プログラミングにハマるプログラマのスレ 164
https://medaka.5ch.net/test/read.cgi/prog/1710220809/
競技プログラミングにハマるプログラマのスレ 165
https://medaka.5ch.net/test/read.cgi/prog/1710398066/
競技プログラミングにハマるプログラマのスレ 166
https://medaka.5ch.net/test/read.cgi/prog/1710650865/
競技プログラミングにハマるプログラマのスレ 167
https://medaka.5ch.net/test/read.cgi/prog/1710987911/

**仕様書無しさん** · 2024/03/28(木) 19:12:50.36

>>197
原神っぽい

**仕様書無しさん** · 2024/03/28(木) 19:15:52.95

ASD特有のエコラリア+造語症定期

**仕様書無しさん** · 2024/03/28(木) 19:18:03.00

PFNレベルならAGCでも主催できそう

**仕様書無しさん** · 2024/03/28(木) 19:18:17.02

原神を続けましょう

**仕様書無しさん** · 2024/03/28(木) 19:19:54.00

G社は競プロを見限ったけどな

**仕様書無しさん** · 2024/03/28(木) 19:21:06.51

その結果落ちぶれてるのではい

**仕様書無しさん** · 2024/03/28(木) 19:22:46.67

ガイジはグーグルに入れません

**仕様書無しさん** · 2024/03/28(木) 19:22:54.10

時代はMetaよ

**仕様書無しさん** · 2024/03/28(木) 19:33:19.92

宮内庁もインスタグラムにアカウント作った以上
インスタが錦の御旗を持っているからな

**仕様書無しさん** · 2024/03/28(木) 19:38:37.37

飛び級で京大医学部学部生で学会で発表国際化学オリンピックでも銀メダルも取ってるらしい
競プロ始めたら半年で赤色になれる逸材だろう
https://youtu.be/F1pgm2OeK7c?si=qtJ280jnEn21A0UN

**仕様書無しさん** · 2024/03/28(木) 19:43:11.25

希望単価を月額100万円未満にしてる馬鹿は開発するな↓

ストップ詐欺被害

月額100万円未満で契約させられる詐欺が多発してます
月額100万円未満の詐欺は開発しないようにして下さい

1次受注金額 200万円詐欺被害金額 0万円
2次受注金額 160万円詐欺被害金額 40万円
3次受注金額 120万円詐欺被害金額 80万円
4次受注金額 80万円詐欺被害金額 120万円

**仕様書無しさん** · 2024/03/28(木) 19:55:58.76

frnzにARCに出た方がいいか聞くの鬼畜かよ

**仕様書無しさん** · 2024/03/28(木) 20:03:20.39

みんなARCには出ないほうがいいのだ！

**仕様書無しさん** · 2024/03/28(木) 20:24:42.10

>>145
橙の実力があれば解けるはずなんだよなぁ…

**仕様書無しさん** · 2024/03/28(木) 20:30:29.43

>>198
1を根とした根付き木を考えよう
各頂点に LIS(1,v) という値を持たせる
そうすると根(1)は 1、そして自分の値を a, 子の値を b とすると a≦b≦a+1…（条件）

この値を出来るだけ大きくしてみると上界が出来る
構築は？ → 値の大きい順から振る

出来るだけ小さくしてみる（すべて1）と下界が出来る
構築は？ → 深さの大きい順から振る

（条件）を満たすものは構築できる？
→ (番号の大きさ, 深さの大きさ)の辞書順に振れば構築可能
つまり（条件）が必要十分であることもわかる

（つづく）

**仕様書無しさん** · 2024/03/28(木) 20:36:23.35

>>215
ないんだよなぁ...

**仕様書無しさん** · 2024/03/28(木) 20:40:32.93

スレは続くよどこまでも

**仕様書無しさん** · 2024/03/28(木) 20:40:39.34

>>198
∑LIS(1,v)=K になるように、条件を満たしながら頂点に値を振る方法

まずは上界、つまり子の値が必ず (自分の値)+1 になっている場合からスタート
頂点 1 に注目する
1 の子 q について、 qの値が 1 の値)+1 になっているなら、qの部分木が含む頂点すべての値をごっそり 1 減らしても（条件）を満たす
これで（qの部分木サイズ）だけ ∑LIS が減らせる

（qの部分木サイズ）-1 だけ減らしたいときはどうするか？
q 自体は減らさず、qの全部の部分木に対して値を減らせばいい

こんな感じに思うと、子の部分木サイズが（残り減らすべき∑LIS）以下だったら減らす、という貪欲でやっていったら0≦x≦(q の部分木サイズ）の任意のxだけ必ず減らせる

**仕様書無しさん** · 2024/03/28(木) 20:41:35.66

>>211
ここまで頭が良いと競プロとかちょろいだろ

**仕様書無しさん** · 2024/03/28(木) 20:43:29.64

ageカスデアの話が始まるとすぐに構ってもらうために自演するよな　ゴミすぎる

**仕様書無しさん** · 2024/03/28(木) 20:44:50.19

>>216
間違えた構築は
(値の大きさ, 深さの大きさ)の辞書順

**仕様書無しさん** · 2024/03/28(木) 20:45:08.52

頓珍漢な発言と行動原理がわかりやすすぎてな

**仕様書無しさん** · 2024/03/28(木) 20:48:55.59

学部生で学会発表できるやつとか聞いたことないな
ガチの天才パターンか

**仕様書無しさん** · 2024/03/28(木) 20:51:00.02

そんなことよりARC-Dの解説昨日くらいから求められてたのに、>>219でようやく解説されたのがヤバい
デ・アの話を増やさないと

僕ですか？
ABまでしか解けなかったので説明無理ですｗ

**仕様書無しさん** · 2024/03/28(木) 20:51:46.63

>>219
まあコンテスト中は試行錯誤したから
「値をswapしていけばLISを1ずつ減らせるのでは」で失敗
その後頂点にLIS(1,v)を振って挙動を試す（上界下界はここでわかった）
その後構築方法より先に ∑LIS を K にする方法を思いつく（swapで構築はかなりやりづらかったから、全部のLIS(1,v)を決めれば構築方法があるのではという直感があった）

**仕様書無しさん** · 2024/03/28(木) 20:53:03.28

だって即解説すると特定班みたいなやつが沸いてくるし…

**仕様書無しさん** · 2024/03/28(木) 21:14:47.08

前回のARC-Aもどうやったらすぐに2方向しかないことに気づけるんだろう
Aごときに時間使いたくない

**仕様書無しさん** · 2024/03/28(木) 21:21:24.15

>>224
普通にいるが...
agerって高卒？

**仕様書無しさん** · 2024/03/28(木) 21:27:02.49

ageカスは明治卒のエリート

**仕様書無しさん** · 2024/03/28(木) 21:30:54.36

>>228
最後の人は右か左の残ってる方から取るしかない
↓
最後の人が右から取るとすると、その隣の人も右から取るしかない

みたいな感じで思いついた

**仕様書無しさん** · 2024/03/28(木) 21:35:02.17

寒色ネトストゴシインコ嫉妬で特定を試みてくるし害悪すぎる

**仕様書無しさん** · 2024/03/28(木) 21:37:34.02

>>231
言われればそうなんだけど、取る順番とか利き手にばかり意識が向いちゃってそもそもどのスプーンを取るかの観点に中々着目することが出来なかったんだよな、それに着目することで数え上げやすくなることが見えなくて
問題文の設定も上手いと思う

**仕様書無しさん** · 2024/03/28(木) 21:40:08.83

>>219
解説きとるやん
サンキューガイジ

上界下界はすぐ見えたんだが頂点のリス値をつけると親子間のリス差が常に1以下になるってのが見えなかったな
そこさえ抜ければ構築法が(リス値, 深さ)の辞書順なのは試行錯誤で出てきそう
リス値の貪欲割り当て法は時間かければ解けるので一番の実力要素はリスへの不理解とみた
ためになった

**仕様書無しさん** · 2024/03/28(木) 21:41:20.09

🐿値

**仕様書無しさん** · 2024/03/28(木) 21:41:27.57

かわいいね

**仕様書無しさん** · 2024/03/28(木) 21:43:47.10

インコの時代も終わりだな

**仕様書無しさん** · 2024/03/28(木) 21:55:22.00

Σ🐿=3

**仕様書無しさん** · 2024/03/28(木) 22:04:24.63

>>238
天才

**仕様書無しさん** · 2024/03/28(木) 22:19:54.57

語呂・由来・記号どれも恵まれてるのにガイジスレ初出なせいで二度と表に出てこないクッソ哀れな動物

**仕様書無しさん** · 2024/03/28(木) 22:23:25.16

nimさんに弔ってもらえ

**仕様書無しさん** · 2024/03/28(木) 22:47:28.58

novisteps普通に便利そう

**仕様書無しさん** · 2024/03/28(木) 23:13:06.91

それでもマスくんならなんとかしてくれる

**仕様書無しさん** · 2024/03/28(木) 23:17:41.90

マス君が、水になるまで名前キングオブガイジのままにするって言ってたの忘れてないぞ

**仕様書無しさん** · 2024/03/28(木) 23:32:13.29

マスくんは競プロ半引退だろ
結局はageカス未満の競プロerだった

**仕様書無しさん** · 2024/03/28(木) 23:59:42.93

インココン運営しっかりしてくれよな

**仕様書無しさん** · 2024/03/29(金) 00:02:15.74

マスくんが破った約束
・今年中に青目指す
・毎日英語勉強
・水なれるまでキングオブガイジ

**仕様書無しさん** · 2024/03/29(金) 00:03:15.94

いかにインコ大学といえ大学を借りて60人以上集めるんだから舐めた運営したらあかんやろ

**仕様書無しさん** · 2024/03/29(金) 00:06:24.79

マスくん見てると普通の才能の人は水色に行くのもかなり苦労するんだろうなって気はしてる

**仕様書無しさん** · 2024/03/29(金) 00:06:56.65

なんでインココンにそんな詳しいん？
おれまったくわからんのだが

**仕様書無しさん** · 2024/03/29(金) 00:08:01.98

>>249
しかもマスくんでさえ緑に到達したのは早い方だからな(4カ月)

**仕様書無しさん** · 2024/03/29(金) 00:11:20.75

日課のゴシで拾った
ゆきこうだが飛びそうな話も拾ったがこっちは主催が若い衆なのでゴシる価値なし

**仕様書無しさん** · 2024/03/29(金) 00:14:41.43

マスくんは普通の人みたいな扱いになってるけどで環境ガチャ失敗からのfランだぞ
普通のレベルなら水は楽になれる

**仕様書無しさん** · 2024/03/29(金) 00:35:12.98

普通とは大学受験の偏差値50未満のことだぞ
50ではなく50未満な
普通を高く見積もりすぎ

**仕様書無しさん** · 2024/03/29(金) 00:52:42.04

偏差値50未満の存在は無視してよいと知られています
普通とは偏差値70程度のことを指します

**仕様書無しさん** · 2024/03/29(金) 00:59:24.45

253の文脈での普通はスレで共有する普通の概念と異なることくらい自明ですよね

**仕様書無しさん** · 2024/03/29(金) 01:02:51.28

このスレでいう普通とはtkndks&ut&人間のことです

**仕様書無しさん** · 2024/03/29(金) 01:09:15.81

アンケートの結果このスレにtkndks&UT&暖色のやつが想像以上に少ないことは分かってる

**仕様書無しさん** · 2024/03/29(金) 01:43:18.57

R1840未満はレート分布やランキングにのせる必要ないんじゃないか？

**仕様書無しさん** · 2024/03/29(金) 04:40:24.66

おまんぽ女学園

**仕様書無しさん** · 2024/03/29(金) 07:27:11.27

ガイジスレ終了

**仕様書無しさん** · 2024/03/29(金) 08:14:46.65

病気を、治したい
AGC前なのに睡眠障害でめちゃくちゃだよ

**仕様書無しさん** · 2024/03/29(金) 08:31:12.01

アンケート云々って言ってるけど自分が人間に値しないのを自覚してるからこそこのスレに定住してるのでは

**仕様書無しさん** · 2024/03/29(金) 08:46:42.27

【結婚難】違反SEの代償【孤独死】

☆大迷惑だから稼働減らして収入増やせ☆

金稼ぎ無理！
共働き無理！

偽装委託多重派遣
　 ↓
時間外労働違反
　 ↓
低技術
　　 ↓
低収入
　　 ↓
結婚難
　　 ↓
孤独死

反社会な孤独死の現場
https://i.imgur.com/pALCFXJ.jpg

**仕様書無しさん** · 2024/03/29(金) 09:15:07.93

ガイジガイジガイジガイジガイジイジガイジガイジガ
イジガイジガイジガイジガイジガイジガイジガイジガ

**仕様書無しさん** · 2024/03/29(金) 09:16:27.83

ガイジガイジガイジガイジガイジイジガイジガイジガ
イジガイジガイジガイジガイジガイジガイジガイジガ
ガイジガイジガイジガイジガイジガイジガイジガイジ

**仕様書無しさん** · 2024/03/29(金) 09:21:53.99

健常者擬態インコ

**仕様書無しさん** · 2024/03/29(金) 09:34:30.35

ガイジがジガイ

**仕様書無しさん** · 2024/03/29(金) 10:19:26.88

ヒトと関わることを諦めることから始めよう

**仕様書無しさん** · 2024/03/29(金) 10:22:48.06

そして輝くウルトラガイジ

**仕様書無しさん** · 2024/03/29(金) 10:31:14.81

Xやってる時点でFAKE野郎確定だからな
結局お前らも“そっち側”の人間だったんだね

**仕様書無しさん** · 2024/03/29(金) 10:39:40.79

本物はPornhubに解説を上げるからな

**仕様書無しさん** · 2024/03/29(金) 10:42:08.14

Pornhubでなんの解説するって？

**仕様書無しさん** · 2024/03/29(金) 10:47:22.38

AC射精完了という言葉からもわかるように競プロって人気なアダルトコンテンツだと思うんだけど、DLSiteでの競プロの隠語って何になったの？　これわからないと困るんだけど

**仕様書無しさん** · 2024/03/29(金) 10:48:34.51

競プロって一人で完結する趣味なのが良いところだから馴れ合いはFAKE

**仕様書無しさん** · 2024/03/29(金) 10:50:12.71

メスイキAC射精

**仕様書無しさん** · 2024/03/29(金) 10:50:37.59

アダルトコンテンツ認定は草ァ！ｗｗｗ
俺達ガイジスレ面白過ぎィ！ｗｗｗ

**仕様書無しさん** · 2024/03/29(金) 10:51:01.47

馴れ合いインコが流入してきてるからな

**仕様書無しさん** · 2024/03/29(金) 10:52:58.42

せーので病気を治してスレ卒業

**仕様書無しさん** · 2024/03/29(金) 11:01:07.47

インコにはチンコがありません

**仕様書無しさん** · 2024/03/29(金) 11:04:07.79

スレ既出

**仕様書無しさん** · 2024/03/29(金) 11:07:01.48

競プロerは典型が好きだからね
過去スレ精進サボりインコのためにも定期的に色々なネタを再放送してくれる良心的なスレ

**仕様書無しさん** · 2024/03/29(金) 11:23:43.74

オウム返し定期

**仕様書無しさん** · 2024/03/29(金) 11:25:55.06

風びゅうびゅうで草

**仕様書無しさん** · 2024/03/29(金) 12:03:34.68

E8様のスライドで森羅万象を勉強したい

**仕様書無しさん** · 2024/03/29(金) 12:22:41.92

何を勘違いしてるか知らんが競プロerなら典型は貶し言葉だろ

**仕様書無しさん** · 2024/03/29(金) 12:25:32.95

どこをどう読んだら典型を褒めてるって解釈ができるんだ？

**仕様書無しさん** · 2024/03/29(金) 12:26:13.45

E8様が典型の権化だと思ってるインコ

**仕様書無しさん** · 2024/03/29(金) 12:27:10.17

parrot
par・rot /pˈærət/
【名詞】【可算名詞】
1【鳥】オウム.
2わけもわからずに他人の言葉を繰り返す人.
【動詞】【他動詞】
〈…を〉機械的に繰り返す，おうむ返しに言う.

わけもわからずに他人の言葉を繰り返す人.←やめてね

**仕様書無しさん** · 2024/03/29(金) 12:28:55.29

インコは解説をオウム返ししてるだけだから典型問題は過学習で解けるようになってもARCAGCでレートを伸ばせない　一生インコ大王

**仕様書無しさん** · 2024/03/29(金) 12:29:44.60

まるでポルノコンテンツに異常に詳しい童貞のようでもある

**仕様書無しさん** · 2024/03/29(金) 12:35:36.86

ABCdiv2,3は鈍らないための.毎日のルーチンみたいなものだろ

**仕様書無しさん** · 2024/03/29(金) 12:36:44.54

div4は？

**仕様書無しさん** · 2024/03/29(金) 12:37:27.48

昨日のdiv4サボったから恣意的に抜いたんですよね？

**仕様書無しさん** · 2024/03/29(金) 12:40:40.92

俺もdiv4は流石にサボって寝ちゃったな
高々水diffの典型問題集合でバチャで30分程度で確実に倒せるはずなのではい

**仕様書無しさん** · 2024/03/29(金) 12:41:18.08

div3,4程度だったら老後もボケ防止で楽しめそう　せいじいもこのために競プロを嗜んでたのかも

**仕様書無しさん** · 2024/03/29(金) 12:42:37.74

div4やるくらいならパ研upsolveのほうがよいそれはそう

**仕様書無しさん** · 2024/03/29(金) 12:50:35.82

競プロポルノで毎日射精してるし、別にコンテストじゃなくていもいい

**仕様書無しさん** · 2024/03/29(金) 13:01:31.05

本番（コンテスト）を生（リアルタイム）でヤったほうが気持ちよく射精できるだろ

**仕様書無しさん** · 2024/03/29(金) 13:02:50.20

正直div4レベルだとADTと大差ないのでだいぶ優先度落ちてしまう

**仕様書無しさん** · 2024/03/29(金) 13:04:27.90

div4は早解きの練習になるぐらいか