競技プログラミングにハマるプログラマのスレ 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:08:27.74

EFの話をコンテ直後にスレでしてたらそれはのいみさんだろ

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

栗さんであってほしい　こんなに解説配信の実況レスしてるのに

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

考察パートは青上位想定で実装998コーナー回避で黄色diff想定だと思う

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

というかWがそんな感じのツイートしてなかったっけ

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

赤diffストリークが続いており非常によい

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

e8くんフォローして無いので

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

すぬけさんのARCでのDの提出コード
ttps://atcoder.jp/contests/arc177/submissions/53420383

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

言われると方針は難しくはないけど、まあめんどいパートはちょこちょこあるしそれに998のバグが挟まると苦しそう

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

草生えまくり

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

赤diffストリークって続けられるほど問題あるの？
インコだから分からない

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

別にマジでスレは卒業したいんだよな
普通にスレのやる気あるデア勢でdiscord作って移住してネトストゴシインコを置き去りにしたい

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

本スレに移住するだけで良かったりしない？

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

>>538
problems見ればわかるけど赤だけでも300くらいあるし銅以上含めたらもっとある

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

すぬけさんもDは解けなかったか

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

解けないというかアンレだしやる気起きなかっただけでは

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

でもメンタル限界の日に変な書き込みできませんよ

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

いたとしたら特定容易

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

AのFAってgptなのかなぁ
コードみるとそんな感じがする

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

俺はメンタル限界の日に変な書き込みをしているため

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

E通してから14分しかなかっただけの話では

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

キチゲ発散スレなので

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

たしかにGPTっぽい
判定ツール使うと高確率でAI生成されたコードと判定される

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

メンタル限界の日に憂さ晴らしにここ来てるわ

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

ガイジスレはガイジ達のハッテン場

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

discordで馴れ合うのとxで馴れ合うの、違いは何？

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

>>550
gpt使うだけでARC-AでFAとれちゃうとなると何とも言えない気持ちになるな

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

昨日のARC-Aは実質ABC-CなのでGPTでも解けるのはそう

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

灰diffがAIで解かれてそんなに騒ぐ？

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

Xで馴れ合えない人がここに集まってるため

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

GPT Detectorみたいな感じでググるとたくさん判定ツールでてくるよ

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

教授にもツールのことを教えておこう

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

AI検知系ツール
誤検知多すぎておわり

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

社会不適合エピソードを消費的に披露してキャッキャしてる奴にはなりたくないので
ジェネルシエピソードはここだけにしてる

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

ワイはゴシの話をする時はスレで、デアの話をする時はXで強い人(青以上)を相手にするようにしてる

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

最近はDiscordが流行ってんの？

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

誤検知のせいで単位落として留年したからAIは死ぬまで恨む

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

AtCoder Regular Contest - A (300点) で出るようなアドホックな易しめの問題を作ってください。

ChatGPT
問題文:
あなたはある日、買い物リストを作成しています。買い物リストには N 個のアイテムがあり、それぞれのアイテムは 1 から N までの番号が付けられています。
しかし、あなたは急いでいて、買い物リストのアイテムをランダムな順番で記入してしまいました。幸いなことに、あなたはその買い物リストに対して 2 つの操作が可能です。

操作1: リスト内の隣接する 2 つのアイテムの位置を交換する。
操作2: リスト内の先頭と末尾のアイテムの位置を交換する。

最小の操作回数で、買い物リストを番号順に並び替えるプログラムを作成してください。ただし、1 ≦ N ≦ 100 とします。

入力:
最初の行にはアイテムの数 N (1 ≦ N ≦ 100) が与えられます。
2 番目の行には 1 から N までの整数が空白区切りで与えられます。これが買い物リストの初期状態を表します。

出力:
最小の操作回数を出力してください。

制約:
入力される整数はすべて整数であることが保証されます。

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

わかる
不真面目イキリは普通にダサいし中高生までが限度

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

今日も頑張ってる中学生・高校生尊い

おい！未就学のガキ、小学生、大学生、おっさんは尊くないぜ！

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

狂人の真似とて大路を走らば即ち狂人なり

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

周りに流されて不真面目イキリしてる大学生は本当にキツいししょうもないやつしかいない

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

青以上は強いラインとして微妙だろ
こんな問題も解けないんですよ定期

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

君たちはどうイキるか

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

水青黄スレ終了

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

怠惰な張り付きインコによる数字のマジック定期

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

>>565
最初状態を頂点に持つBFSだと思っちゃった
1から順にえっちらおっちら移動させるシミュレーションすればいいのかな？

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

>>565
最初状態を頂点に持つBFSだと思っちゃった
1から順にえっちらおっちら移動させるシミュレーションすればいいのかな？

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

えっち (〃ﾉдﾉ)

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

明らかにA300レベルじゃない問題はNG

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

来週のARCも勝つぞ

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

機械学習の学習でずっとGPU回してるけど電気代やばそう

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

1から順にえっちしても解けんため

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

昨日のAみたいなの正当性証明のdiffと思いつくdiffの乖離がでかすぎるから好きじゃないわ
ARC-Aなんて所詮この程度ｗって思って投げるのが正解になってしまう

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

「強い人(青以上)」はインコ透けすぎでしょ

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

300点のコイン問題が貪欲インコ問出ないとやばいため→AC

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

インコ問のcommonの部分

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

ああいう証明が難しい貪欲はあまりABC的じゃなくてARC/AGCっぽいんだけど、あまりにもその貪欲を思いつくのが簡単すぎたって感じ

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

Bの操作回数を最小化する場合

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

前回の双子ARCのAを両替の問題って言ってくれた人のおかげで今回はすぐ貪欲だと分かった

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

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