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

**仕様書無しさん** · 2024/05/12(日) 23:43:01.26

競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
競技プログラミングにハマるプログラマのスレ 168
https://medaka.5ch.net/test/read.cgi/prog/1711463770/
競技プログラミングにハマるプログラマのスレ 169
https://medaka.5ch.net/test/read.cgi/prog/1711884759/
競技プログラミングにハマるプログラマのスレ 170
https://medaka.5ch.net/test/read.cgi/prog/1712220373/
競技プログラミングにハマるプログラマのスレ 171(旧)
https://medaka.5ch.net/test/read.cgi/prog/1712726816/
競技プログラミングにハマるプログラマのスレ 171(新)
https://medaka.5ch.net/test/read.cgi/prog/1712726828/
競技プログラミングにハマるプログラマのスレ 172
https://medaka.5ch.net/test/read.cgi/prog/1713176839/
競技プログラミングにハマるプログラマのスレ 173
https://medaka.5ch.net/test/read.cgi/prog/1714042920/
競技プログラミングにハマるプログラマのスレ 174
https://medaka.5ch.net/test/read.cgi/prog/1714572646/
競技プログラミングにハマるプログラマのスレ 175
https://medaka.5ch.net/test/read.cgi/prog/1714981816/

**仕様書無しさん** · 2024/05/13(月) 23:53:27.03

大きいコインから使う貪欲の正当性ってそんなに気になるもんなの？
同じ金額を選ぶなら後の自由度が高くなるようにするのがいいから...

**仕様書無しさん** · 2024/05/13(月) 23:54:49.82

>>582
界隈の強いひとにギリギリ認められているのが青コーダーだからね

**仕様書無しさん** · 2024/05/13(月) 23:55:43.74

今回見たいな回はWA出したら被害結構あるし、そこの気持ち悪さ抱えたまま数分の間に解くのきつくないか

**仕様書無しさん** · 2024/05/13(月) 23:56:53.90

強い人 (ただしインコ)

**仕様書無しさん** · 2024/05/13(月) 23:57:41.57

そもそも金額の組み合わせがちょっと違ったら正当じゃないからな
通貨問題典型ではあるが

**仕様書無しさん** · 2024/05/13(月) 23:58:04.19

貪欲で払えるなら自明に払える(そのように払える)
逆払えるなら、ある払い方の2つの払い方についてより大きな硬貨と小さい硬貨で入れ替えて大きい硬貨を貪欲で選んでいるような払い方にできる？

**仕様書無しさん** · 2024/05/13(月) 23:58:15.20

>>587
これ書いたの私です　感謝しなさい

**仕様書無しさん** · 2024/05/13(月) 23:58:36.53

人呼ばわりなのに実態はインコとはこれいかに

**仕様書無しさん** · 2024/05/13(月) 23:58:51.67

インコイン問題というわけか
スレに媚びすぎ

**仕様書無しさん** · 2024/05/14(火) 00:00:00.21

いや、必ず入れ替えられるな(それぞれの硬貨が整数倍なので)
じゃあOK

**仕様書無しさん** · 2024/05/14(火) 00:00:00.55

まあわかる
大銭から払う貪欲の正当性が示せない場合小銭から払う貪欲も試さなあかんが、これなら1ペナ吐くのと期待値変わらんと思って大銭貪欲で未証明subした

**仕様書無しさん** · 2024/05/14(火) 00:00:43.48

Aにしては簡単すぎて怖いのはわかるけど流石に有名問題すぎるため
BCも同じ感覚でポンポン提出した

**仕様書無しさん** · 2024/05/14(火) 00:00:49.37

こんな問題も解けないのかみたいな枠で引用されるイメージが強い
インコにしてはできるハイエンド型インコだけど、人間の問題解かせたらやっぱ全然だめだねみたいな

**仕様書無しさん** · 2024/05/14(火) 00:01:23.16

優インコ:青
インコ大王:黄色タッチ
インコ人間境界線:2100

再掲

**仕様書無しさん** · 2024/05/14(火) 00:01:27.67

3円玉と5円玉の場合は破綻するので普通に怖いとおもった

**仕様書無しさん** · 2024/05/14(火) 00:02:10.43

まあ双子なら前半はコーナーケースサンプルに置いてくれるイメージある

**仕様書無しさん** · 2024/05/14(火) 00:03:12.92

Bは作問歴があれば10^6がジャッジの都合でしかない値だと確信できる

**仕様書無しさん** · 2024/05/14(火) 00:03:46.50

そういう指定こどふぉで無限回あるから関係ない

**仕様書無しさん** · 2024/05/14(火) 00:04:42.42

人間の問題とかいう概念好き
ハイエンド型インコもカッコよくて好き

**仕様書無しさん** · 2024/05/14(火) 00:05:06.91

>>565
これ結局解ける問題なの？

**仕様書無しさん** · 2024/05/14(火) 00:05:14.40

それぞれの硬貨が整数倍じゃなかったらどうなるの？
2種類とかじゃないと解けなくない？

**仕様書無しさん** · 2024/05/14(火) 00:06:06.99

部分話問題に帰着されるので色々辛そう
DP復元とかでできると思うけど貪欲では無理

**仕様書無しさん** · 2024/05/14(火) 00:08:01.42

>>608
コインの種類数次元のDPでどうですか？

**仕様書無しさん** · 2024/05/14(火) 00:08:25.62

>>607
gptに解答聞いたけど余裕で間違えてそうだから消しちゃった
でも解けるなら流石に既出そう

**仕様書無しさん** · 2024/05/14(火) 00:08:27.24

今回の200枚以下ならdp[i][j][k]=i番目の支払いまで終わってAをj、Bをk枚使った時のCを使用した数で持てば3枚くらいまでは処理できそう(支払い方が結構多いので遷移ダルいけど)

**仕様書無しさん** · 2024/05/14(火) 00:09:06.78

>>565
円環上でバブルソートをすると考えて、最適な操作の場合必ずどこかに交換が起きない部分があるのでどこで切るかを全部試す、みたいな？

**仕様書無しさん** · 2024/05/14(火) 00:10:14.05

インコ作問やめてね

**仕様書無しさん** · 2024/05/14(火) 00:11:29.08

i種類目のお土産までを買ったとき、(X,Y,Z)円玉が残り(x,y,z)枚
の4次元dpでzは落とせる的な

**仕様書無しさん** · 2024/05/14(火) 00:12:08.04

円環のバブルソート最小化ってできるの？

**仕様書無しさん** · 2024/05/14(火) 00:12:50.55

>>613
ARCで出題されたらメタ読みでこれでやるけど交換しない場所があるっていう証明ができない

**仕様書無しさん** · 2024/05/14(火) 00:12:55.38

nimさんに教えてもらおう

**仕様書無しさん** · 2024/05/14(火) 00:14:01.52

もしそれでAC射精完了できるのなら普通にARC-Bとかに置ける良問そう

**仕様書無しさん** · 2024/05/14(火) 00:17:55.50

上界下界が実は達成できます、隣接を見れば見通しが良くなります、区切りを全探索出来ますみたいなのARCで無限回見た

**仕様書無しさん** ころころ · 2024/05/14(火) 00:24:54.50

交換しない箇所を決め打って転倒数をO(1)で更新か

**仕様書無しさん** ころころ · 2024/05/14(火) 00:25:41.04

交換しない箇所があることの保証はどうやって証明しますか

**仕様書無しさん** ころころ · 2024/05/14(火) 00:26:54.50

e8くんのアンチおるやん
twitter.com/aplysiaSheep/status/1789813006848729167?t=7pIwkQiItX0Ley5BpvFjYw&s=19
https://twitter.com/thejimwatkins

**仕様書無しさん** · 2024/05/14(火) 00:30:35.77

マシュマロにしか来ない雑魚

**仕様書無しさん** · 2024/05/14(火) 00:32:43.28

個人的には所謂毒マロを拾うのもどうかと思う

**仕様書無しさん** · 2024/05/14(火) 00:46:44.13

のだ氏ものん氏ものし氏も毒マロは無視してるからな

**仕様書無しさん** · 2024/05/14(火) 00:52:45.95

キモいと思うのはお前が嫉妬してるから定期

**仕様書無しさん** · 2024/05/14(火) 00:54:57.84

競プロ界隈がキモい連中だらけだから、競プロ関係者は競い合うようによりキモくなっている
社長も副社長もキモいのはこのため

**仕様書無しさん** · 2024/05/14(火) 00:56:53.40

結局TKNDKS+UT+暖色(赤色)という完全なる上位存在への嫉妬ドリブンでしかない

**仕様書無しさん** · 2024/05/14(火) 01:05:12.23

GPT-4にキモくないように書き直して、ってお願いすればいいだけなのに

**仕様書無しさん** · 2024/05/14(火) 01:32:22.04

学業、実は楽しいがち

**仕様書無しさん** · 2024/05/14(火) 05:44:42.82

ラジオ体操第一をして疲弊　ねりゅ

**仕様書無しさん** · 2024/05/14(火) 06:29:01.35

ガイジスレ終了

**仕様書無しさん** · 2024/05/14(火) 08:45:38.87

GPT-4oすげえな
もはや人間よりも圧倒的に人語を扱うのが上手い

**仕様書無しさん** · 2024/05/14(火) 08:59:57.10

はやくtourist超えねえかな

**仕様書無しさん** · 2024/05/14(火) 09:25:12.52

4oでようやく使い物になる速度になった
ついていけない競合はどんどん潰されそう

**仕様書無しさん** · 2024/05/14(火) 09:31:43.77

自分の実力ではどうしようもないことを悟ってLLMに希望を見出すインコ虚しすぎる

**仕様書無しさん** · 2024/05/14(火) 10:33:57.98

INKo

**仕様書無しさん** · 2024/05/14(火) 10:38:28.45

I'm also incredibly excited about the possibility of this as an always available coding rubber duck. The multimodal demos they showed really drove this home, how collaboration with the model can basically be as seamless as screensharing with someone else. Incredible.

**仕様書無しさん** · 2024/05/14(火) 10:41:35.29

https://vimeo.com/945587328
the Khan academy demo is nuts. The inflections are so good. It's pretty much right there in the uncanny valley because it does still feel like you're talking to a robot but it also directly interacting with it. Crazy stuff.

**仕様書無しさん** · 2024/05/14(火) 10:51:36.88

ゴム鴨さんクワクワで草
対話機能のことバカにしてるだろ

**仕様書無しさん** · 2024/05/14(火) 10:53:04.23

愛嬌があってしゃべらないゴム鴨なら俺のほうが適任だが

**仕様書無しさん** · 2024/05/14(火) 11:34:14.42

競プロの終焉も時間の問題かぁ

**仕様書無しさん** · 2024/05/14(火) 11:59:59.87

GPT-3.5→茶色
GPT-4.0→茶色上位(たまに奥も解けるので緑は運次第)
GPT-4o→何色なの？

**仕様書無しさん** · 2024/05/14(火) 12:18:13.21

式変形がめちゃくちゃ上手く纏まって気持ち良すぎる
課題でAC射精完了するとは思わなかった

**仕様書無しさん** · 2024/05/14(火) 12:25:20.52

LLMの開発に従事してないどころか仕組みすらわかってない寒色インコ「頼む、俺の知能じゃもう競プロでは伸びないからLLMがめちゃくちゃにしてくれ～～～～泣泣泣」

**仕様書無しさん** · 2024/05/14(火) 12:25:44.45

GPTがどういう仕組みで動いてるのか一ミリも分かってなさそう

**仕様書無しさん** · 2024/05/14(火) 12:29:43.31

インコは相変わらず他責・他人任せすぎるな
自分の実力で勝負せんかい

**仕様書無しさん** · 2024/05/14(火) 12:32:19.98

巨人の肩に乗る小人の分際で図に乗るな

**仕様書無しさん** ころころ · 2024/05/14(火) 12:33:05.28

GPTの威を借るインコ

**仕様書無しさん** · 2024/05/14(火) 12:34:05.33

競プロも終わりが近いの悲しいわ

**仕様書無しさん** · 2024/05/14(火) 12:35:04.35

頼む、終わってくれえええええ泣

**仕様書無しさん** · 2024/05/14(火) 12:35:18.25

暖色への嫉妬定期

**仕様書無しさん** · 2024/05/14(火) 12:35:21.75

競プロはオンラインに頼りきりなのがなぁ

**仕様書無しさん** · 2024/05/14(火) 12:36:37.87

不正が蔓延してまともにコンテストが成り立たなくなる日が近い
将来的にはIOIとICPC以外のコンテストが無くなるだろう

**仕様書無しさん** · 2024/05/14(火) 12:37:18.45

>>647
仕組みとかどうでもいいかな

**仕様書無しさん** · 2024/05/14(火) 12:37:35.05

そうだといいね寒色で停滞してるインコくん

**仕様書無しさん** · 2024/05/14(火) 12:38:39.72

TKNDKSに嫉妬、UTに嫉妬、暖色に嫉妬、

今日は暖色に嫉妬のフェーズです
インコの知能への嫉妬は止まらない

**仕様書無しさん** · 2024/05/14(火) 12:40:22.33

競プロとか数オリ辺りに恨みがある人は自分の知能にコンプを持ってるってあの人も言ってた

**仕様書無しさん** · 2024/05/14(火) 12:41:41.01

数オリは生き残りそうだけど競プロは生き残れないだろうなぁ

**仕様書無しさん** · 2024/05/14(火) 12:41:50.36

ソフト指し理論定期

**仕様書無しさん** · 2024/05/14(火) 12:42:07.85

ライブラリペタリコンテストとかいうゴミカスなのではい

**仕様書無しさん** · 2024/05/14(火) 12:42:45.55

>>659
恨みっていうか、必要以上に時間をかけるのは馬鹿みたいだなって感じる

**仕様書無しさん** · 2024/05/14(火) 12:43:10.56

やったことないけどOMCも競プロ愚直で殴れるんじゃねーの

**仕様書無しさん** · 2024/05/14(火) 12:43:17.41

暖色だけど使えるもんは使ったほうがいい(対戦型ゲームなので)からGPTに課金しよかな

**仕様書無しさん** · 2024/05/14(火) 12:44:04.67

普通にトランスフォーマー×かなりでかい数だろ
LLMに限らず最近の有名なモデルって特徴量ベクトルの次元を100倍にしたぜ、とかこのモデルを1000個組み合わせました、じゃん

**仕様書無しさん** · 2024/05/14(火) 12:44:10.18

>>663
お前はその空いた時間で何か成し遂げられたの？
お前よりも能力の高い人は両立余裕で出来てるから自分の低い能力を世の中の基準だと思うなよ

**仕様書無しさん** · 2024/05/14(火) 12:45:02.17

FPSのエイム練習は非本質なのでエイムアシスト使いますねと同じ理屈
クソつまらんエイム練で疲弊するバカはお前だけでいいです

**仕様書無しさん** · 2024/05/14(火) 12:45:19.42

>>664
OMCはプログラム禁止
だけどそれを検知する方法はないので全探索出来るやつは全部全探索(不正)と大学レベルの数学力があれば水青に行けてしまう

**仕様書無しさん** · 2024/05/14(火) 12:45:28.91

UTに暖色が多いのが全て
インコは競プロをやらなくても両方こなしてるやつにすぐ追い抜かれる

**仕様書無しさん** · 2024/05/14(火) 12:45:35.23

>>667
詭弁過ぎてわろた
世の中の基準の話は上位互換がいることとどう関係しますか

**仕様書無しさん** · 2024/05/14(火) 12:46:24.72

受験勉強に時間割くのも時間の無駄って主張して自分の低学歴を正当化してそう
一生しょうもない人生送っててほしい

**仕様書無しさん** · 2024/05/14(火) 12:46:28.23

>>669
大学レベルの数学力がない前提だとどこまで行けそうなん？

**仕様書無しさん** · 2024/05/14(火) 12:47:02.62

岡田康志も河野玄斗もsakiもさぐさぐも競プロはやってないからなぁ

**仕様書無しさん** · 2024/05/14(火) 12:47:06.88

OMCを競プロで殴る話で数学力を前提とするのは違うと思うので

**仕様書無しさん** · 2024/05/14(火) 12:47:53.69

>>656
そんなんだから知能が低いんだよ　妄想で語るな

**仕様書無しさん** · 2024/05/14(火) 12:47:55.11

UTに暖色が多いのって
UT→レートじゃなくて知能→UT、レートだと思うんだよな
結婚してる人のほうが研究うまく行くみたいな言説も結婚→研究じゃなくて能力→結婚、研究な気がする

**仕様書無しさん** · 2024/05/14(火) 12:48:27.45

結局全部相関があるからね

**仕様書無しさん** · 2024/05/14(火) 12:49:19.30

TKNDKS+UTなどの努力+才能+環境が揃った人材が総取り出来るシステム

**仕様書無しさん** · 2024/05/14(火) 12:50:27.51

(入人、結婚などを)していない群にはしたくてもできない人が全員放り込まれるのではい

**仕様書無しさん** · 2024/05/14(火) 12:50:28.14

>>673
俺(旧帝)が緑水反復まで行ったので受験数学ある程度出来るならプログラムで不正すれば水色までは行けそう
数学苦手で競プロの知識しかない場合は愚直に全探索書きまくれば緑くらい？

**仕様書無しさん** · 2024/05/14(火) 12:50:51.83

>>677
それはそうすぎる
能力がある人間がUTなり暖色なりを達成してるだけの話

**仕様書無しさん** · 2024/05/14(火) 12:51:59.21

俺は頭悪いから競技プログラミングに全ツッパよ

**仕様書無しさん** · 2024/05/14(火) 12:52:32.21

全ツッパしても片手間でやってる高知能に負けるのが悲しいね

**仕様書無しさん** · 2024/05/14(火) 12:52:38.44

OMCの色とすごさの感覚がわからないため

**仕様書無しさん** · 2024/05/14(火) 12:54:57.40

>>685
暖色の人数がかなり少ないので赤や橙、黄色はかなり強い
サンプル数=3だけど偏差値60-67.5ある理系なら緑か水色まではスルッと行く
って感じだ

**仕様書無しさん** · 2024/05/14(火) 12:55:10.28

AtCの1色下とみなしてええな
AtC黄=OMC青